4.3 Recursing down Lists

The member/2 predicate works by recursively working its way down a list, doing something to the head, and then recursively doing the same thing to the tail. Recursing down a list (or indeed, several lists) in this way is extremely common in Prolog; so common, in fact, that it is important that you really master the technique. So let’s look at another example.

When working with lists, we often want to compare one list with another, or to copy bits of one list into another, or to translate the contents of one list into another, or something similar. Here’s an example. Let’s suppose we need a predicate a2b/2 that takes two lists as arguments, and succeeds if the first argument is a list of a s, and the second argument is a list of b s of exactly the same length. For example, if we pose the following query

a2b([a,a,a,a],[b,b,b,b]).

we want Prolog to say yes. On the other hand, if we pose the query

?- a2b([a,a,a,a],[b,b,b]).

or the query

?- a2b([a,c,a,a],[b,b,5,4]).

we want Prolog to say no.

When faced with such tasks, often the best way to set about solving them is to start by thinking about the simplest possible case. Now, when working with lists, thinking about the simplest case often means thinking about the empty list, and it certainly means this here. After all: what is the shortest possible list of a s? It’s the empty list. Why? Because it contains no a s at all. And what is the shortest possible list of b s? Again, the empty list: no b s whatsoever in that. So the most basic information our definition needs to contain is

?- a2b([],[]).

This records the obvious fact that the empty list contains exactly as many a s as b s. But although obvious, this fact turns out to play an important role in our program, as we shall see.

So far so good: but how do we proceed? Here’s the idea: for longer lists, think recursively . So: when should a2b/2 decide that two non-empty lists are a list of a s and a list of b s of exactly the same length? Simple: when the head of the first list is an a , and the head of the second list is a b , and a2b/2 decides that the two tails are lists of a s and b s of exactly the same length! This immediately gives us the following rule:

a2b([a|Ta],[b|Tb]) :- a2b(Ta,Tb).

This says: the a2b/2 predicate should succeed if its first argument is a list with head a , its second argument is a list with head b , and a2b/2 succeeds on the two tails.

Now, this definition make good sense declaratively. It is a simple and natural recursive predicate, the base clause dealing with the empty list, the recursive clause dealing with non-empty lists. But how does it work in practice? That is, what is its procedural meaning? For example, if we pose the query

?- a2b([a,a,a],[b,b,b]).

Prolog will say yes, which is what we want — but why exactly does this happen?

Let’s work the example through. In this query, neither list is empty, so the fact does not help. Thus Prolog goes on to try the recursive rule. Now, the query does match the rule (after all, the head of the first list is a and the head of the second is b ) so Prolog now has a new goal, namely

?- a2b([a,a],[b,b]).

Once again, the fact does not help with this, but the recursive rule can be used again, leading to the following goal:

?- a2b([a],[b]).

Yet again the fact does not help, but the recursive rule does, so we get the following goal:

?- a2b([],[]).

At last we can use the fact: this tells us that, yes, we really do have two lists here that contain exactly the same number of a s and b s (namely, none at all). And because this goal succeeds, this means that the goal

?- a2b([a],[b]).

succeeds too. This in turn means that the goal

?- a2b([a,a],[b,b]).

succeeds, and thus that the original goal

?- a2b([a,a,a],[b,b,b]).

is satisfied.

We could summarise this process as follows. Prolog started with two lists. It peeled the head off each of them, and checked that they were an a and a b , respectively, as required. It then recursively analysed the tails of both lists. That is, it worked its way down both tails simultaneously, checking that at each stage the tails were headed by an a and a b . Why did the process stop? Because at each recursive step we had to work with shorter lists (namely the tails of the lists examined at the previous step) and eventually we ended up with empty lists. At this point, our rather trivial looking fact was able to play a vital role: it said yes. This halted the recursion, and ensured that the original query succeeded.

It’s is also important to think about what happens with queries that fail . For example, if we pose the query

?- a2b([a,a,a,a],[b,b,b]).

Prolog will correctly say no. Why? because after carrying out the peel-off-the-head-and-recursively-examine-the-tail process three times, it will be left with the query

?- a2b([a],[]).

But this goal cannot be satisfied. And if we pose the query

?- a2b([a,c,a,a],[b,b,5,4]).

after carrying out the peel-off-the-head-and-recursively-examine-the-tail process once, Prolog will have the goal

?- a2b([c,a,a],[b,5,4]).

and again, this cannot be satisfied.

Well, that’s how a2b/2 works in simple cases, but we haven’t exhausted its possibilities yet. As always with Prolog, it’s a good idea to investigate what happens when variables as used as input. And with a2b/2 something interesting happens: it acts as a translator, translating lists of a s to lists of b s, and vice versa. For example the query

?- a2b([a,a,a,a],X).

yields the response

X = [b,b,b,b].

That is, the list of a s has been translated to a list of b s. Similarly, by using a variable in the first argument position, we can use it to translate lists of b s to lists of a s:

?- a2b(X,[b,b,b,b]).

X = [a,a,a,a].

And of course, we can use variables in both argument positions:

?- a2b(X,Y).

Can you work out what happens in this case?

To sum up: a2b/2 is an extremely simple example of a program that works by recursing its way down a pair of lists. But don’t be fooled by its simplicity: the kind of programming it illustrates is fundamental to Prolog. Both its declarative form (a base clause dealing with the empty list, a recursive clause dealing with non-empty lists) and the procedural idea it trades on (do something to the heads, and then recursively do the same thing to the tails) come up again and again in Prolog programming. In fact, in the course of your Prolog career, you’ll find that you’ll write what is essentially the a2b/2 predicate, or a more complex variant of it, many times over in many different guises.