[mLite]

More Example Programs

List Functions  |  Sorting  |  Combinations and Permutations

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)

contact  |  privacy