diff options
Diffstat (limited to 'std/List.bruijn')
| -rw-r--r-- | std/List.bruijn | 64 |
1 files changed, 47 insertions, 17 deletions
diff --git a/std/List.bruijn b/std/List.bruijn index 1241576..afcfe6b 100644 --- a/std/List.bruijn +++ b/std/List.bruijn @@ -253,33 +253,63 @@ drop-while z [[[rec]]] ⧗ (a → Boolean) → (List a) → (List a) :test (drop-while zero? ((+0) : ((+0) : ((+1) : empty)))) ((+1) : empty) # returns pair of take-while and drop-while -span z [[[rec]]] ⧗ (a → Boolean) → (List a) → (Pair (List a) (List a)) - rec ∅?0 case-end case-drop - case-drop 1 ^0 ((^0 : ^recced) : ~recced) (empty : 0) - recced 2 1 ~0 - case-end empty : empty +span [[(take-while 1 0) : (drop-while 1 0)]] ⧗ (a → Boolean) → (List a) → (Pair (List a) (List a)) :test (span (\les? (+3)) ((+1) : ((+2) : ((+4) : ((+1) : empty))))) (((+1) : ((+2) : empty)) : ((+4) : ((+1) : empty))) # same as span but with inverted predicate # slower but equivalent: span ∘ (…∘… ¬‣) -break z [[[rec]]] ⧗ (a → Boolean) → (List a) → (Pair (List a) (List a)) - rec ∅?0 case-end case-drop - case-drop ¬(1 ^0) ((^0 : ^recced) : ~recced) (empty : 0) - recced 2 1 ~0 - case-end empty : empty +break [[left : right]] ⧗ (a → Boolean) → (List a) → (Pair (List a) (List a)) + left take-while (¬‣ ∘ 1) 0 + right drop-while (¬‣ ∘ 1) 0 :test (break (\gre? (+3)) ((+1) : ((+2) : ((+4) : ((+1) : empty))))) (((+1) : ((+2) : empty)) : ((+4) : ((+1) : empty))) -# splits a list into two lists based on predicate -split-at z [[[rec]]] ⧗ (a → Boolean) → (List a) → (Pair (List a) (List a)) - rec ∅?dropped case-end case-split - dropped drop-while 1 0 - case-split ^broken : (2 1 ~broken) - broken break 1 dropped +# groups list by eq predicate +group-by z [[[rec]]] ⧗ (a → a → Boolean) → (List a) → (List (List a)) + rec ∅?0 case-end case-group + case-group build (span (1 ^0) ~0) + build [(^1 : ^0) : (3 2 ~0)] + case-end empty + +:test (group-by [[(0 - 1) <? (+2)]] ((+1) : ((+2) : ((+3) : ((+4) : empty))))) (((+1) : ((+2) : empty)) : (((+3) : ((+4) : empty)) : empty)) + +# splits a list into a pair of two lists based on predicate, drops match +split-by [[left : right]] ⧗ (a → Boolean) → (List a) → (Pair (List a) (List a)) + left take-while (¬‣ ∘ 1) 0 + right fix (drop-while (¬‣ ∘ 1) 0) + fix [∅?0 empty ~0] + +:test (split-by (…=?… (+1)) ((+2) : ((+1) : ((+3) : ((+2) : empty))))) ((((+2) : empty) : ((+3) : ((+2) : empty)))) + +# splits a list into lists based on predicate, drops match +split-list-by z [[[rec]]] ⧗ (a → Boolean) → (List a) → (List (List a)) + rec ∅?0 case-end case-split + case-split build (split-by 1 0) + build [^0 : (3 2 ~0)] + case-end empty + +:test (split-list-by (…=?… (+1)) ((+2) : ((+1) : ((+3) : ((+2) : empty))))) ((((+2) : empty) : (((+3) : ((+2) : empty)) : empty))) + +# sorts a list of numbers in ascending order using non-inplace (obviously) quicksort +sort-asc z [[rec]] + rec ∅?0 case-end case-sort + case-sort (1 lesser) ++ {}(^0) ++ (1 greater) + lesser ~0 <#> (\les? ^0) + greater ~0 <#> (\geq? ^0) + case-end empty + +:test (sort-asc ((+3) : ((+2) : ((+1) : empty)))) ((+1) : ((+2) : ((+3) : empty))) + +# sorts a list of numbers in descending order using non-inplace (obviously) quicksort +sort-desc z [[rec]] + rec ∅?0 case-end case-sort + case-sort (1 greater) ++ {}(^0) ++ (1 lesser) + greater ~0 <#> (\geq? ^0) + lesser ~0 <#> (\les? ^0) case-end empty -:test (split-at (…=?… (+1)) ((+2) : ((+1) : ((+3) : ((+2) : empty))))) ((((+2) : empty) : (((+3) : ((+2) : empty)) : empty))) +:test (sort-desc ((+1) : ((+2) : ((+3) : empty)))) ((+3) : ((+2) : ((+1) : empty))) # returns true if any element in a list matches a predicate any? ⋁?‣ ∘∘ map ⧗ (a → Boolean) → (List a) → Boolean |