| << Prev | - Up - | Next >> |
Member works by recursively working 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 idea. So let's look at another example of the technique at work.
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 as, and the second argument is a list of bs 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 as? Why, the empty list: it contains no as at all! And what is the shortest possible list of bs? Again, the empty list: no bs 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 as as bs. But although obvious, this fact turns out to play a very 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 as and a list of bs 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 as and bs 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, by 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 in 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 as and bs (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 summarize 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 as required. It then recursively analyzed the tails of both lists. That is, it worked 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 as to lists of bs, 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 as has been translated to a list of bs. Similarly, by using a variable in the first argument position, we can use it to translate lists of bs to lists of as:
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.
| << Prev | - Up - | Next >> |