4 files changed, 58 insertions, 21 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
diff --git a/std/Math.bruijn b/std/Math.bruijn
index ee33fa2..3b3bca8 100644
--- a/std/Math.bruijn
+++ b/std/Math.bruijn
@@ -1,9 +1,9 @@
 # MIT License, Copyright (c) 2022 Marvin Borner
 
-:import std/List .
-
 :input std/Number
 
+:import std/List .
+
 # adds all values in list
 sum foldl add (+0) ⧗ (List Number) → Number
 
diff --git a/std/Pair.bruijn b/std/Pair.bruijn
index a955fe2..95995ee 100644
--- a/std/Pair.bruijn
+++ b/std/Pair.bruijn
@@ -21,6 +21,13 @@ snd [0 ki] ⧗ (Pair a b) → b
 
 :test (~([[0]] : [[1]])) ([[1]])
 
+# maps both elements to a function
+map [[(1 ^0) : (1 ~0)]] ⧗ (a → b) → (Pair a a) → (Pair b b)
+
+…<$>… map
+
+:test ([[1]] <$> ([[0]] : [[1]])) ([[[0]]] : [[[1]]])
+
 # applies both elements of a pair to a function
 uncurry [[1 ^0 ~0]] ⧗ (a → b → c) → (Pair a b) → c
 
diff --git a/std/String.bruijn b/std/String.bruijn
index 9267f20..d613dea 100644
--- a/std/String.bruijn
+++ b/std/String.bruijn
@@ -35,8 +35,8 @@ number! from-digits ∘ (map C.number!)
 
 # splits string by newline character
 lines z [[rec]]
-	rec ∅?(~broken) (^broken : empty) (^broken : (1 ~(~broken)))
-		broken break (B.eq? '\n') 0
+	rec build (break (B.eq? '\n') 0)
+		build [∅?(~0) (^0 : empty) (^0 : (2 ~(~0)))]
 
 :test (lines "ab\ncd") ("ab" : ("cd" : empty))