![[mLite]](mlite.png)
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)