Learn Prolog Now!

4.1 Lists

As its name suggests, a list is just a plain old list of items. Slightly more precisely, it is a finite sequence of elements. Here are some examples of lists in Prolog:

[mia, vincent, jules, yolanda]

[mia, robber(honey_bunny), X, 2, mia]

[]

[mia, [vincent, jules], [butch, girlfriend(butch)]]

[[], dead(z), [2, [b, c]], [], Z, [2, [b, c]]]

We can learn some important things from these examples.

We can specify lists in Prolog by enclosing the elements of the list in square brackets (that is, the symbols [ and ] ). The elements are separated by commas. For example, the first list shown above, [mia, vincent, jules, yolanda] , is a list with four elements, namely mia , vincent , jules , and yolanda . The length of a list is the number of elements it has, so our first example is a list of length four.
From [mia,robber(honey_bunny),X,2,mia] , our second example, we learn that all sorts of Prolog objects can be elements of a list. The first element of this list is mia , an atom; the second element is robber(honey_bunny) , a complex term; the third element is X , a variable; the fourth element is 2 , a number. Moreover, we also learn that the same item may occur more than once in the same list: for example, the fifth element of this list is mia , which is same as the first element.
The third example shows that there is a special list, the empty list. The empty list (as its name suggests) is the list that contains no elements. What is the length of the empty list? Zero, of course (for the length of a list is the number of members it contains, and the empty list contains nothing).
The fourth example teaches us something extremely important: lists can contain other lists as elements. For example, the second element of
```
[mia, [vincent, jules], [butch,girlfriend(butch)]
```
is [vincent,jules] . The third is [butch,girlfriend(butch)] .

What is the length of the fourth list? The answer is: three. If you thought it was five (or indeed, anything else) you’re not thinking about lists in the right way. The elements of the list are the things between the outermost square brackets separated by commas. So this list contains three elements: the first element is mia , the second element is [vincent, jules] , and the third element is [butch, girlfriend(butch)] .
The last example mixes all these ideas together. We have here a list which contains the empty list (in fact, it contains it twice), the complex term dead(z) , two copies of the list [2, [b, c]] , and the variable Z . Note that the third (and the last) elements are lists which themselves contain lists (namely [b, c] ).

Now for an important point. Any non-empty list can be thought of as consisting of two parts: the head and the tail. The head is simply the first item in the list; the tail is everything else. To put it more precisely, the tail is the list that remains when we take the first element away; that is, the tail of a list is always a list . For example, the head of

?- [mia, vincent, jules, yolanda].

is mia and the tail is [vincent, jules, yolanda] . Similarly, the head of

?- [[], dead(z), [2, [b, c]], [], Z, [2, [b, c]]].

is [] , and the tail is [dead(z), [2,[b,c]],[],Z,[2,[b, c]]] . And what are the head and the tail of the list [dead(z)] ? Well, the head is the first element of the list, which is dead(z) , and the tail is the list that remains if we take the head away, which, in this case, is the empty list [] .

What about the empty list? It has neither a head nor a tail. That is, the empty list has no internal structure; for Prolog, [] is a special, particularly simple, list. As we shall learn when we start writing recursive list processing programs, this fact plays an important role in Prolog programming.

Prolog has a special built-in operator | which can be used to decompose a list into its head and tail. It is important to get to know how to use | , for it is a key tool for writing Prolog list manipulation programs.

The most obvious use of | is to extract information from lists. We do this by using | together with unification. For example, to get hold of the head and tail of [mia,vincent, jules,yolanda] we can pose the following query:

?- [Head|Tail] = [mia, vincent, jules, yolanda].

Head = mia
Tail = [vincent,jules,yolanda]
yes

That is, the head of the list has become bound to Head and the tail of the list has become bound to Tail . Note that there is nothing special about Head and Tail , they are simply variables. We could just as well have posed the query:

?- [X|Y] = [mia, vincent, jules, yolanda].

X = mia
Y = [vincent,jules,yolanda]
yes

As we mentioned above, only non-empty lists have heads and tails. If we try to use | to pull [] apart, Prolog will fail:

?- [X|Y] = [].

no

That is, Prolog treats [] as a special list. This observation is extremely important. We’ll see why later.

Let’s look at some other examples. We can extract the head and tail of the following list just as we saw above:

?- [X|Y] = [[], dead(z), [2, [b, c]], [], Z].

X = []
Y = [dead(z),[2,[b,c]],[],_7800]
Z = _7800
yes

That is: the head of the list is bound to X , the tail is bound to Y . (We also learn that Prolog has bound Z to the internal variable _7800 .)

But we can do a lot more with | ; it really is a flexible tool. For example, suppose we wanted to know what the first two elements of the list were, and also the remainder of the list after the second element. Then we’d pose the following query:

?- [X,Y | W] = [[], dead(z), [2, [b, c]], [], Z].

X = []
Y = dead(z)
W = [[2,[b,c]],[],_8327]
Z = _8327
yes

That is, the head of the list is bound to X , the second element is bound to Y , and the remainder of the list after the second element is bound to W (that is, W is the list that remains when we take away the first two elements). So | can not only be used to split a list into its head and its tail, we can also use it to split a list at any point. To the left of | we simply indicate how many elements we want to take away from the front of the list, and then to right of the | we will get what remains.

This is a good time to introduce the anonymous variable. Suppose we were interested in getting hold of the second and fourth elements of the list:

?- [[], dead(z), [2, [b, c]], [], Z].

Now, we could find out like this:

?- [X1,X2,X3,X4 | Tail] =
            [[], dead(z), [2, [b, c]], [], Z].

X1 = []
X2 = dead(z)
X3 = [2,[b,c]]
X4 = []
Tail = [_8910]
Z = _8910
yes

Ok, we have got the information we wanted: the values we are interested in are bound to the variables X2 and X4 . But we’ve got a lot of other information too (namely the values bound to X1 , X3 and Tail ). And perhaps we’re not interested in all this other stuff. If so, it’s a bit silly having to explicitly introduce variables X1 , X3 and Tail to deal with it. And in fact, there is a simpler way to obtain only the information we want: we can pose the following query instead:

?- [_,X,_,Y|_] = [[], dead(z), [2, [b, c]], [], Z].

X = dead(z)
Y = []
Z = _9593
yes

The _ symbol (that is, underscore) is the anonymous variable. We use it when we need to use a variable, but we’re not interested in what Prolog instantiates the variable to. As you can see in the above example, Prolog didn’t bother telling us what _ was bound to. Moreover, note that each occurrence of _ is independent : each is bound to something different. This couldn’t happen with an ordinary variable of course, but then the anonymous variable isn’t meant to be ordinary. It’s simply a way of telling Prolog to bind something to a given position, completely independently of any other bindings.

Let’s look at one last example. The third element of our working example is a list (namely [2, [b, c]] ). Suppose we wanted to extract the tail of this internal list, and that we are not interested in any other information. How could we do this? As follows:

?- [_,_,[_|X]|_] =
      [[], dead(z), [2, [b, c]], [], Z, [2, [b, c]]].

X = [[b,c]]
Z = _10087
yes

[ next ] [ front ] [ up ]