The definition of Standard ML does not insist that these destructors should be available since they are not needed; a list value may be decomposed by matching it against a pattern which uses the constructor. If we wished to use these destructors, how could we implement them? A difficulty which we would encounter in any typed language is that these functions are undefined for empty lists and so they must fail in these cases. Standard ML provides exceptions as a mechanism to signal failure. Raising an exception is a different activity from returning a value. For the purposes of type-checking it is similar to non-termination because no value is returned when an exception is raised.
An exception is introduced using the exception keyword. Here are declarations for three exceptions, Empty, Overflow and Subscript.
exception Empty; exception Overflow; exception Subscript;
These declarations provide us with three new constructors for the built-in exn type. Like constructors of a datatype Empty, Overflow and Subscript may be used in patterns to denote themselves. Again like constructors of a datatype they may be handled as values--passed to functions, returned as results, stored in lists and so forth. Exception constructors differ from datatype constructors in that they may be raised to signal that an exceptional case has been encountered and raised exceptions may subsequently be handled in order to recover from the effect of encountering an exceptional case. Thus exceptions are not fatal errors, they are merely transfers of program control. Now to return to implementing list destructors.
Definition (Head)
An empty list has no head. This is an exceptional case. The head of a non-empty list is the first element. This function has type 'a list -> 'a.
fun hd [] = raise Empty | hd (h::t) = h;
Definition (Last)
An empty list has no last element. This is an exceptional case. The last element of a one-element list is the first element. The last element of a longer list is the last element of its tail. This function has type 'a list -> 'a.
fun last [] = raise Empty | last [x] = x | last (h::t) = last t;
Definition (Tail)
An empty list has no tail. This is an exceptional case. The tail of a non-empty list is that part of the list following the first element. This function has type 'a list -> 'a list.
fun tl [] = raise Empty | tl (h::t) = t;
Definition (Testers)
We might instead choose to use versions of head, last and tail functions which are of type 'a list -> 'a option and 'a list -> 'a list option. The option datatype is defined as shown below.
datatype 'a option = NONE | SOME of 'a;
The definitions of these `tester' functions follow.
fun hd_tst [] = NONE | hd_tst (h::t) = SOME h; fun last_tst [] = NONE | last_tst [x] = SOME x | last_tst (h::t) = last_tst t; fun tl_tst [] = NONE | tl_tst (h::t) = SOME t;
These functions never raise exceptions and might be used in preference to the exception-producing versions given above. The conversion from one set to the other is so systematic that we can write a general purpose function to perform the conversion from an exception-producing function to one with an optional result. The tester function shown below achieves this effect. Any exception which is raised by the application of f to x is handled and the value NONE is returned.
fun tester f x = SOME (f x) handle _ => NONE;
Thus hd_tst is equivalent to tester hd, last_tst is equivalent to tester last and tl_tst is equivalent to tester tl.
Definition (Length)
The length function for lists has type 'a list -> int. The empty list has length zero; a list with a head and a tail is one element longer than its tail.
fun length [] = 0 | length (h::t) = 1 + length t;
Definition (Append)
The append function has type ('a list * 'a list) -> 'a list. In fact this is a pre-defined right associative operator, @, in Standard ML. If l1 and l2 are two lists of the same type then l1 @ l2 is a list which contains all the elements of both lists in the order they occur. This append operator has the same precedence as cons.
infixr 5 @ fun [] @ l2 = l2 | (h::t) @ l2 = h :: t @ l2;
Exercise
Consider the situation where we had initially mistakenly set the precedence of the append symbol to be four, and corrected this immediately afterwards.infixr 4 @ fun [] @ l2 = l2 | (h::t) @ l2 = h :: t @ l2; infixr 5 @Could this mistake be detected subsequently? If so, how?
Definition (Reverse)
Using the append function we can easily define the function which reverses lists. This function has type 'a list -> 'a list. The rev function is pre-defined but we will give a definition here which is identical to the pre-defined function. The base case for the recursion will be the empty list which reverses to itself. Given a list with head h and tail t then we need only reverse t and append the single-element list [h] (equivalently, h :: nil).
fun rev [] = [] | rev (h::t) = (rev t) @ [h];
Definition (Reverse append)
One some occasions, the order in which elements appear in a list is not very important and we do not care about having the order of the inputs preserved in the results (as the append function does). The revAppend function joins lists by reversing the first onto the front of the second.
fun revAppend ([], l2) = l2 | revAppend (h::t,l2) = revAppend (t, h::l2);
Exercise
Provide a definition of a reverse function by using reverse appending.