Recursive Specification of Lists

either a list is_empty
or it consists of two parts: a head (first element) and a tail (list of the remaining elements).

Resembles a stack, except elements can be accessed freely.

Unlike pop, tail does not modify its argument. T = tail(L) leaves L alone and creates a list T having all the elements of L except the first.

head(tail(tail(L))) gives access to the 3rd element of L.

Example Recursive Functions On Lists

int addup(list L)
{ return is_empty(L) ? 0 : head(L) + addup(tail(L)); }

boolean member (int V,list L)
{ return is_empty(L) ? false
         : V==head(L) || member(V,tail(L)); }