# More Example Programs

## Some List Functions

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
```

## Sorting

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
```

## Combinations and Permutations

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)
```