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(zed), [2, [b, chopper]], [], Z, [2, [b, chopper]]]

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, our first example [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 our second example, [mia,robber(honey_bunny),X,2,mia], 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 very 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 the list [vincent,jules], and the third element is [butch,girlfriend(butch)]]. In short, lists are examples of recursive data structures: lists can be made out of lists. 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(zed), two copies of the list [2, [b, chopper]], and the variable Z. Note that the third (and the last) elements are lists which themselves contain lists (namely [b, chopper]).

Now for a very 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. Or more precisely, the tail is the list that remains when we take the first element away, i.e. the tail of a list is always a list again. For example, the head of

[mia, vincent, jules, yolanda]

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

[[], dead(zed), [2, [b, chopper]], [], Z, [2, [b, chopper]]]

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

Note that only non-empty lists have heads and tails. That is, the empty list contains no internal structure. For Prolog, the empty list [] is a special, particularly simple, list.

Prolog has a special inbuilt operator | which can be used to decompose a list into its head and tail. It is very 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 matching. 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 very 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(zed), [2, [b, chopper]], [], Z]. X = [] Y = [dead(zed),[2,[b,chopper]],[],_7800] Z = _7800 yes

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

But we can can do a lot more with |; it really is a very 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(zed), [2, [b, chopper]], [], Z]. X = [] Y = dead(zed) W = [[2,[b,chopper]],[],_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. 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, but we can in fact use it to split a list at any point. Left of the |, we just have to enumerate how many elements we want to take away from the beginning of the list, and right of the | we will then get what remains of the list. In this example, we also get the information that Prolog has bound Z to the internal variable _8327.

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(zed), [2, [b, chopper]], [], Z].

Now, we could find out like this:

?- [X1,X2,X3,X4 | Tail] = [[], dead(zed), [2, [b, chopper]], [], Z]. X1 = [] X2 = dead(zed) X3 = [2,[b,chopper]] 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(zed), [2, [b, chopper]], [], Z]. X = dead(zed) 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 it 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, chopper]]). 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(zed), [2, [b, chopper]], [], Z, [2, [b, chopper]]]. X = [[b,chopper]] Z = _10087 yes