Example Programs

Not impressed yet? Here's more...

The perm function generates all permutions of a list:

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

How does it work?

(1) There is only one permutation of a single-element list.

(2) The rot function turns x into a list of rotations of x. It is defined as follows:

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

(3) map head extracts the heads from a list of rotations:

map head [[1, 2, 3], [2, 3, 1], [3, 1, 2]]  -->  [1, 2, 3]

(4) map (perm o tail) extracts the tails of the rotations and generates the permutations of the tails by recursing. perm o tail is the function composition of perm and tail.

map (perm o tail) [[1, 2, 3], [2, 3, 1], [3, 1, 2]]
  --> [[[2, 3], [3, 2]], [[3, 1], [1, 3]], [[1, 2], [2, 1]]] 

(5) The zip function creates tuples from the heads and permutated tails:

zip  [1,2,3]  [[[2, 3], [3, 2]],
               [[3, 1], [1, 3]],
               [[1, 2], [2, 1]]] 
  -->  [(1, [[2, 3], [3, 2]]),
        (2, [[3, 1], [1, 3]]),
        (3, [[1, 2], [2, 1]])]

and append_map maps dist over the above result. Unlike map, append_map appends its results. The dist function distributes its first element over the lists in its second argument:

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

So the final result of the function is this: (@ denotes the concatenation done by append_map)

  dist (1, [[2, 3], [3, 2]])
@ dist (2, [[3, 1], [1, 3]])
@ dist (3, [[1, 2], [2, 1]])  -->  [[1, 2, 3], [1, 3, 2],
                                    [2, 3, 1], [2, 1, 3],
                                    [3, 1, 2], [3, 2, 1]]

Does it make sense now? Have another look! Or check out other examples.

contact  |  privacy