Samples and std additions

18 files changed, 301 insertions, 63 deletions

diff --git a/bruijn.cabal b/bruijn.cabal
index 8f768fb..7b92d04 100644
--- a/bruijn.cabal
+++ b/bruijn.cabal
@@ -36,6 +36,7 @@ data-files:
     std/test_all.sh
     std/AIT/Beavers.bruijn
     std/Number/Binary.bruijn
+    std/Number/Bruijn.bruijn
     std/Number/Conversion.bruijn
     std/Number/Pairing.bruijn
     std/Number/Ternary.bruijn
diff --git a/docs/wiki_src/coding/recursion.md b/docs/wiki_src/coding/recursion.md
index 5a3ab85..89e71c8 100644
--- a/docs/wiki_src/coding/recursion.md
+++ b/docs/wiki_src/coding/recursion.md
@@ -69,9 +69,9 @@ g [[[=?0 true (1 --0)]]]
 # the even? recursive call will be the first argument (2)
 h [[[=?0 false (2 --0)]]]
 
-even? head (y* g h) ⧗ Number → Boolean
+even? head (y* (g : {}h)) ⧗ Number → Boolean
 
-odd? tail (y* g h) ⧗ Number → Boolean
+odd? tail (y* (g : {}h)) ⧗ Number → Boolean
 ```
 
 Read more about this in the blog post [Variadic fixed-point
diff --git a/samples/rosetta/de_bruijn_sequence.bruijn b/samples/rosetta/de_bruijn_sequence.bruijn
new file mode 100644
index 0000000..1012223
--- /dev/null
+++ b/samples/rosetta/de_bruijn_sequence.bruijn
@@ -0,0 +1,15 @@
+# TODO: Too slow to be published. Probably needs Maps/Sets/Vectors/sth.
+
+:import std/Combinator .
+:import std/Char C
+:import std/Math .
+:import std/List .
+
+# very slow but elegant
+de-bruijn y [[[C.?infix? (take 0 1) ~1 case-end case-rec]]]
+	case-rec max-by (compare ⋔ length) ([3 (0 : 2) 1] <$> (C.?nub 1))
+	case-end drop 0 1
+
+:test (de-bruijn "abcd" (+2)) ("dccaadbbacbdabcd")
+
+main [[0]]
diff --git a/samples/rosetta/halt_and_catch_fire.bruijn b/samples/rosetta/halt_and_catch_fire.bruijn
new file mode 100644
index 0000000..e053451
--- /dev/null
+++ b/samples/rosetta/halt_and_catch_fire.bruijn
@@ -0,0 +1,3 @@
+:test ([[0]]) ([[1]])
+
+main [[0 0] [0 0]]
diff --git a/samples/rosetta/higher_order_functions.bruijn b/samples/rosetta/higher_order_functions.bruijn
new file mode 100644
index 0000000..952d08f
--- /dev/null
+++ b/samples/rosetta/higher_order_functions.bruijn
@@ -0,0 +1,7 @@
+first [0 [[0]]]
+
+second [first [[1]]]
+
+:test (second) ([[[[0]]]])
+
+main [[0]]
diff --git a/samples/rosetta/luhn_test_of_credit_card_numbers.bruijn b/samples/rosetta/luhn_test_of_credit_card_numbers.bruijn
new file mode 100644
index 0000000..e52011e
--- /dev/null
+++ b/samples/rosetta/luhn_test_of_credit_card_numbers.bruijn
@@ -0,0 +1,14 @@
+:import std/Combinator .
+:import std/Math .
+:import std/List .
+
+luhn number→list → reverse → check → (\mod (+10)) → zero?
+	check y [[[[0 [[[6 \5 (4 + (5 odd even)) 1]]] 1]]]] k (+0)
+		odd 2
+		even digit-sum (2 ⋅ (+2))
+
+:test (luhn (+61789372994)) ([[1]])
+:test (luhn (+49927398716)) ([[1]])
+:test (luhn (+49927398717)) ([[0]])
+:test (luhn (+1234567812345678)) ([[0]])
+:test (luhn (+1234567812345670)) ([[1]])
diff --git a/samples/rosetta/sorting_quicksort.bruijn b/samples/rosetta/sorting_quicksort.bruijn
index f55f128..0413024 100644
--- a/samples/rosetta/sorting_quicksort.bruijn
+++ b/samples/rosetta/sorting_quicksort.bruijn
@@ -4,8 +4,8 @@
 
 sort y [[0 [[[case-sort]]] case-end]]
 	case-sort (4 lesser) ++ (2 : (4 greater))
-		lesser 1 <#> (\les? 2)
-		greater 1 <#> (\geq? 2)
+		lesser (\les? 2) <#> 1
+		greater (\geq? 2) <#> 1
 	case-end empty
 
 :test (sort ((+3) : ((+2) : {}(+1)))) ((+1) : ((+2) : {}(+3)))
diff --git a/samples/rosetta/sum_and_product_of_an_array.bruijn b/samples/rosetta/sum_and_product_of_an_array.bruijn
new file mode 100644
index 0000000..70b146b
--- /dev/null
+++ b/samples/rosetta/sum_and_product_of_an_array.bruijn
@@ -0,0 +1,6 @@
+:import std/List .
+:import std/Math .
+
+arr (+1) : ((+2) : ((+3) : {}(+4)))
+
+main [∑arr : ∏arr]
diff --git a/samples/rosetta/validate_isin.bruijn b/samples/rosetta/validate_isin.bruijn
new file mode 100644
index 0000000..7608ed5
--- /dev/null
+++ b/samples/rosetta/validate_isin.bruijn
@@ -0,0 +1,30 @@
+:import luhn_test_of_credit_card_numbers .
+
+:import std/Number/Conversion .
+:import std/Combinator .
+:import std/String .
+:import std/Char .
+:import std/Logic .
+:import std/Number .
+
+# verifies ISIN format
+format? [len ⋀? country ⋀? security ⋀? checksum]
+	len (length 0) =? (+12)
+	country all? uppercase? (take (+2) 0)
+	security all? (φ or? uppercase? numeric?) (take (+9) (drop (+2) 0))
+	checksum numeric? _0
+
+# performs luhn test
+checksum? (map (from-base36 → number→string)) → concat → string→number → luhn
+	from-base36 binary→ternary → [(0 - (0 ≥? (+65) ((+65) - (+10)) (+48)))]
+
+# performs format and checksum test
+validate φ and? format? checksum?
+
+:test (validate "US0378331005") (true)
+:test (validate "US0373831005") (false)
+:test (validate "U50378331005") (false)
+:test (validate "US03378331005") (false)
+:test (validate "AU0000XVGZA3") (true)
+:test (validate "AU0000VXGZA3") (true)
+:test (validate "FR0000988040") (true)
diff --git a/std/Char.bruijn b/std/Char.bruijn
index df6c78b..75a0ab3 100644
--- a/std/Char.bruijn
+++ b/std/Char.bruijn
@@ -4,8 +4,61 @@
 
 :import std/Number/Conversion .
 
+# prefix for comparing functions
+?‣ &eq?
+
 # converts a char to a balanced ternary number
-char→number [binary→ternary (0 - '0')] ⧗ Char → Number
+char→number (\sub '0') → binary→ternary ⧗ Char → Number
+
+:test (char→number '0') ((+0))
 
 # converts a balanced ternary number to a char
-number→char ['0' + (ternary→binary 0)] ⧗ Number → Char
+number→char ternary→binary → (add '0') ⧗ Number → Char
+
+:test (number→char (+0)) ('0')
+:test (number→char (+9)) ('9')
+
+# returns true if char is in A-Z
+uppercase? φ and? (\geq? 'A') (\leq? 'Z') ⧗ Char → Boolean
+
+:test (uppercase? 'a') (false)
+:test (uppercase? 'z') (false)
+:test (uppercase? 'A') (true)
+:test (uppercase? 'Z') (true)
+:test (uppercase? '0') (false)
+
+# returns true if char is in a-z
+lowercase? φ and? (\geq? 'a') (\leq? 'z') ⧗ Char → Boolean
+
+:test (lowercase? 'a') (true)
+:test (lowercase? 'z') (true)
+:test (lowercase? 'A') (false)
+:test (lowercase? 'Z') (false)
+:test (lowercase? '0') (false)
+
+# returns true if char is in a-zA-Z
+alpha? φ or? lowercase? uppercase? ⧗ Char → Boolean
+
+:test (alpha? 'a') (true)
+:test (alpha? 'z') (true)
+:test (alpha? 'A') (true)
+:test (alpha? 'Z') (true)
+:test (alpha? '0') (false)
+
+# returns true if char is in 0-9
+numeric? φ and? (\geq? '0') (\leq? '9') ⧗ Char → Boolean
+
+:test (numeric? '0') (true)
+:test (numeric? '9') (true)
+:test (numeric? 'a') (false)
+
+# returns true if char is in a-zA-Z0-9
+alpha-numeric? φ or? numeric? alpha? ⧗ Char → Boolean
+
+:test (alpha-numeric? 'a') (true)
+:test (alpha-numeric? 'z') (true)
+:test (alpha-numeric? 'A') (true)
+:test (alpha-numeric? 'Z') (true)
+:test (alpha-numeric? '0') (true)
+:test (alpha-numeric? '9') (true)
+:test (alpha-numeric? '$') (false)
diff --git a/std/List.bruijn b/std/List.bruijn
index d63ab6a..d355ea9 100644
--- a/std/List.bruijn
+++ b/std/List.bruijn
@@ -216,9 +216,9 @@ filter z [[[rec]]] ⧗ (a → Boolean) → (List a) → (List a)
 		case-filter 4 2 (cons 2) i (5 4 1)
 		case-end empty
 
-…<#>… \filter
+…<#>… filter
 
-:test (((+1) : ((+0) : {}(+3))) <#> zero?) ({}(+0))
+:test (zero? <#> ((+1) : ((+0) : {}(+3)))) ({}(+0))
 
 # returns the last element of a list
 last ^‣ ∘ <~>‣ ⧗ (List a) → a
@@ -315,6 +315,12 @@ drop-while z [[[rec]]] ⧗ (a → Boolean) → (List a) → (List a)
 
 :test (drop-while zero? ((+0) : ((+0) : {}(+1)))) ({}(+1))
 
+# returns all tails of a list
+tails z [[rec]] ⧗ (List a) → (List a)
+	rec ∅?0 {}empty (0 : (1 ~0))
+
+:test (tails "abc") ("abc" : ("bc" : ("c" : {}empty)))
+
 # returns all combinations of two lists
 cross [[[[1 : 0] <$> 1] <++> 1]] ⧗ (List a) → (List b) → (List (Pair a b))
 
@@ -324,8 +330,6 @@ cross [[[[1 : 0] <$> 1] <++> 1]] ⧗ (List a) → (List b) → (List (Pair a b))
 # TODO: add/use triple type (list element types can be different)
 cross3 [[[[[[2 : (1 : {}0)] <$> 2] <++> 2] <++> 2]]] ⧗ (List a) → (List a) → (List a) → (List (List a))
 
-# :test (cross "ab" "cd") (('a' : 'c') : (('a' : 'd') : (('b' : 'c') : {}('b' : 'd'))))
-
 # returns pair of take-while and drop-while
 span [[(take-while 1 0) : (drop-while 1 0)]] ⧗ (a → Boolean) → (List a) → (Pair (List a) (List a))
 
@@ -369,8 +373,8 @@ split-list-by z [[[rec]]] ⧗ (a → Boolean) → (List a) → (List (List a))
 sort-asc z [[rec]]
 	rec 0 [[[case-sort]]] case-end
 		case-sort (4 lesser) ++ {}(2) ++ (4 greater)
-			lesser 1 <#> (\les? 2)
-			greater 1 <#> (\geq? 2)
+			lesser (\les? 2) <#> 1
+			greater (\geq? 2) <#> 1
 		case-end empty
 
 :test (sort-asc ((+3) : ((+2) : {}(+1)))) ((+1) : ((+2) : {}(+3)))
@@ -379,8 +383,8 @@ sort-asc z [[rec]]
 sort-desc z [[rec]]
 	rec 0 [[[case-sort]]] case-end
 		case-sort (4 greater) ++ {}(2) ++ (4 lesser)
-			greater 1 <#> (\geq? 2)
-			lesser 1 <#> (\les? 2)
+			greater (\geq? 2) <#> 1
+			lesser (\les? 2) <#> 1
 		case-end empty
 
 :test (sort-desc ((+1) : ((+2) : {}(+3)))) ((+3) : ((+2) : {}(+1)))
@@ -416,6 +420,24 @@ eq? ⋀?‣ ∘∘∘ zip-with ⧗ (a → a → Boolean) → (List a) → Boolea
 :test (eq? …=?… ((+1) : {}(+2)) ((+2) : {}(+2))) (false)
 :test (eq? …=?… empty empty) (true)
 
+# returns true if list is prefix of other list
+prefix? z [[[[rec]]]] ⧗ (a → a → Boolean) → (List a) → (List a) → Boolean
+	rec ∅?1 true (∅?0 false go)
+		go 1 [[2 [[(6 3 1) ⋀? (7 6 2 0)]]]]
+
+:test (prefix? …=?… ((+1) : {}(+2)) ((+1) : {}(+2))) (true)
+:test (prefix? …=?… ((+1) : {}(+2)) ((+0) : ((+1) : {}(+2)))) (false)
+:test (prefix? …=?… ((+1) : {}(+2)) ((+2) : {}(+2))) (false)
+:test (prefix? …=?… empty empty) (true)
+
+# returns true if list is within other list
+infix? [[[any? (prefix? 2 1) (tails 0)]]] ⧗ (a → a → Boolean) → (List a) → (List a) → Boolean
+
+:test (infix? …=?… ((+1) : {}(+2)) ((+1) : {}(+2))) (true)
+:test (infix? …=?… ((+1) : {}(+2)) ((+0) : ((+1) : {}(+2)))) (true)
+:test (infix? …=?… ((+1) : {}(+2)) ((+2) : {}(+2))) (false)
+:test (infix? …=?… empty empty) (true)
+
 # finds the first index that matches a predicate
 find-index z [[[rec]]] ⧗ (a → Boolean) → (List a) → Number
 	rec 0 [[[case-find]]] case-end
@@ -426,7 +448,7 @@ find-index z [[[rec]]] ⧗ (a → Boolean) → (List a) → Number
 :test (find-index (…=?… (+2)) ((+1) : ((+2) : ((+3) : {}(+2))))) ((+1))
 :test (find-index (…=?… (+4)) ((+1) : ((+2) : ((+3) : {}(+2))))) ((-1))
 
-# removes first element that match an eq predicate
+# removes first element that matches an eq predicate
 remove z [[[[rec]]]] ⧗ (a → a → Boolean) → a → (List a) → (List a)
 	rec 0 [[[case-remove]]] case-end
 		case-remove (5 2 4) 1 (2 : (6 5 4 1))
@@ -437,7 +459,7 @@ remove z [[[[rec]]]] ⧗ (a → a → Boolean) → a → (List a) → (List a)
 # removes duplicates from list based on eq predicate (keeps first occurrence)
 nub z [[[rec]]] ⧗ (a → a → Boolean) → (List a) → (List a)
 	rec 0 [[[case-nub]]] case-end
-		case-nub 2 : (5 4 (1 <#> [¬(5 0 3)]))
+		case-nub 2 : (5 4 ([¬(5 0 3)] <#> 1))
 		case-end empty
 
 :test (nub …=?… ((+1) : ((+2) : {}(+3)))) ((+1) : ((+2) : {}(+3)))
diff --git a/std/Math.bruijn b/std/Math.bruijn
index 58da709..62d04e0 100644
--- a/std/Math.bruijn
+++ b/std/Math.bruijn
@@ -12,6 +12,13 @@ sum foldl add (+0) ⧗ (List Number) → Number
 
 :test (∑((+1) : ((+2) : {}(+3)))) ((+6))
 
+# digit sum of all values
+digit-sum sum ∘ number→list ⧗ Number → Number
+
+:test ((digit-sum (+0)) =? (+0)) (true)
+:test ((digit-sum (+10)) =? (+1)) (true)
+:test ((digit-sum (+19)) =? (+10)) (true)
+
 # returns max value of list
 lmax foldl1 max ⧗ (List Number) → Number
 
@@ -22,14 +29,6 @@ lmin foldl1 min ⧗ (List Number) → Number
 
 :test (lmin ((+2) : ((+1) : {}(+0)))) ((+0))
 
-# converts number to list of its digits
-digits z [[rec]] ⧗ Number → (List Number)
-	rec =?0 case-end case-rec
-		case-rec (1 (0 / (+10))) ; (0 % (+10))
-		case-end empty
-
-:test (digits (+0)) (empty)
-
 # list from num to num
 {…→…} z [[[rec]]] ⧗ Number → Number → (List Number)
 	rec (1 =? ++0) case-end case-list
diff --git a/std/Number.bruijn b/std/Number.bruijn
index f74b7d4..b2f3631 100644
--- a/std/Number.bruijn
+++ b/std/Number.bruijn
@@ -8,9 +8,16 @@
 
 # the following functions are only here because of recursive imports of list/ternary
 
-# converts a list of digits into a balanced ternary number
-from-digits foldl [[(+10) ⋅ 1 + 0]] (+0)
+# converts number to list of its digits
+number→list [=?0 {}(+0) (z [[rec]] 0)] ⧗ Number → (List Number)
+	rec =?0 case-end case-rec
+		case-rec (1 (0 / (+10))) ; (0 % (+10))
+		case-end empty
+
+:test (number→list (+0)) ({}(+0))
 
-:test (from-digits ((+4) : ((+2) : {}(+0)))) ((+420))
-:test (from-digits empty) ((+0))
+# converts a list of digits into a balanced ternary number
+list→number foldl [[(+10) ⋅ 1 + 0]] (+0) ⧗ (List Number) → Number
 
+:test (list→number ((+4) : ((+2) : {}(+0)))) ((+420))
+:test (list→number empty) ((+0))
diff --git a/std/Number/Binary.bruijn b/std/Number/Binary.bruijn
index a056538..77ce09c 100644
--- a/std/Number/Binary.bruijn
+++ b/std/Number/Binary.bruijn
@@ -163,6 +163,9 @@ not-eq? not! ∘∘ eq? ⧗ Binary → Binary → Boolean
 :test ([[[1 (0 2)]]] ≠? [[[1 (0 2)]]]) (false)
 :test ([[[1 (0 2)]]] ≠? (+2b)) (true)
 
+# prefix for comparing functions
+?‣ &eq?
+
 # adds 1 to a binary number (can introduce leading 0s)
 inc [~(0 z a¹ a⁰)] ⧗ Binary → Binary
 	z (+0b) : (+1b)
@@ -196,7 +199,7 @@ complement [[[[3 2 0 1]]]] ⧗ Binary → Binary
 :test (-*(+42b)) ([[[1 (0 (1 (0 (1 (0 2)))))]]])
 
 # inverts a binary number by complementing and incrementing (2's complement)
-# don't forget to pad the number with zeroes if needed
+# don't forget to pad the number with 0s if needed
 invert ++‣ ∘ -*‣ ⧗ Binary → Binary
 
 -‣ invert
@@ -204,9 +207,9 @@ invert ++‣ ∘ -*‣ ⧗ Binary → Binary
 :test (-(+0b)) ((+1b))
 :test (-(+1b)) ((+1b))
 
-# pads a binary number with zeroes until its as long a another binary number
-# TODO: this could probably be done without list magic
-pad [[binary! (pad-right ∀(list! %1) b⁰ (list! 0))]] ⧗ Binary → Binary → Binary
+# pads a binary number with 0s until it's as long a another binary number
+# TODO: this could be done without list magic (see Ternary)
+pad [[binary! (pad-right ∀(list! %1) b⁰ (list! %0))]] ⧗ Binary → Binary → Binary
 
 :test (pad (+5b) [[[1 2]]]) ([[[1 (0 (0 2))]]])
 
@@ -248,7 +251,7 @@ sub* [[abs 1 →^0]] ⧗ Binary → Binary → Binary
 # subs two binary numbers
 # uses addition but with two's complement
 # TODO: isn't very performant ⇒ replace with sub*
-# TODO: gives wrong results if b>a in a-b
+# TODO: gives fun results if b>a in a-b
 sub [[(0 =? 1) (+0b) -((pad 1 0) + -(pad 0 1))]] ⧗ Binary → Binary → Binary
 
 …-… sub
@@ -279,6 +282,20 @@ div² [~(0 z a¹ a⁰)] ⧗ Binary → Binary
 :test (/²(+6b) =? (+3b)) (true)
 :test (/²(+5b) =? (+2b)) (true)
 
+# ceiled integer log2 by counting bits
+# also counts leading 0s
+log2* [0 (+0b) inc inc] ⧗ Binary → Binary
+
+# ceiled integer log2 by counting bits
+log2 log2* ∘ strip ⧗ Binary → Binary
+
+:test ((log2 (+1b)) =? (+1b)) (true)
+:test ((log2 (+2b)) =? (+2b)) (true)
+:test ((log2 (+3b)) =? (+2b)) (true)
+:test ((log2 (+4b)) =? (+3b)) (true)
+:test ((log2 (+32b)) =? (+6b)) (true)
+:test ((log2 (+48b)) =? (+6b)) (true)
+
 # returns true if the number is even (remainder mod 2 == 0)
 even? ¬‣ ∘ lsb ⧗ Binary → Boolean
 
diff --git a/std/Number/Conversion.bruijn b/std/Number/Conversion.bruijn
index 0057310..52f3c9e 100644
--- a/std/Number/Conversion.bruijn
+++ b/std/Number/Conversion.bruijn
@@ -9,14 +9,18 @@
 # converts unary numbers to ternary
 unary→ternary [0 T.inc (+0t)] ⧗ Unary → Ternary
 
-:test (unary→ternary (+0u)) ((+0t))
-:test (unary→ternary (+2u)) ((+2t))
+¹³‣ unary→ternary
+
+:test (¹³(+0u)) ((+0t))
+:test (¹³(+2u)) ((+2t))
 
 # converts ternary numbers to unary
 ternary→unary [T.apply 0 U.inc (+0u)] ⧗ Ternary → Unary
 
-:test (ternary→unary (+0t)) ((+0u))
-:test (ternary→unary (+2t)) ((+2u))
+³¹‣ ternary→unary
+
+:test (³¹(+0t)) ((+0u))
+:test (³¹(+2t)) ((+2u))
 
 # converts binary numbers to ternary
 # constructs reversed path of composed functions and applies to ternary
@@ -25,8 +29,10 @@ binary→ternary [y [[[rec]]] [0] 0 (+0t)] ⧗ Binary → Ternary
 		case-rec B.odd? 0 (2 (1 ∘ T.inc) (B.dec 0)) (2 (1 ∘ (T.mul (+2t))) (B.div² 0))
 		case-end 1
 
-:test (T.eq? (binary→ternary (+0b)) (+0t)) ([[1]])
-:test (T.eq? (binary→ternary (+42b)) (+42t)) ([[1]])
+²³‣ binary→ternary
+
+:test (T.eq? ²³(+0b) (+0t)) ([[1]])
+:test (T.eq? ²³(+42b) (+42t)) ([[1]])
 
 # converts numbers to binary
 # constructs reversed path of composed functions and applies to ternary
@@ -35,5 +41,7 @@ ternary→binary [y [[[rec]]] [0] 0 (+0b)] ⧗ Ternary → Binary
 		case-rec T.odd? 0 (2 (1 ∘ B.inc) (T.dec 0)) (2 (1 ∘ (B.mul (+2b))) (T.div² 0))
 		case-end 1
 
-:test (B.eq? (ternary→binary (+0t)) (+0b)) ([[1]])
-:test (B.eq? (ternary→binary (+42t)) (+42b)) ([[1]])
+³²‣ ternary→binary
+
+:test (B.eq? ³²(+0t) (+0b)) ([[1]])
+:test (B.eq? ³²(+42t) (+42b)) ([[1]])
diff --git a/std/Number/Ternary.bruijn b/std/Number/Ternary.bruijn
index 20a89e8..86f4593 100644
--- a/std/Number/Ternary.bruijn
+++ b/std/Number/Ternary.bruijn
@@ -1,5 +1,5 @@
 # MIT License, Copyright (c) 2022 Marvin Borner
-# ternary implementation of T.Æ. Mogensen and Douglas W. Jones (see refs in README)
+# inspiration from T.Æ. Mogensen and Douglas W. Jones (see refs in README)
 # → refer to std/Math for more advanced functions
 
 :import std/Box B
@@ -65,6 +65,9 @@ t⁰? [0 false false true] ⧗ Trit → Boolean
 :test (t⁺ ↑ (+42)) (↑⁺(+42))
 :test (t⁰ ↑ (+42)) (↑⁰(+42))
 
+# lshifts a zero trit into a balanced ternary number
+←⁰‣ [[[[[4 (0 3) 2 1 0]]]]]
+
 # infinity
 # WARNING: using this mostly results in undefined behavior! (TODO?)
 infty z [[[[[1 (4 1)]]]]] ⧗ Number
@@ -129,6 +132,20 @@ lst [0 t⁰ [t⁻] [t⁺] [t⁰]] ⧗ Number → Trit
 :test (lst (+42)) (t⁰)
 
 # extracts most significant trit from a balanced ternary number
+mst* [B.get t⁰ (0 z a⁻ a⁺ a⁰)] ⧗ Number → Trit
+	z B.empty
+	a⁻ [B.store! 0 t⁻]
+	a⁺ [B.store! 0 t⁺]
+	a⁰ [B.store! 0 t⁰]
+
+:test (mst* (-1)) (t⁻)
+:test (mst* (+0)) (t⁰)
+:test (mst* (+1)) (t⁺)
+:test (mst* (+42)) (t⁺)
+:test (mst* [[[[(0 (1 (0 3)))]]]]) (t⁰)
+
+# extracts most significant trit from a balanced ternary number
+# ignores leading 0s
 mst [B.get t⁰ (0 z a⁻ a⁺ a⁰)] ⧗ Number → Trit
 	z B.empty
 	a⁻ [B.store! 0 t⁻]
@@ -215,6 +232,9 @@ not-eq? not! ∘∘ eq? ⧗ Number → Number → Boolean
 :test ((+1) ≠? (+0)) (true)
 :test ((-42) ≠? (+42)) (true)
 
+# prefix for comparing functions
+?‣ &eq?
+
 # adds (+1) to a balanced ternary number (can introduce leading 0s)
 inc [~(0 z a⁻ a⁺ a⁰)] ⧗ Number → Number
 	z (+0) : (+1)
@@ -339,6 +359,23 @@ abs [<?0 -0 0] ⧗ Number → Number
 :test (|(-1)) ((+1))
 :test (|(+42)) ((+42))
 
+# returns max number of two
+max [[(1 ≤? 0) 0 1]] ⧗ Number → Number → Number
+
+:test (max (+5) (+2)) ((+5))
+
+# returns min number of two
+min [[(1 ≤? 0) 1 0]] ⧗ Number → Number → Number
+
+:test (min (+5) (+2)) ((+2))
+
+# clamps a number between two numbers
+clamp [[[min 1 (max 0 2)]]] ⧗ Number → Number → Number
+
+:test (clamp (+0) (+5) (+3)) ((+3))
+:test (clamp (+0) (+5) (-2)) ((+0))
+:test (clamp (+0) (+5) (+7)) ((+5))
+
 # apply a function n times to a value
 # ~> substitute church numbers
 apply z [[[rec]]] ⧗ Number → (a → a) → a → a
@@ -396,6 +433,17 @@ div² [z [[[[rec]]]] (+0) 0 0] ⧗ Number → Number
 :test (/³*(-6) =? (-2)) (true)
 :test (/³*(+5) =? (+1)) (true)
 
+# ceiled integer log3 by counting number of trits
+# also counts leading 0s
+log3* [0 (+0) inc inc inc] ⧗ Number → Number
+
+# ceiled integer log3 by counting number of trits
+log3 log3* ∘ strip ⧗ Number → Number
+
+:test (log3 (+0)) ((+0))
+:test (log3 (+5)) ((+3))
+:test (log3 (+42)) ((+5))
+
 # returns the smallest number in a range such that a predicate is true
 binary-search z [[[[rec]]]] ⧗ (Number → Boolean) → Number → Number → Number
 	rec (0 =? 1) case-end case-search
@@ -417,10 +465,29 @@ ternary-search z [[[[rec]]]] ⧗ (Number → Number) → Number → Number → N
 
 # finds quotient and remainder using binary search
 # TODO: fix for numbers <=1 (case analysis, q,r<0)
-# TODO: faster algorithm
 quot-rem [[go --(binary-search [0 ⋅ 1 >? 2] (+0) 1)]] ⧗ Number → Number → (Pair Number Number)
 	go [0 : (2 - (1 ⋅ 0))]
 
+# pads a ternary number with 0s until it's as long a another ternary number
+pad y [[[(log3* 0) <? (log3* 1) (2 1 ←⁰0) 0]]] ⧗ Number → Number → Number
+
+# forces number to be exactly n trits long (either pad/trim)
+force [[[0 <? 2 pad trim] (log3* 0)]] ⧗ Number → Number
+	pad y [[[=?1 0 (2 --1 ←⁰0)]]] (2 - 0) 1
+	trim y [[[=?1 0 (2 --1 /³0)]]] (0 - 2) 1
+
+# technique by Douglas W. Jones
+# TODO: fix
+quot-rem* [[[[z [[[[rec]]]] 1 (+0) 3]] ((max (log3 1) (log3 0)) ⋅ (+2)) 0]]
+	rec =?2 (0 : 1) ([[compare-case eq lt gt 1 (+0)]] rem' quo')
+		rem' force 5 ((mst* (force 5 0)) ↑ (+0) + ↑⁰1)
+		quo' force 5 ↑⁰0
+		eq 5 --4 1 0
+		lt [(-0 >? 2) ⋁? ((-0 =? 2) ⋀? <?1) fix (6 --5 2 1)] (force 7 (1 + 6))
+			fix 6 --5 0 --1
+		gt [(-0 <? 2) ⋁? ((-0 =? 2) ⋀? >?1) fix (6 --5 2 1)] (force 7 (1 - 6))
+			fix 6 --5 0 ++1
+
 # divs two balanced ternary numbers
 div ^‣ ∘∘ quot-rem ⧗ Number → Number
 
@@ -461,20 +528,3 @@ odd? ¬‣ ∘ even? ⧗ Number → Boolean
 :test (≠²?(+1)) (true)
 :test (≠²?(+41)) (true)
 :test (≠²?(+42)) (false)
-
-# returns max number of two
-max [[(1 ≤? 0) 0 1]] ⧗ Number → Number → Number
-
-:test (max (+5) (+2)) ((+5))
-
-# returns min number of two
-min [[(1 ≤? 0) 1 0]] ⧗ Number → Number → Number
-
-:test (min (+5) (+2)) ((+2))
-
-# clamps a number between two numbers
-clamp [[[min 1 (max 0 2)]]] ⧗ Number → Number → Number
-
-:test (clamp (+0) (+5) (+3)) ((+3))
-:test (clamp (+0) (+5) (-2)) ((+0))
-:test (clamp (+0) (+5) (+7)) ((+5))
diff --git a/std/Number/Unary.bruijn b/std/Number/Unary.bruijn
index 0c65c41..81af007 100644
--- a/std/Number/Unary.bruijn
+++ b/std/Number/Unary.bruijn
@@ -119,6 +119,9 @@ not-eq? not! ∘∘ eq? ⧗ Unary → Unary → Boolean
 :test ((+1u) ≠? (+1u)) (false)
 :test ((+42u) ≠? (+42u)) (false)
 
+# prefix for comparing functions
+?‣ &eq?
+
 # returns eq, lt, gt depending on comparison of two numbers
 compare-case [[[[[go (1 - 0) (0 - 1)]]]]] ⧗ a → b → c → Unary → Unary → d
 	go [[=?0 (=?1 6 5) 4]]
diff --git a/std/String.bruijn b/std/String.bruijn
index 5af9574..645eda3 100644
--- a/std/String.bruijn
+++ b/std/String.bruijn
@@ -14,8 +14,11 @@ eq? eq? B.eq? ⧗ String → String → Boolean
 :test ("ab" =? "ab") (true)
 :test ("ab" =? "aa") (false)
 
+# prefix for comparing functions
+?‣ &eq?
+
 # returns true if character is part of a string
-in? in? B.eq? ⧗ Char → String → Boolean
+in? B.?in? ⧗ Char → String → Boolean
 
 …∈… in?
 
@@ -29,7 +32,7 @@ ni? \in? ⧗ String → Char → Boolean
 :test ("ab" ∋ 'c') (false)
 
 # converts a string of digits into a number
-string→unsigned-number from-digits ∘ (map C.char→number) ⧗ String → Number
+string→unsigned-number list→number ∘ (map C.char→number) ⧗ String → Number
 
 :test (%(string→unsigned-number "123")) ((+123))
 
@@ -50,7 +53,7 @@ string→number [C.les? ^0 '0' signed unsigned] ⧗ String → Number
 :test (%(string→number "-123")) ((-123))
 
 # converts a number to a string
-number→string (map C.number→char) ∘ digits ⧗ Number → String
+number→string (map C.number→char) ∘ number→list ⧗ Number → String
 
 :test (number→string (+123)) ("123")