13.1 The definition of a list (Ad)

Defining what a list is

A list is a datastructure which is central to Prolog. Informally, a list is an ordered sequence of items. For example, the following is a list:

(Peter,Paul,Mary)

The list is a sequence of items, which means that it is a succession of items after each other. The list is ordered, which means that it does matter in which order or sequence the items are. For example, the following list is different from the above list:

(Mary,Paul,Peter)

because the items are in a different order.

Had this been a set rather than a list, the order would not have mattered. But since a list is an ordered sequence, the order does matter.

We usually call the items of a list the elements of a list.

Recursive definition of a list

The notion of 'list' can be defined recursively as follows:

A list is either the empty list (called 'nil'), or it is a head followed by a tail, where the head is an element and the tail is a list.

Unraveling the recursive definition

We see that a list is one of two things. It is:

  1. Either the empty list, called 'nil',
  2. Or a succession consisting of:
    1. The head of the list, which is an element,
    2. The tail of the list, which is a list.

We see that a list is partially defined in terms of itself. The tail of a list is a list. It is this self-reference which gives the predicate "recursive" in the definition.

In order to translate a list such as the following:

(Ishmael, Isaac)

to something that matches the above definition, we could define a structure called cons/2. This structure would look as follows:

cons(H,T)

This structure would be interpreted to mean that:

  1. the head H (which is an element)
  2. is before
  3. the tail T (which is a list).

At the same time, we would define an atomic constant called nil:

nil

which would be interpreted to be an empty list.

We now have all of the ingredients needed to translate our example list:

(Ishmael, Isaac)

to something that matches the definition:

cons(Ishmael, cons(Isaac, nil))

We see that Ishmael is in the place of the head of the outermost cons. In the place of the tail of this outermost cons, we find another cons. This inner cons has Isaac in the place of the head, and the list 'nil' in the place of the tail. Thus the list terminates after Isaac.

Again, the list

(Peter,Paul,Mary)

would be written as:

cons(Peter, cons(Paul, cons(Mary, nil)))

Exercise: Try to unravel this list, identifying each part, and saying whether each part is a head or a tail, an element or a list. Be sure to point out where the brackets for each part begin and end.

Summary

A list is an ordered sequence of elements. A list can be defined recursively as follows:

A list is either the empty list, or it is an element followed by a list. The element is called the head of the list, and the trailing list is called the tail of the list.

It is the element of self-reference that gives rise to the predicate recursive definition.

Next

Next, we take a deeper look at what exactly makes a definition 'recursive'.


Prev: 13 Recursivity and lists (Ad)
Up: 13 Recursivity and lists (Ad)
Next: 13.2 Recursive definitions (Ad)