As noted in the previous handout, 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
[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 the last
notes) 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:
| ?- [a] = X. X = [a] ?
Single-element lists unify:
| ?- [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
Head|Tail 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] ? Y = b yes
A couple of trivial examples of predicates using lists are the following: