Selecting from a list

It is useful to have functions which select elements from a list, perhaps selecting the nth element numbered from zero. This function will have type 'a list * int -> 'a and should raise the exception Subscript whenever the nth element cannot be found (either because there are fewer than n elements or because n is negative).

fun nth ([], _) = raise Subscript
  | nth (h::t, 0) = h
  | nth (_::t, n) = nth (t, n-1) handle Overflow => raise Subscript;

Note the excruciatingly complicated final case. We could program the test for a negative index explicitly with a conditional expression but this would cost us the test every time that the function was called whereas the present expression of this function allows the negative number to be reduced successively until either the list runs out and the Subscript exception is raised or the subtraction operation underflows (raising Overflow!) and this is handled in order that the Subscript exception may be raised instead.

The selection criteria might be moderately more complex:

1.

select the first n elements; or

2.

select all but the first n elements.

Call the function which implements the first criterion take and the function which implements the second drop. The selection could be slightly more exacting if we supply a predicate which characterises the required elements. The selection might then be:

1.

select the leading elements which satisfy the criterion; or

2.

select all but the leading elements which satisfy the criterion.

Call the function which implements the first criterion takewhile and the function which implements the second dropwhile. We will implement take and takewhile.