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.

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)

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))

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.

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));