Not impressed yet? Here's more...

The `perm`

function generates all permutions of a list:

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

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.