diff options
| -rw-r--r-- | bruijn.cabal | 1 | ||||
| -rw-r--r-- | std/Char.bruijn | 2 | ||||
| -rw-r--r-- | std/List.bruijn | 52 | ||||
| -rw-r--r-- | std/Math.bruijn | 4 | ||||
| -rw-r--r-- | std/Number/Ternary.bruijn | 11 | ||||
| -rw-r--r-- | std/Set.bruijn | 20 | ||||
| -rw-r--r-- | std/String.bruijn | 9 | ||||
| -rw-r--r-- | std/Tree/Balanced.bruijn | 13 |
8 files changed, 104 insertions, 8 deletions
diff --git a/bruijn.cabal b/bruijn.cabal index ca86a9a..b3e4bf1 100644 --- a/bruijn.cabal +++ b/bruijn.cabal @@ -30,6 +30,7 @@ data-files: std/Option.bruijn std/Pair.bruijn std/Result.bruijn + std/Set.bruijn std/String.bruijn std/Number/Binary.bruijn std/Number/Ternary.bruijn diff --git a/std/Char.bruijn b/std/Char.bruijn index 8351142..cdab0bf 100644 --- a/std/Char.bruijn +++ b/std/Char.bruijn @@ -1,5 +1,5 @@ # MIT License, Copyright (c) 2023 Marvin Borner -:import std/Number/Binary . +:input std/Number/Binary . number! [ternary! (0 - '0')] ⧗ Char → Number diff --git a/std/List.bruijn b/std/List.bruijn index 3b8a242..12e85c8 100644 --- a/std/List.bruijn +++ b/std/List.bruijn @@ -1,5 +1,6 @@ # MIT License, Copyright (c) 2022 Marvin Borner # Lists in Church/Boehm-Berarducci encoding using pairs +# implementations are generally lazy (except when they're broken) # TODO: Replace fold/map/etc. with faster LC native logic :import std/Combinator . @@ -68,6 +69,14 @@ index z [[[rec]]] ⧗ (List a) → Number → a :test (((+1) : ((+2) : {}(+3))) !! (-1)) (empty) :test (((+1) : ((+2) : {}(+3))) !! (+3)) (empty) +# constructs a list of successively reduced values +scanl z [[[[1 : rec]]]] ⧗ (b → a → b) → b → (List a) → (List b) + rec ∅?0 case-end case-scan + case-scan 3 2 (2 1 ^0) ~0 + case-end 0 + +:test (scanl …+… (+0) ((+1) : ((+2) : {}(+3)))) ((+0) : ((+1) : ((+3) : {}(+6)))) + # applies a left fold on a list foldl z [[[[rec]]]] ⧗ (b → a → b) → b → (List a) → b rec ∅?0 case-end case-fold @@ -130,6 +139,9 @@ append z [[[rec]]] ⧗ (List a) → (List a) → (List a) …++… append +:test ({}(+1) ++ empty) ({}(+1)) +:test (empty ++ {}(+1)) ({}(+1)) +:test (empty ++ empty) (empty) :test (((+1) : ((+2) : {}(+3))) ++ {}(+4)) ((+1) : ((+2) : ((+3) : {}(+4)))) # appends an element to a list @@ -194,12 +206,21 @@ concat-map concat ∘∘ map ⧗ (a → (List b)) → (List a) → (List b) # zips two lists discarding excess elements zip z [[[rec]]] ⧗ (List a) → (List b) → (List (Pair a b)) - rec ∅?1 case-end case-zip - case-zip ∅?0 empty ((^1 : ^0) : (2 ~1 ~0)) + rec (∅?1 ⋁? ∅?0) case-end case-zip + case-zip (^1 : ^0) : (2 ~1 ~0) case-end empty :test (zip ((+1) : {}(+2)) ((+2) : {}(+1))) (((+1) : (+2)) : {}((+2) : (+1))) +# zips three lists discarding excess elements +# TODO: add/use triple type (list element types can be different) +zip3 z [[[[rec]]]] ⧗ (List a) → (List a) → (List a) → (List (List a)) + rec (∅?2 ⋁? ∅?1 ⋁? ∅?0) case-end case-zip + case-zip (^2 : (^1 : {}(^0))) : (3 ~2 ~1 ~0) + case-end empty + +:test (zip3 ((+1) : {}(+2)) ((+2) : {}(+1)) ((+3) : {}(+0))) (((+1) : ((+2) : {}(+3))) : {}((+2) : ((+1) : {}(+0)))) + # applies pairs of the zipped list as arguments to a function zip-with z [[[[rec]]]] ⧗ (a → b → c) → (List a) → (List b) → (List c) rec ∅?1 case-end case-zip @@ -250,6 +271,17 @@ drop-while z [[[rec]]] ⧗ (a → Boolean) → (List a) → (List a) :test (drop-while zero? ((+0) : ((+0) : {}(+1)))) ({}(+1)) +# returns all combinations of two lists +cross [[concat-map [map [1 : 0] 1] 1]] ⧗ (List a) → (List b) → (List (Pair a b)) + +:test (cross "ab" "cd") (('a' : 'c') : (('a' : 'd') : (('b' : 'c') : {}('b' : 'd')))) + +# returns all combinations of three lists +# TODO: add/use triple type (list element types can be different) +cross3 [[[concat-map [concat-map [map [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)) @@ -309,6 +341,12 @@ sort-desc z [[rec]] :test (sort-desc ((+1) : ((+2) : {}(+3)))) ((+3) : ((+2) : {}(+1))) +# inserts an element into a ascendingly sorted list +insert-sorted [go ∘ (span (\les? 0))] + go [^0 ++ (1 : ~0)] + +:test (insert-sorted (+3) ((+1) : ((+2) : {}(+4)))) ((+1) : ((+2) : ((+3) : {}(+4)))) + # returns true if any element in a list matches a predicate any? ⋁?‣ ∘∘ map ⧗ (a → Boolean) → (List a) → Boolean @@ -334,6 +372,16 @@ eq? ⋀?‣ ∘∘∘ zip-with ⧗ (a → a → Boolean) → (List a) → Boolea :test (eq? …=?… ((+1) : {}(+2)) ((+2) : {}(+2))) (false) :test (eq? …=?… empty empty) (true) +# finds the first index that matches a predicate +find-index z [[[rec]]] ⧗ (a → Boolean) → (List a) → Number + rec ∅?0 case-end case-find + case-find (1 ^0) (+0) !(2 1 ~0) + !‣ [<?0 0 ++0] + case-end (-1) + +: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 remove z [[[[rec]]]] ⧗ (a → a → Boolean) → a → (List a) → (List a) rec ∅?0 case-end case-remove diff --git a/std/Math.bruijn b/std/Math.bruijn index 772373f..6fdbc48 100644 --- a/std/Math.bruijn +++ b/std/Math.bruijn @@ -40,9 +40,9 @@ lmin foldl1 min ⧗ (List Number) → Number # multiplies all values in list product foldl mul (+1) ⧗ (List Number) → Number -Π product +∏‣ product -:test (Π ((+1) : ((+2) : {}(+3)))) ((+6)) +:test (∏((+1) : ((+2) : {}(+3)))) ((+6)) # equivalent of mathematical product function ∏…→…|… z [[[[[rec]]]]] (+1) ⧗ Number → Number → (Number → Number) → Number diff --git a/std/Number/Ternary.bruijn b/std/Number/Ternary.bruijn index d05caa0..9fb075e 100644 --- a/std/Number/Ternary.bruijn +++ b/std/Number/Ternary.bruijn @@ -322,9 +322,16 @@ geq? \leq? ⧗ Number → Number → Boolean :test ((+2) ≥? (+2)) (true) :test ((+3) ≥? (+2)) (true) +# returns eq, lt, gt depending on comparison of two functions +compare-case [[[[[go (1 - 0)]]]]] ⧗ a → b → c → Number → Number → d + go [=?0 5 (>?0 4 3)] + # returns 1 if a>b, -1 if a<b and 0 if a=b -compare [[go (1 - 0)]] ⧗ Number → Number → Number - go [=?0 (+0) (>?0 (+1) (-1))] +compare compare-case (+0) (+1) (-1) ⧗ Number → Number → Number + +:test (compare (+2) (+2)) ((+0)) +:test (compare (+2) (+1)) ((+1)) +:test (compare (+1) (+2)) ((-1)) # negates a balanced ternary number if <0 abs [<?0 -0 0] ⧗ Number → Number diff --git a/std/Set.bruijn b/std/Set.bruijn new file mode 100644 index 0000000..5f64335 --- /dev/null +++ b/std/Set.bruijn @@ -0,0 +1,20 @@ +# MIT License, Copyright (c) 2023 Marvin Borner +# Set implementation using AVL trees +# can currently only store Numbers (due to std/Tree/Balanced) + +:import std/Tree/Balanced T + +# empty set +empty T.empty ⧗ Set + +# adds a number of a set +add T.insert ⧗ Number → Set → Set + +# returns true if a number is in a set +has? T.has? ⧗ Number → Set → Boolean + +# converts a set to a list +list! T.list! ⧗ Set → (List Number) + +# converts a list to a set +from-list T.from-list ⧗ (List Number) → Set diff --git a/std/String.bruijn b/std/String.bruijn index e06cd1a..955a752 100644 --- a/std/String.bruijn +++ b/std/String.bruijn @@ -31,7 +31,14 @@ ni? \in? ⧗ String → Char → Boolean # converts a string of digits into a number number! from-digits ∘ (map C.number!) ⧗ String → Number -:test ((number! "123") =? (+123)) (true) +:test (%(number! "123")) ((+123)) + +# converts a signed string of digits into a number +signed-number! [(sign ^0) (number! ~0)] ⧗ String → Number + sign [(B.eq? 0 '-') -‣ i] + +:test (%(signed-number! "+123")) ((+123)) +:test (%(signed-number! "-123")) ((-123)) # splits string by newline character lines z [[rec]] ⧗ String → (List String) diff --git a/std/Tree/Balanced.bruijn b/std/Tree/Balanced.bruijn index fe4a155..ab0a921 100644 --- a/std/Tree/Balanced.bruijn +++ b/std/Tree/Balanced.bruijn @@ -5,6 +5,7 @@ :import std/Combinator . :import std/List L +:import std/Logic . :import std/Number . :import std/Option . :import std/Pair . @@ -82,13 +83,25 @@ insert z [[[rec]]] ⧗ Number → (Option BalancedTree) → (Option BalancedTree lt some (node (2 1 //(!0)) ?(!0) \\(!0)) gt some (node //(!0) ?(!0) (2 1 \\(!0))) +# returns true if a number is in a tree +has? z [[[rec]]] ⧗ Number → (Option BalancedTree) → Boolean + rec none? 0 false (u 1 ?(!0)) + u compare-case eq lt gt + eq true + lt 2 1 //(!0) + gt 2 1 \\(!0) + +:test (has? (+42) empty) (false) + # number of elements in tree (slow) size z [[rec]] ⧗ (Option BalancedTree) → Number rec none? 0 case-empty case-full case-full (1 //(!0)) + (1 \\(!0)) + (+1) case-empty (+0) +# converts a tree to a list list! z [[map-or L.empty go 0]] ⧗ (Option BalancedTree) → (List Number) go [L.append (L.append (2 //0) L.{}(?0)) (2 \\0)] +# converts a list to a tree from-list L.foldr insert empty ⧗ (List Number) → (Option BalancedTree) |