diff options
| -rw-r--r-- | bruijn.cabal | 2 | ||||
| -rw-r--r-- | std/List/Church.bruijn | 10 | ||||
| -rw-r--r-- | std/Number/Binary.bruijn | 2 | ||||
| -rw-r--r-- | std/Number/Ternary.bruijn | 2 | ||||
| -rw-r--r-- | std/Number/Unary.bruijn | 2 | ||||
| -rw-r--r-- | std/Set.bruijn | 18 | ||||
| -rw-r--r-- | std/Set/NumberSet.bruijn | 22 | ||||
| -rw-r--r-- | std/Set/StringSet.bruijn | 23 | ||||
| -rw-r--r-- | std/String.bruijn | 8 | ||||
| -rw-r--r-- | std/Tree/Balanced.bruijn | 17 |
10 files changed, 77 insertions, 29 deletions
diff --git a/bruijn.cabal b/bruijn.cabal index 0938354..20cd3cd 100644 --- a/bruijn.cabal +++ b/bruijn.cabal @@ -58,6 +58,8 @@ data-files: std/Number/Ternary.bruijn std/Number/Unary.bruijn std/Number/Wadsworth.bruijn + std/Set/NumberSet.bruijn + std/Set/StringSet.bruijn std/Tree/Balanced.bruijn std/Tree/Finger.bruijn std/Tree/Rose.bruijn diff --git a/std/List/Church.bruijn b/std/List/Church.bruijn index c8d5d29..b48e7c8 100644 --- a/std/List/Church.bruijn +++ b/std/List/Church.bruijn @@ -421,13 +421,15 @@ eq? ⋀?‣ ∘∘∘ zip-with ⧗ (a → a → Boolean) → (List a) → Boolea :test (eq? …=?… empty empty) (true) # returns eq, lt, gt depending on comparison of two lists and comparison function -compare-case z [[[[[[[rec]]]]]]] ⧗ (a → a → Boolean) → c → d → e → (List a) → (List a) → Boolean - rec ∅?1 (∅?0 4 3) (∅?0 2 go) - go [=?0 (7 6 5 4 3 ~2 ~1) 0] (5 ^1 ^0) +compare-case' z [[[[[[[rec]]]]]]] ⧗ Compare → a → b → c → (List a) → (List a) → d + rec ∅?1 (∅?0 4 2) (∅?0 3 (5 eq gt lt ^1 ^0)) + eq 6 5 4 3 2 ~1 ~0 + gt 3 + lt 2 # returns 1 if a>b, -1 if a<b and 0 if a=b # also: spaceship operator -compare [compare-case 0 (+0) (+1) (-1)] ⧗ (a → a → Boolean) → Binary → Binary → Number +compare' [compare-case' 0 (+0) (+1) (-1)] ⧗ Compare → Binary → Binary → Number # returns true if list is prefix of other list prefix? z [[[[rec]]]] ⧗ (a → a → Boolean) → (List a) → (List a) → Boolean diff --git a/std/Number/Binary.bruijn b/std/Number/Binary.bruijn index 87f7312..c778890 100644 --- a/std/Number/Binary.bruijn +++ b/std/Number/Binary.bruijn @@ -139,6 +139,8 @@ binary→ternary [y [[[rec]]] [0] 0 (+0t)] ⧗ Binary → Ternary # TODO: remove ternary conversion compare-case [[[(T.compare-case 2 1 0) ⋔ binary→ternary]]] ⧗ a → b → c → Binary → Binary → d +<?>‣ &compare-case + # returns true if number is greater than other number # TODO: remove ternary conversion gt? T.gt? ⋔ binary→ternary ⧗ Binary → Binary → Boolean diff --git a/std/Number/Ternary.bruijn b/std/Number/Ternary.bruijn index 5392b63..e00bbc5 100644 --- a/std/Number/Ternary.bruijn +++ b/std/Number/Ternary.bruijn @@ -291,6 +291,8 @@ gt? positive? ∘∘ sub ⧗ Number → Number → Boolean compare-case [[[[[go (1 - 0)]]]]] ⧗ a → b → c → Number → Number → d go [=?0 5 (>?0 4 3)] +<?>‣ &compare-case + # ============================================================================ # # most relevant functions are defined - we can now derive from Generic/Number! # # ============================================================================ # diff --git a/std/Number/Unary.bruijn b/std/Number/Unary.bruijn index 214bfb9..96fef9a 100644 --- a/std/Number/Unary.bruijn +++ b/std/Number/Unary.bruijn @@ -103,6 +103,8 @@ eq? [[=?(1 - 0) ⋀? =?(0 - 1)]] ⧗ Unary → Unary → Boolean compare-case [[[[[go (1 - 0) (0 - 1)]]]]] ⧗ a → b → c → Unary → Unary → d go [[=?0 (=?1 6 5) 4]] +<?>‣ &compare-case + # ============================================================================ # # most relevant functions are defined - we can now derive from Generic/Number! # # ============================================================================ # diff --git a/std/Set.bruijn b/std/Set.bruijn index bec1645..0b9ea6d 100644 --- a/std/Set.bruijn +++ b/std/Set.bruijn @@ -1,6 +1,6 @@ # MIT License, Copyright (c) 2023 Marvin Borner -# Set implementation using AVL trees -# can currently only store Numbers (due to std/Tree/Balanced) +# Generic set implementation using AVL trees +# some functions require a compare-case argument! :import std/Tree/Balanced T :import std/List . @@ -9,13 +9,10 @@ empty T.empty ⧗ Set # adds a number of a set -add T.insert ⧗ Number → Set → Set +add T.insert ⧗ Compare → Number → Set → Set # returns true if a number is in a set -has? T.has? ⧗ Number → Set → Boolean - -:test (has? (+5) (add (+5) empty)) ([[1]]) -:test (has? (+5) empty) ([[0]]) +has? T.has? ⧗ Compare → Number → Set → Boolean # count of elements in set size T.size ⧗ Set → Number @@ -24,9 +21,4 @@ size T.size ⧗ Set → Number set→list T.tree→list ⧗ Set → (List Number) # converts a list to a set -list→set T.list→tree ⧗ (List Number) → Set - -:test (has? (+0) (list→set ((+5) : ((+3) : ((+2) : ((+1) : {}(+0))))))) ([[1]]) -:test (has? (+5) (list→set ((+5) : ((+3) : ((+2) : ((+1) : {}(+0))))))) ([[1]]) -:test (has? (+6) (list→set ((+5) : ((+3) : ((+2) : ((+1) : {}(+0))))))) ([[0]]) -:test (has? (+7) (list→set ((+5) : ((+7) : {}(+1))))) ([[1]]) +list→set T.list→tree ⧗ Compare → (List Number) → Set diff --git a/std/Set/NumberSet.bruijn b/std/Set/NumberSet.bruijn new file mode 100644 index 0000000..220e2dc --- /dev/null +++ b/std/Set/NumberSet.bruijn @@ -0,0 +1,22 @@ +# MIT License, Copyright (c) 2024 Marvin Borner + +:input std/Set + +:import std/Number T + +# adds a number of a set +add T.<?>add ⧗ Number → NumberSet → NumberSet + +# returns true if a number is in a set +has? T.<?>has? ⧗ Number → NumberSet → Boolean + +:test (has? (+5) (add (+5) empty)) ([[1]]) +:test (has? (+5) empty) ([[0]]) + +# converts a list to a set +list→set T.<?>list→set ⧗ (List Number) → NumberSet + +:test (has? (+0) (list→set ((+5) : ((+3) : ((+2) : ((+1) : {}(+0))))))) ([[1]]) +:test (has? (+5) (list→set ((+5) : ((+3) : ((+2) : ((+1) : {}(+0))))))) ([[1]]) +:test (has? (+6) (list→set ((+5) : ((+3) : ((+2) : ((+1) : {}(+0))))))) ([[0]]) +:test (has? (+7) (list→set ((+5) : ((+7) : {}(+1))))) ([[1]]) diff --git a/std/Set/StringSet.bruijn b/std/Set/StringSet.bruijn new file mode 100644 index 0000000..4bee345 --- /dev/null +++ b/std/Set/StringSet.bruijn @@ -0,0 +1,23 @@ +# MIT License, Copyright (c) 2024 Marvin Borner +# TODO: hash instead of comparing + +:input std/Set + +:import std/String S + +# adds a number of a set +add S.<?>add ⧗ String → StringSet → StringSet + +# returns true if a number is in a set +has? S.<?>has? ⧗ String → StringSet → Boolean + +:test (has? "abc" (add "abc" empty)) ([[1]]) +:test (has? "abc" empty) ([[0]]) + +# converts a list to a set +list→set S.<?>list→set ⧗ (List String) → StringSet + +:test (has? "0" (list→set ("a" : ("b" : ("d" : ("c" : {}"0")))))) ([[1]]) +:test (has? "a" (list→set ("a" : ("b" : ("d" : ("c" : {}"0")))))) ([[1]]) +:test (has? "e" (list→set ("a" : ("b" : ("d" : ("c" : {}"0")))))) ([[0]]) +:test (has? "c" (list→set ("a" : ("c" : {}"b")))) ([[1]]) diff --git a/std/String.bruijn b/std/String.bruijn index 291188d..4ee002b 100644 --- a/std/String.bruijn +++ b/std/String.bruijn @@ -18,7 +18,9 @@ eq? eq? B.eq? ⧗ String → String → Boolean ?‣ &eq? # returns eq, gt, lt depending on comparison of two numbers -compare-case B.<=>compare-case ⧗ a → b → c → String → String → d +compare-case B.<?>compare-case' ⧗ a → b → c → String → String → d + +<?>‣ &compare-case # returns 1 if a>b, -1 if a<b and 0 if a=b # also: spaceship operator @@ -31,8 +33,8 @@ compare compare-case (+0) (+1) (-1) ⧗ String → String → Number :test (compare "2" "2") ((+0)) :test (compare "2" "1") ((+1)) :test (compare "1" "2") ((-1)) -:test (compare "12" "1") ((-1)) -:test (compare "1" "12") ((+1)) +:test (compare "12" "1") ((+1)) +:test (compare "1" "12") ((-1)) # returns true if string is lexically less than other string lt? c-lt? ∘∘ compare ⧗ String → String → Boolean diff --git a/std/Tree/Balanced.bruijn b/std/Tree/Balanced.bruijn index 8fa3880..70e749e 100644 --- a/std/Tree/Balanced.bruijn +++ b/std/Tree/Balanced.bruijn @@ -1,6 +1,5 @@ # MIT License, Copyright (c) 2023 Marvin Borner -# Balanced AVL tree for numerical leafs, inspired by Rudy Matela's implementation -# TODO: Extend for arbitrary orderable types? +# Balanced AVL tree, inspired by Rudy Matela's implementation # TODO: Analyze performance bottlenecks :import std/Combinator . @@ -80,27 +79,27 @@ balance [go (factor 0)] ⧗ (Option BalancedTree) → (Option BalancedTree) else 1 # inserts a number into a tree -insert z [[[rec]]] ⧗ Number → (Option BalancedTree) → (Option BalancedTree) +insert [z [[[rec]]]] ⧗ Compare → Number → (Option BalancedTree) → (Option BalancedTree) rec none? 0 (some (leaf 1)) (balance (u 1 ?(!0))) - u compare-case eq gt lt + u 3 eq gt lt eq 0 gt some (node //(!0) ?(!0) (2 1 \\(!0))) lt some (node (2 1 //(!0)) ?(!0) \\(!0)) # returns true if a number is in a tree -has? z [[[rec]]] ⧗ Number → (Option BalancedTree) → Boolean +has? [z [[[rec]]]] ⧗ Compare → Number → (Option BalancedTree) → Boolean rec none? 0 false (u 1 ?(!0)) - u compare-case eq gt lt + u 3 eq gt lt eq true gt 2 1 \\(!0) lt 2 1 //(!0) -:test (has? (+42) empty) (false) +:test (has? compare-case (+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-full ++((1 //(!0)) + (1 \\(!0))) case-empty (+0) # converts a tree to a list @@ -108,4 +107,4 @@ tree→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 -list→tree L.foldr insert empty ⧗ (List Number) → (Option BalancedTree) +list→tree [L.foldr (insert 0) empty] ⧗ Compare → (List Number) → (Option BalancedTree) |