5. List Specification (Sections 4.1, 4.2)

In the next 2 lectures we first give a specification for lists and then discuss various possible implementations and the strengths and weaknesses of each. This is a major case study, an example of how to do this for any abstract data type you ever have to specify and implement.

The abstract type `list' is meant to capture the everyday meaning of `list', as in shopping list, ingredients list, parts list, mailing list... The basic idea is that there are number of entries (items,components) arranged in a strict order e.g. mailing list may be alphabetical or in priority order. The order does not necessarily have any special significance (e.g. shopping list) but, in any case, the items are ordered one after another.

Although everyone agrees in general terms on what a list is, there are numerous ways to specify a list.

5.1. Classical Specification

The textbook's specification takes the classical approach to lists. This emphasizes operations that work on an element by element basis - for example, add one element to a list, delete element item from a list. According to the textbook's specification at any given time you have immediate access to just one element (called the current node). Its specification includes operations for changing the current node to be another element in the list.

5.2. Recursive Specification

Another very common way to specify lists is with a recursive definition,

A list is either EMPTY
or it consists of two parts: (1) a HEAD (first element) and (2) a TAIL (a list)

This closely resembles the specification of a stack, and indeed in the recursive specification of a list there are usually list operations very similar to at least some of the stack operations. But a list differs from a stack in that it is possible to access any item of a list without disturbing any of the other elements - contrast this with a stack, where access is restricted to the top element, so to get access to other elements the stack must be taken apart. Of course, when you take the stack apart you can save all the pieces somewhere and then later reconstruct the stack, but this is entirely the user's responsibility. With a list, the user gets arbitrary access for free.

How does the recursive specification allow access to items other than the head of a list? The idea is that TAIL can be used like POP to move past the early items in the list. This key difference between the two operations is that POP(S) changes S whereas TAIL(L) leaves L alone.

                T = TAIL(L);

creates a list (T) having all the elements of L except the first. But it does not change L. Now HEAD of T is the second element of L. HEAD(TAIL(TAIL(L)) gives access to the third element etc.

The recursive definition is extremely simple and convenient from the application programmer's point of view, and is the normal style of lists built into in recursion-oriented languages like Lisp and Prolog.

As we have seen above, this sort of recursive structural definition directly informs us how to perform many operations on a data structure. Suppose for example, we wanted to add up the values in a list. Following our usual strategy:

ADDUP (L):

if L is EMPTY, return 0
otherwise return HEAD(L) + ADDUP(TAIL(L))

The functions HEAD and TAIL return the two parts of a nonempty list; we apply the ADDUP function recursively to the TAIL and add the result to the HEAD.

A slightly more complex recursive function, called MEMBER, takes 2 arguments, a value V, and a list L, and returns TRUE if V occurs in L and FALSE if it does not.

We can directly solve this problem if L is EMPTY: the answer must be FALSE, no matter what V is, because no value occurs in an empty list.

If L is non-empty, we divide it into its two natural parts, head and tail, and solve the corresponding subproblems:

P1: is value V in L's head? Now, L's head is not a list, it just a single value. So we solve this subproblem, not by a recursive call but simply by comparing V to the L's head. The answer, S1, will be either TRUE or FALSE.
P2: is value V in L's tail? L's tail is a list, so we can solve this subproblem by a recursive call to MEMBER. The answer is S2.

How do we combine these results? The overall answer is TRUE if either S1 or S2 is TRUE. In other words, final answer = S1 OR S2.

In pseudocode the function implementing this strategy would be:

MEMBER(V,L):
  if L is EMPTY  return FALSE;
  else           return V==HEAD(L)  OR  MEMBER(V,TAIL(L));

We may wish to write this in a slightly different way:

MEMBER(V,L):
  if L is EMPTY        return FALSE;
  else  if V==HEAD(L)  return TRUE ;
        else           return  MEMBER(V,TAIL(L));