NEXT ·  UP ·  PREVIOUS ·  CONTENTS ·  INDEX

Lists

This pleasant datatype is to be found in almost all functional programming languages. In untyped languages lists are simply collections but in typed languages they are collections of values of the same type and so a list is always a list of something. Properly speaking, in Standard ML list is not a type, it is a type constructor. When we choose a particular type for the variable used by the type constructor then we have a type; so char list is a type and int list is a type and so forth. As we saw when we considered the definition [*] a list can be built up by using two value constructors, one for empty lists [nil of type 'a list] and one for non-empty lists [:: of type 'a * 'a list -> 'a list]. Some languages also provide destructors often called head and tail (car and cdr in LISP.)

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.

NEXT ·  UP ·  PREVIOUS ·  CONTENTS ·  INDEX