More functions

4 files changed, 123 insertions, 73 deletions

diff --git a/std/Combinator.bruijn b/std/Combinator.bruijn
index ceb9c48..34f9631 100644
--- a/std/Combinator.bruijn
+++ b/std/Combinator.bruijn
@@ -7,20 +7,20 @@ a [[1 0]]
 
 …$… a
 
-# bluebird combinator: function composition: (f . g) x = f (g x)
+# bluebird combinator: function composition: (f ∘ g) x = f (g x)
 b [[[2 (1 0)]]]
 
-….… b
+…∘… b
 
-# blackbird combinator: 2x function composition: (f .. g) x y = f (g x y)
+# blackbird combinator: 2x function composition: (f ∘∘ g) x y = f (g x y)
 b' [[[[3 (2 1 0)]]]]
 
-…..… b'
+…∘∘… b'
 
-# bunting combinator: 3x function composition: (f ... g) x y z = f (g x y z)
+# bunting combinator: 3x function composition: (f ∘∘∘ g) x y z = f (g x y z)
 b'' [[[[[4 (3 2 1 0)]]]]]
 
-…...… b''
+…∘∘∘… b''
 
 # becard combinator
 b''' [[[[3 (2 (1 0))]]]]
diff --git a/std/List.bruijn b/std/List.bruijn
index 297f882..02d55a7 100644
--- a/std/List.bruijn
+++ b/std/List.bruijn
@@ -68,8 +68,8 @@ foldl z [[[[rec]]]]
 		case-fold 3 2 (2 1 ^0) ~0
 		case-end 1
 
-:test ((foldl add (+0) ((+1) : ((+2) : ((+3) : empty)))) =? (+6)) (true)
-:test ((foldl sub (+6) ((+1) : ((+2) : ((+3) : empty)))) =? (+0)) (true)
+:test ((foldl …+… (+0) ((+1) : ((+2) : ((+3) : empty)))) =? (+6)) (true)
+:test ((foldl …-… (+6) ((+1) : ((+2) : ((+3) : empty)))) =? (+0)) (true)
 
 # foldl without starting value
 foldl1 [[foldl 1 ^0 ~0]]
@@ -80,8 +80,8 @@ foldr [[[z [[rec]] 0]]]
 		case-fold 4 ^0 (1 ~0)
 		case-end 3
 
-:test ((foldr add (+0) ((+1) : ((+2) : ((+3) : empty)))) =? (+6)) (true)
-:test ((foldr sub (+2) ((+1) : ((+2) : ((+3) : empty)))) =? (+0)) (true)
+:test ((foldr …+… (+0) ((+1) : ((+2) : ((+3) : empty)))) =? (+6)) (true)
+:test ((foldr …-… (+2) ((+1) : ((+2) : ((+3) : empty)))) =? (+0)) (true)
 
 # foldr without starting value
 foldr1 [[foldl 1 ^0 ~0]]
@@ -104,30 +104,6 @@ land? foldr and? true
 :test (⋀?(true : (false : empty))) (false)
 :test (⋀?(false : (false : empty))) (false)
 
-# multiplies all values in list
-product foldl mul (+1)
-
-Π product
-
-:test (Π ((+1) : ((+2) : ((+3) : empty)))) ((+6))
-
-# adds all values in list
-sum foldl add (+0)
-
-Σ sum
-
-:test (Σ ((+1) : ((+2) : ((+3) : empty)))) ((+6))
-
-# returns max value of list
-lmax foldl1 max
-
-:test (lmax ((+1) : ((+3) : ((+2) : empty)))) ((+3))
-
-# returns min value of list
-lmin foldl1 min
-
-:test (lmin ((+2) : ((+1) : ((+0) : empty)))) ((+0))
-
 # reverses a list
 reverse foldl \cons empty
 
@@ -139,6 +115,13 @@ reverse foldl \cons empty
 # TODO: fix for balanced ternary
 list [0 [[[2 (0 : 1)]]] reverse empty]
 
+# creates list with single element
+singleton [0 : empty]
+
+{…} singleton
+
+:test ({ (+1) }) ((+1) : empty)
+
 # appends two lists
 append z [[[rec]]]
 	rec <>?1 case-end case-append
@@ -150,7 +133,7 @@ append z [[[rec]]]
 :test (((+1) : ((+2) : ((+3) : empty))) ++ ((+4) : empty)) ((+1) : ((+2) : ((+3) : ((+4) : empty))))
 
 # appends an element to a list
-snoc [[1 ++ (0 : empty)]]
+snoc [[1 ++ ({ 0 })]]
 
 …;… snoc
 
@@ -165,7 +148,7 @@ map z [[[rec]]]
 
 …<$>… map
 
-:test (inc <$> ((+1) : ((+2) : ((+3) : empty)))) ((+2) : ((+3) : ((+4) : empty)))
+:test (++‣ <$> ((+1) : ((+2) : ((+3) : empty)))) ((+2) : ((+3) : ((+4) : empty)))
 
 # filters a list based on a predicate
 filter z [[[rec]]]
@@ -204,7 +187,7 @@ concat foldr append empty
 :test (concat ("a" : ("b" : empty))) ("ab")
 
 # maps a function returning list of list and concatenates
-concat-map [foldr (append . 0) empty]
+concat-map concat ∘∘ map
 
 :test (concat-map [-0 : (0 : empty)] ((+1) : ((+2) : empty))) ((-1) : ((+1) : ((-2) : ((+2) : empty))))
 
@@ -222,7 +205,17 @@ zip-with z [[[[rec]]]]
 		case-zip <>?0 empty ((2 ^1 ^0) : (3 2 ~1 ~0))
 		case-end empty
 
-:test (zip-with add ((+1) : ((+2) : empty)) ((+2) : ((+1) : empty))) ((+3) : ((+3) : empty))
+:test (zip-with …+… ((+1) : ((+2) : empty)) ((+2) : ((+1) : empty))) ((+3) : ((+3) : empty))
+
+# list comprehension
+{…|…} map
+
+:test ({ ++‣ | ((+0) : ((+2) : empty)) }) ((+1) : ((+3) : empty))
+
+# doubled list comprehension
+{…|…,…} zip-with
+
+:test ({ …+… | ((+0) : ((+2) : empty)) , ((+1) : ((+3) : empty)) }) ((+1) : ((+5) : empty))
 
 # returns first n elements of a list
 take z [[[rec]]]
@@ -266,30 +259,30 @@ span z [[[rec]]]
 :test (span (\les? (+3)) ((+1) : ((+2) : ((+4) : ((+1) : empty))))) (((+1) : ((+2) : empty)) : ((+4) : ((+1) : empty)))
 
 # same as span but with inverted predicate
-break [span (not! . 0)]
+break span ∘ (…∘… ¬‣)
 
 :test (break (\gre? (+3)) ((+1) : ((+2) : ((+4) : ((+1) : empty))))) (((+1) : ((+2) : empty)) : ((+4) : ((+1) : empty)))
 
 # returns true if any element in a list matches a predicate
-any? [⋁?‣ . (map 0)]
+any? ⋁?‣ ∘∘ map
 
 :test (any? (\gre? (+2)) ((+1) : ((+2) : ((+3) : empty)))) (true)
 :test (any? (\gre? (+2)) ((+1) : ((+2) : ((+2) : empty)))) (false)
 
 # returns true if all elements in a list match a predicate
-all? [⋀?‣ . (map 0)]
+all? ⋀?‣ ∘∘ map
 
 :test (all? (\gre? (+2)) ((+3) : ((+4) : ((+5) : empty)))) (true)
 :test (all? (\gre? (+2)) ((+4) : ((+3) : ((+2) : empty)))) (false)
 
 # returns true if element is part of a list based on eq predicate
-in? [[any? (\1 0)]]
+in? …∘… any?
 
 :test (in? …=?… (+3) ((+1) : ((+2) : ((+3) : empty)))) (true)
 :test (in? …=?… (+0) ((+1) : ((+2) : ((+3) : empty)))) (false)
 
 # returns true if all elements of one list are equal to corresponding elements of other list
-eq? ⋀?‣ ... zip-with
+eq? ⋀?‣ ∘∘∘ zip-with
 
 :test (eq? …=?… ((+1) : ((+2) : empty)) ((+1) : ((+2) : empty))) (true)
 :test (eq? …=?… ((+1) : ((+2) : empty)) ((+2) : ((+2) : empty))) (false)
@@ -333,7 +326,7 @@ cycle z [[rec]]
 iterate z [[[rec]]]
 	rec 0 : (2 1 (1 0))
 
-:test (take (+5) (iterate inc (+0))) (((+0) : ((+1) : ((+2) : ((+3) : ((+4) : empty))))))
+:test (take (+5) (iterate ++‣ (+0))) (((+0) : ((+1) : ((+2) : ((+3) : ((+4) : empty))))))
 :test (take (+2) (iterate sdec (+5))) (((+5) : ((+4) : empty)))
 :test (take (+5) (iterate i (+4))) (take (+5) (repeat (+4)))
-:test (take (+0) (iterate inc (+0))) (empty)
+:test (take (+0) (iterate ++‣ (+0))) (empty)
diff --git a/std/Math.bruijn b/std/Math.bruijn
index ea2bf71..9d3dff2 100644
--- a/std/Math.bruijn
+++ b/std/Math.bruijn
@@ -4,6 +4,54 @@
 
 :input std/Number .
 
+# adds all values in list
+sum foldl add (+0)
+
+∑‣ sum
+
+:test (∑((+1) : ((+2) : ((+3) : empty)))) ((+6))
+
+# returns max value of list
+lmax foldl1 max
+
+:test (lmax ((+1) : ((+3) : ((+2) : empty)))) ((+3))
+
+# returns min value of list
+lmin foldl1 min
+
+:test (lmin ((+2) : ((+1) : ((+0) : empty)))) ((+0))
+
+# list from num to num
+{…→…} z [[[rec]]]
+	rec (1 =? ++0) case-end case-list
+		case-list 1 : (2 ++1 0)
+		case-end empty
+
+:test ({ (+0) → (+2) }) ((+0) : ((+1) : ((+2) : empty)))
+
+# equivalent of mathematical sum function
+∑…→…|… z [[[[[rec]]]]] (+0)
+	rec (2 =? ++1) case-end case-sum
+		case-sum 4 (3 + (0 2)) ++2 1 0
+		case-end 3
+
+:test (∑ (+1) → (+3) | ++‣) ((+9))
+
+# multiplies all values in list
+product foldl mul (+1)
+
+Π product
+
+:test (Π ((+1) : ((+2) : ((+3) : empty)))) ((+6))
+
+# equivalent of mathematical product function
+∏…→…|… z [[[[[rec]]]]] (+1)
+	rec (2 =? ++1) case-end case-sum
+		case-sum 4 (3 * (0 2)) ++2 1 0
+		case-end 3
+
+:test (∏ (+1) → (+3) | ++‣) ((+24))
+
 # greatest common divisor
 gcd z [[[(1 =? 0) case-eq ((1 >? 0) case-gre case-les)]]]
 	case-eq 1
@@ -22,13 +70,13 @@ pow […!!… (iterate (…*… 0) (+1))]
 :test (((+2) ** (+3)) =? ((+8))) (true)
 
 # factorial function
-# fac Z [[(0 <? (+2)) (+1) (0 * (1 --0))]]
-fac [Π (take 0 (iterate ++‣ (+1)))]
+# TODO: faster fac?
+fac [∏ (+1) → 0 | i]
 
 :test ((fac (+3)) =? (+6)) (true)
 
 # fibonacci sequence
-# fibs Z [(+1) : ((+1) : (zip-with (+) 0 ~0))]
+# TODO: faster fib?
 fibs fst <$> (iterate [~0 : (^0 + ~0)] ((+0) : (+1)))
 
 fib [fibs !! ++0]
diff --git a/std/Number.bruijn b/std/Number.bruijn
index 812a5c4..f6aba7d 100644
--- a/std/Number.bruijn
+++ b/std/Number.bruijn
@@ -70,6 +70,12 @@ down [~(0 z a⁻ a⁺ a⁰)]
 	a⁺ [0 [[↑⁺1 : 1]]]
 	a⁰ [0 [[↑⁰1 : 1]]]
 
+# infinity
+# WARNING: using this mostly results in undefined behavior! (TODO?)
+infty z [[[[[1 (4 1)]]]]]
+
+∞ infty
+
 # negates a balanced ternary number
 negate [[[[[4 3 1 2 0]]]]]
 
@@ -152,6 +158,7 @@ zero? [0 true [false] [false] i]
 :test (=?(+42)) (false)
 
 # converts the normal balanced ternary representation into abstract
+# infinity can't be abstracted in finite time
 # → the abstract representation is used in eq?/add/sub/mul
 abstract! [0 z a⁻ a⁺ a⁰]
 	z (+0)
@@ -166,9 +173,11 @@ abstract! [0 z a⁻ a⁺ a⁰]
 :test (→^(+3)) ([[[[0 [[[[1 [[[[3]]]]]]]]]]]])
 
 # converts the abstracted balanced ternary representation back to normal
-# using ω to solve recursion
-normal! ω rec
-	rec [[0 (+0) [↑⁻([3 3 0] 0)] [↑⁺([3 3 0] 0)] [↑⁰([3 3 0] 0)]]]
+normal! ω [[0 z a⁻ a⁺ a⁰]]
+	z (+0)
+	a⁻ [↑⁻([3 3 0] 0)]
+	a⁺ [↑⁺([3 3 0] 0)]
+	a⁰ [↑⁰([3 3 0] 0)]
 
 →_‣ normal!
 
@@ -188,7 +197,7 @@ eq? [[abs 1 →^0]]
 
 …=?… eq?
 
-…/=?… not! .. eq?
+…/=?… not! ∘∘ eq?
 
 :test ((-42) =? (-42)) (true)
 :test ((-1) =? (-1)) (true)
@@ -216,7 +225,7 @@ inc [~(0 z a⁻ a⁺ a⁰)]
 ++‣ inc
 
 # adds (+1) to a balanced ternary number and strips leading 0s
-ssinc strip . inc
+ssinc strip ∘ inc
 
 :test ((++(-42)) =? (-41)) (true)
 :test ((++(-1)) =? (+0)) (true)
@@ -234,7 +243,7 @@ dec [~(0 z a⁻ a⁺ a⁰)]
 --‣ dec
 
 # subs (+1) from a balanced ternary number and strips leading 0s
-sdec strip . dec
+sdec strip ∘ dec
 
 :test ((--(-42)) =? (-43)) (true)
 :test ((--(+0)) =? (-1)) (true)
@@ -243,7 +252,7 @@ sdec strip . dec
 :test ((--(+42)) =? (+41)) (true)
 
 # adds two balanced ternary numbers (can introduce leading 0s)
-# larger numbers should be second argument (performance)
+# second argument gets abstracted (performance)
 add [[abs 1 →^0]]
 	abs [c (0 z a⁻ a⁺ a⁰)]
 		b⁻ [1 ↑⁺(3 0 t⁻) ↑⁰(3 0 t⁰) ↑⁻(3 0 t⁰)]
@@ -260,7 +269,7 @@ add [[abs 1 →^0]]
 …+… add
 
 # adds two balanced ternary numbers and strips leading 0s
-sadd strip .. add
+sadd strip ∘∘ add
 
 :test (((-42) + (-1)) =? (-43)) (true)
 :test (((-5) + (+6)) =? (+1)) (true)
@@ -270,13 +279,13 @@ sadd strip .. add
 :test (((+42) + (+1)) =? (+43)) (true)
 
 # subs two balanced ternary numbers (can introduce leading 0s)
-# larger numbers should be second argument (performance)
+# second argument gets abstracted (performance)
 sub [[1 + -0]]
 
 …-… sub
 
 # subs two balanced ternary numbers and strips leading 0s
-ssub strip .. sub
+ssub strip ∘∘ sub
 
 :test (((-42) - (-1)) =? (-41)) (true)
 :test (((-5) - (+6)) =? (-11)) (true)
@@ -285,6 +294,21 @@ ssub strip .. sub
 :test (((+1) - (+2)) =? (-1)) (true)
 :test (((+42) - (+1)) =? (+41)) (true)
 
+# muls two balanced ternary numbers (can introduce leading 0s)
+mul [[1 (+0) a⁻ a⁺ a⁰]]
+	a⁻ [↑⁰0 - 1]
+	a⁺ [↑⁰0 + 1]
+	a⁰ [↑⁰0]
+
+…*… mul
+
+smul strip ∘∘ mul
+
+:test (((+42) * (+0)) =? (+0)) (true)
+:test (((-1) * (+42)) =? (-42)) (true)
+:test (((+3) * (+11)) =? (+33)) (true)
+:test (((+42) * (-4)) =? (-168)) (true)
+
 # returns true if number is greater than other number
 # larger numbers should be second argument (performance)
 gre? [[>?(1 - 0)]]
@@ -330,18 +354,3 @@ max [[(1 ≤? 0) 0 1]]
 
 # returns min number of two
 min [[(1 ≤? 0) 1 0]]
-
-# muls two balanced ternary numbers (can introduce leading 0s)
-mul [[1 (+0) a⁻ a⁺ a⁰]]
-	a⁻ [↑⁰0 - 1]
-	a⁺ [↑⁰0 + 1]
-	a⁰ [↑⁰0]
-
-…*… mul
-
-smul strip .. mul
-
-:test (((+42) * (+0)) =? (+0)) (true)
-:test (((-1) * (+42)) =? (-42)) (true)
-:test (((+3) * (+11)) =? (+33)) (true)
-:test (((+42) * (-4)) =? (-168)) (true)