Lists

Lists in Prolog are themselves terms, and consist of a sequence of terms separated from one-another by commas and enclosed at each end by matching square brackets:

[a]
[a,b]
[a,b,c]

Note that, as you might expect, [ ] represents the empty list. Internally to Prolog, lists are represented as right-branching trees. So the structure of [a, b, c] would be [a [b [c [ ] ] ] ] The first element of a list is called the head of the list, and the remainder is called the tail of the list. Note that (perhaps counterintuitively) the last element of every non-empty list is the empty list; although the normal Prolog notation suppresses this fact. So a is the head of all the above lists; [ ] is the tail of the first example, [b] is the tail of the second example, and [b, c] is the tail of the third example. Because of the importance of the distinction between the head and tail of a list, Prolog provides a convenient notation that can be used to match against the head and tail of any list.

[X | Y]

Where X will match against the head, and Y against the tail. (Of course, any variable names may be used, not just X and Y.) To illustrate these concepts, we will also introduce an operator which can be used to evaluate unification (discussed in section 1.4) directly. This operator is the equals sign =/2. The expression A = B is true in Prolog, if A is a term, and B is term, and A and B unify. The following can be typed in and evaluated: Two constants:

|?- a = a.

yes

|?- a = b.

no

A constant and a variable:

|?- a = X.

X = a ?

yes

Two variables:

|?- X = Y.

Y = X ?

yes

Using this operator, we can illustrate how variables unify with lists: Lists and variables are both terms:

|?- [ ] = X.

X = [ ] ?

Single-element lists unify (because they have the same `arity'):

|?- [a] = [X].

X = a ?

yes

The following fails, because the two lists have different numbers of elements:

|?- [a, b] = [X].

no

The following unify because both lists are of length 2:

|?- [a, b] = [X, Y].

X = a,

Y = b ?

yes

Note carefully the difference between the above and the following using HeadTail notation. X matches the first element of the list [a], which is the constant a, and Y matches the tail, which is the empty list:

|?- [a] = [X | Y].

X = a,

Y = [ ] ?

yes

Here again, X matches with a, and Y matches with the tail of the list [a, b], which is itself the list [b]:

|?- [a, b] = [X | Y].

X = a,

Y = [b] ?

yes

Finally, a three element list:

|?- [a, b, c] = [X | Y].

X = a,

Y = [b, c] ?

yes

A couple of trivial examples of predicates using lists are the following: