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.

exceptionEmpty;exceptionOverflow;exceptionSubscript;

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.

funhd [] =raiseEmpty | 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.

funlast [] =raiseEmpty | 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.

funtl [] =raiseEmpty | 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 | SOMEof'a;

The definitions of these `tester' functions follow.

funhd_tst [] = NONE | hd_tst (h::t) = SOME h;funlast_tst [] = NONE | last_tst [x] = SOME x | last_tst (h::t) = last_tst t;funtl_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.

funtester f x = SOME (f x)h_ => NONE;andle

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.

funlength [] = 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.

5 @infixrfun[] @ 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.4 @infixrfun[] @ l2 = l2 | (h::t) @ l2 = h :: t @ l2;5 @infixrCould 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*).

funrev [] = [] | 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.

funrevAppend ([], l2) = l2 | revAppend (h::t,l2) = revAppend (t, h::l2);

**Exercise**

Provide a definition of a reverse function by using reverse appending.