All the examples of unification seen so far have included only predictable,
fixed data structures, such as atomics and structured objects. We
can unify one list with another:
| ?- [a, b, c] = [Elem1, Elem2, Elem3].
Elem1 = a,
Elem2 = b,
Elem3 = c ?
and because an uninstantiated variable will unify with anything, we
can unify a list with a variable:
| ?- Var = [a, b, c].
Var = [a,b,c] ?
As these two examples show, we haven't achieved much. In the first
example we had to know exactly how many elements there are in the
lists: in the second example we just instantiated Var to
the complete list, rather than accessing parts of it.
In order to be able to use unification with lists of unknown length,
we must have an extension to the list notation and so to our way
of thinking about lists.
Rather than thinking of a list as consisting of a certain number
of elements, we can think of it as having a head and a tail.
At the simplest, the head is the first element of the list and the
tail is the remainder. In Prolog, we use the "list constructor"
(written as "|") to denote the head and tail.
| ?- [a, b, c] = [Head|Tail].
Head = a,
Tail = [b,c] ?
The important thing to notice in this example is that the tail of
the list is itself a list. In this example, there was one element
before the list constructor, but it is possible to have more than
one:
| ?- [a, b, c] = [Head1, Head2|Tail].
Tail = [c],
Head1 = a,
Head2 = b ?
Again, note that the tail of the list is still a list in its own right,
even though it only has one element. What happens if we extend this
example to include three elements before the list constructor?
| ?- [a, b, c] = [Hd1, Hd2, Hd3|Tail].
Hd1 = a,
Hd2 = b,
Hd3 = c,
Tail = [] ?
All three elements are unified with variables before the list constructor,
so there is nothing with which Tail can be unified. This
is shown by Tail being instantiated to the empty list '[]'.
|
