diff options
Diffstat (limited to 'std')
| -rw-r--r-- | std/Set.bruijn | 16 | ||||
| -rw-r--r-- | std/Tree/Balanced.bruijn | 31 |
2 files changed, 32 insertions, 15 deletions
diff --git a/std/Set.bruijn b/std/Set.bruijn index 5f64335..bec1645 100644 --- a/std/Set.bruijn +++ b/std/Set.bruijn @@ -3,6 +3,7 @@ # can currently only store Numbers (due to std/Tree/Balanced) :import std/Tree/Balanced T +:import std/List . # empty set empty T.empty ⧗ Set @@ -13,8 +14,19 @@ add T.insert ⧗ 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]]) + +# count of elements in set +size T.size ⧗ Set → Number + # converts a set to a list -list! T.list! ⧗ Set → (List Number) +set→list T.tree→list ⧗ Set → (List Number) # converts a list to a set -from-list T.from-list ⧗ (List Number) → 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]]) diff --git a/std/Tree/Balanced.bruijn b/std/Tree/Balanced.bruijn index 39d5bc8..8fa3880 100644 --- a/std/Tree/Balanced.bruijn +++ b/std/Tree/Balanced.bruijn @@ -2,14 +2,13 @@ # Balanced AVL tree for numerical leafs, inspired by Rudy Matela's implementation # TODO: Extend for arbitrary orderable types? # TODO: Analyze performance bottlenecks -# TODO: More tests :import std/Combinator . :import std/List L :import std/Logic . -:import std/Number . :import std/Option . :import std/Pair . +:import std/Number . # error return that can't happen (in theory) error Ω @@ -48,20 +47,26 @@ left [^(~0)] ⧗ BalancedTree → (Option BalancedTree) //‣ left +:test (//(node none (+0) none)) (none) +:test (//(node (some (leaf (+3))) (+0) none)) (some (leaf (+3))) + # returns the right branch of a tree right [~(~(~0))] ⧗ BalancedTree → (Option BalancedTree) \\‣ right +:test (\\(node none (+0) none)) (none) +:test (\\(node none (+0) (some (leaf (+3))))) (some (leaf (+3))) + # returns the balancing factor of a tree factor map-or (+0) d ⧗ (Option BalancedTree) → Number d [(height //0) - (height \\0)] :test (factor (some (leaf (+42)))) (++(-1)) -rotate-ll [node //(!(//0)) ?(//0) (some (node \\(!(//0)))) ?0 \\0] ⧗ BalancedTree → BalancedTree +rotate-ll [node //(!(//0)) ?(!(//0)) (some (node \\(!(//0)) ?0 \\0))] ⧗ BalancedTree → BalancedTree -rotate-rr [node (some (node //0 ?0 //(!(\\0)))) ?(\\0) \\(!(\\0))] ⧗ BalancedTree → BalancedTree +rotate-rr [node (some (node //0 ?0 //(!(\\0)))) ?(!(\\0)) \\(!(\\0))] ⧗ BalancedTree → BalancedTree rotate-lr [rotate-ll (node (some (rotate-rr !(//0))) ?0 \\0)] ⧗ BalancedTree → BalancedTree @@ -69,26 +74,26 @@ rotate-rl [rotate-rr (node //0 ?0 (some (rotate-ll !(\\0))))] ⧗ BalancedTree â # balances a tree balance [go (factor 0)] ⧗ (Option BalancedTree) → (Option BalancedTree) - go [=?0 else ((0 >? (+1)) left ((0 <? (-1)) right else))] - left some (((factor //(!1)) =? (-1)) (rotate-lr !1) (rotate-ll !1)) - right some (((factor \\(!1)) =? (+1)) (rotate-rl !1) (rotate-rr !1)) + go [=?0 else (0 >? (+1) left (0 <? (-1) right else))] + left some (((factor //(!1)) =? (-1)) rotate-lr rotate-ll !1) + right some (((factor \\(!1)) =? (+1)) rotate-rl rotate-rr !1) else 1 # inserts a number into a tree insert z [[[rec]]] ⧗ Number → (Option BalancedTree) → (Option BalancedTree) rec none? 0 (some (leaf 1)) (balance (u 1 ?(!0))) - u compare-case eq lt gt + u compare-case eq gt lt eq 0 - lt some (node (2 1 //(!0)) ?(!0) \\(!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 rec none? 0 false (u 1 ?(!0)) - u compare-case eq lt gt + u compare-case eq gt lt eq true - lt 2 1 //(!0) gt 2 1 \\(!0) + lt 2 1 //(!0) :test (has? (+42) empty) (false) @@ -99,8 +104,8 @@ size z [[rec]] ⧗ (Option BalancedTree) → Number case-empty (+0) # converts a tree to a list -list! z [[map-or L.empty go 0]] ⧗ (Option BalancedTree) → (List Number) +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 -from-list L.foldr insert empty ⧗ (List Number) → (Option BalancedTree) +list→tree L.foldr insert empty ⧗ (List Number) → (Option BalancedTree) |