List Functions | Sorting | Combinations and Permutations

Count members of lists

;; count [1,[2],3] --> 3 fun count [] = 0 | x :: xs = count x + count xs | _ = 1

Depth of a list

;; depth [1,[2],3] --> 2 fun depth x :: xs = 1 + (fold (max,0) ` map depth ` x :: xs) | _ = 0

Convert lists to flat lists (linear-recursive version)

;; flatten [1,[2,[3]],4] --> [1,2,3,4] fun flatten x = let fun f ([], r) = r | (x :: xs, r) = f (x, f (xs, r)) | (x, r) = x :: r in f (x, []) end

Scheme-like `assoc`

;; assoc (2, [(1,"a"), (2,"b"), (3,"c")]) --> (2,"b") fun assoc (x, (k, v) :: as) where (x = k) = (k, v) | (x, _ :: as) = assoc (x, as) | (x, []) = false

Partition lists

;; part (fn x = x mod 2 = 0) [1,2,3,4,5] --> ([2,4], [1,3,5]) fun part f = let fun p ([], s1, s0) = (rev s1, rev s0) | (f a :: as, s1, s0) = p (as, a :: s1, s0) | (a :: as, s1, s0) = p (as, s1, a :: s0) in fn a = p (a, [], []) end

Quicksort (median taken from the middle)

;; qsort op < [3,1,5,2,4] --> [1,2,3,4,5] fun qsort f = let fun q [] = [] | [x] = [x] | x = let val k = len x div 2; val m = ref (x, k); val x = sub (x, 0, k) @ sub (x, k+1, len x); val p = part (fn x = f (x, m)) x in q #0p @ [m] @ q #1p end in fn a = q a end

Split lists into fixed-length groups (except last group)

;; group ([1,2,3,4,5,6,7], 3) --> [[1,2,3], [4,5,6], [7]] fun group (x, k) = let fun g ([], a, r, _) = rev (rev a :: r) | (x, a, r, 0) = g (x, [], rev a :: r, k) | (x :: xs, a, r, n) = g (xs, x :: a, r, n - 1) in g (x, [], [], k) end

Split lists into two (almost) equally-sized sublists

;; split [1,2,3,4,5] --> [[1,2,3], [4,5]] fun split x = group (x, ceil ` len x / 2)

Merge lists under a predicate

;; merge (<, [1,3,5], [2,4,6]) --> [1,2,3,4,5,6] fun merge (f, a, b) = let fun m ([], [], r) = r | (a :: as, [], r) = m (as, [], a :: r) | ([], b :: bs, r) = m ([], bs, b :: r) | (a :: as, b :: bs, r) where f (a, b) = m (a :: as, bs, b :: r) | (a :: as, b :: bs, r) = m (as, b :: bs, a :: r) in m (rev a, rev b, []) end

Mergesort

;; mergesort op < [3,1,5,2,4] --> [1,2,3,4,5] fun mergesort f = let fun s [] = [] | [x] = [x] | a = let val [p1,p2] = split a in merge (f, s p1, s p2) end in fn a = s a end

Generate rotations of a list

;; rot [1,2,3] --> [[1,2,3], [2,3,1], [3,1,2]] fun rot (_, 0) = [] | (x :: xs, k) = (x :: xs) :: rot (xs @ [x], k - 1) | x = rot (x, len x)

Distribute elements over lists

;; dist (1, [[2], [3], [4]]) --> [[1,2], [1,3], [1,4]] fun dist (x, a :: as) = (x :: a) :: dist (x, as) | (x, []) = []

Map functions over list tails

;; maptail (fn x=x) [1,2,3,4] --> [[1,2,3,4], [2,3,4], [3,4], [4]] fun maptail f = let fun m [] = [] | x :: xs = f (x :: xs) :: m xs in fn a = m a end

Generate k-combinations of lists

;; kcomb (2, [1,2,3]) --> [[1,2], [1,3], [2,3]] fun kcomb (0, _) = [] | (1, a) = map (fn x = [x]) a | (k, a) = append_map (fn h :: t = map (fn x = h :: x) ` kcomb (k - 1, t)) ` maptail (fn x = x) a

Generate multicombinations of lists (this is almost the same as above)

```
;; mcomb (2, [1,2,3]) --> [[1,1], [1,2], [1,3], [2,2], [2,3], [3,3]]
fun mcomb (0, _) = []
| (1, a) = map (fn x = [x]) a
| (k, a) = append_map (fn h :: t =
map (fn x = h :: x)
` mcomb (k - 1, h :: t))
` maptail (fn x = x) a
```

Generate permutations of lists

;; perm [1,2,3] --> [[1,2,3],[1,3,2],[2,3,1],[2,1,3],[3,1,2],[3,2,1]] fun perm [x] = [[x]] | x = let val r = rot x in let val ts = map (perm o tail) r in append_map dist ` zip x ts end end

Generate k-permutations of lists

;; kperm (2, [1,2,3]) --> [[1,2], [2,1], [1,3], [3,1], [2,3], [3,2]] fun kperm (k, a) = append_map perm ` kcomb (k, a)