12.3. More Features

12.3.1. Collections

A more interesting example (copied from [ULLMAN98]>) is the following implementation of merge sort. The algorithm is implemented with three functions: split, merge, and mergeSort. The split function just splits a list into two halfs returned as a pair of lists.

- fun split(nil) = (nil, nil)
    | split([a]) = ([a], nil)
    | split(a::b::cs) =
        let val (M,N) = split(cs) in (a::M, b::N) end;
> val 'a split = fn : 'a list -> 'a list * 'a list

The first two lines take care of the trivial cases of an empty list and a list containing a single element. If the list has at least two elements, we split what's left behind the first two elements and prepend these element to the two resulting lists. As you can tell, this is harder to describe in plain english (at least for me) than in the two lines of ML code. Next we need the merge function which merges two ordered lists so that the result is again an ordered list.

- fun merge(nil, M) = M
    | merge(L, nil) = L
    | merge(L as x::xs, M as y::ys) =
        if x<y then x::merge(xs, M) else y::merge(L, ys);
> val merge = fn : int list * int list -> int list

The new feature here is the "as" expression in the last pattern. It lets us refer to the matching values in two different ways, as lists and split into head and tail, just as needed for the merge function.

- fun mergeSort(nil) = nil
    | mergeSort([a]) = [a]
    | mergeSort(L) =
        let val (M, N) = split(L) in
          merge(mergeSort(M), mergeSort(N))
        end;
> val mergeSort = fn : int list -> int list
- val l = [3, 4, 2, 7, 1];
> val l = [3, 4, 2, 7, 1] : int list
- mergeSort(l);
> val it = [1, 2, 3, 4, 7] : int list

After this preparation, the mergeSort function is not surprising anymore. ML also has the typical higher order list processiong functions map and reduce.

- map (fn x => 2*x) [1, 2, 3];
> val it = [2, 4, 6] : int list

12.3.2. Exceptions