4.2 Member

It’s time to look at our first example of a recursive Prolog program for manipulating lists. One of the most basic things we would like to know is whether something is an element of a list or not. So let’s write a program that, when given as inputs an arbitrary object X and a list L , tells us whether or not X belongs to L . The program that does this is usually called member , and it is the simplest example of a Prolog program that exploits the recursive structure of lists. Here it is:

member(X,[X|T]).
member(X,[H|T]) :- member(X,T).

That’s all there is to it: one fact (namely member(X,[X|T]) ) and one rule (namely member(X,[H|T])  :-  member(X,T) ). But note that the rule is recursive (after all, the functor member occurs in both the rule’s head and body) and it is this that explains why such a short program is all that is required. Let’s take a closer look.

We’ll start by reading the program declaratively. And read this way, it is obviously sensible. The first clause (the fact) simply says: an object X is a member of a list if it is the head of that list. Note that we used the built-in | operator to state this (simple but important) principle about lists.

What about the second clause, the recursive rule? This says: an object X is member of a list if it is a member of the tail of the list. Again, note that we used the | operator to state this principle.

Now, clearly this definition makes good declarative sense. But does this program actually do what it is supposed to do? That is, will it really tell us whether an object X belongs to a list L ? And if so, how exactly does it do this? To answer such questions, we need to think about its procedural meaning. Let’s work our way through a few examples.

Suppose we posed the following query:

?- member(yolanda,[yolanda,trudy,vincent,jules]).

Prolog will immediately answer yes. Why? Because it can unify yolanda with both occurrences of X in the first clause (the fact) in the definition of member/2 , so it succeeds immediately.

Next consider the following query:

?- member(vincent,[yolanda,trudy,vincent,jules]).

Now the first rule won’t help ( vincent and yolanda are distinct atoms) so Prolog goes to the second clause, the recursive rule. This gives Prolog a new goal: it now has to see if

?- member(vincent,[trudy,vincent,jules]).

Once again the first clause won’t help, so Prolog goes (again) to the recursive rule. This gives it a new goal, namely

?- member(vincent,[vincent,jules]).

This time, the first clause does help, and the query succeeds.

So far so good, but we need to ask an important question. What happens when we pose a query that fails ? For example, what happens if we pose the query

?- member(zed,[yolanda,trudy,vincent,jules]).

Now, this should obviously fail (after all, zed is not on the list). So how does Prolog handle this? In particular, how can we be sure that Prolog really will stop , and say no , instead going into an endless recursive loop?

Let’s think this through systematically. Once again, the first clause cannot help, so Prolog uses the recursive rule, which gives it a new goal

?- member(zed,[trudy,vincent,jules]).

Again, the first clause doesn’t help, so Prolog reuses the recursive rule and tries to show that

?- member(zed,[vincent,jules]).

Similarly, the first rule doesn’t help, so Prolog reuses the second rule yet again and tries the goal

?- member(zed,[jules]).

Again the first clause doesn’t help, so Prolog uses the second rule, which gives it the goal

?- member(zed,[]).

And this is where things get interesting. Obviously the first clause can’t help here. But note: the recursive rule can’t do anything more either . Why not? Simple: the recursive rule relies on splitting the list into a head and a tail, but as we have already seen, the empty list can’t be split up in this way. So the recursive rule cannot be applied either, and Prolog stops searching for more solutions and announces no. That is, it tells us that zed does not belong to the list, which is just what it ought to do.

We could summarise the member/2 predicate as follows. It is a recursive predicate, which systematically searches down the length of the list for the required item. It does this by stepwise breaking down the list into smaller lists, and looking at the first item of each smaller list. This mechanism that drives this search is recursion, and the reason that this recursion is safe (that is, the reason it does not go on forever) is that at the end of the line Prolog has to ask a question about the empty list. The empty list cannot be broken down into smaller parts, and this allows a way out of the recursion.

Well, we’ve now seen why member/2 works, but in fact it’s far more useful than the previous example might suggest. Up till now we’ve only been using it to answer yes/no questions. But we can also pose questions containing variables. For example, we can have the following dialog with Prolog:

?- member(X,[yolanda,trudy,vincent,jules]).

X = yolanda ;

X = trudy ;

X = vincent ;

X = jules ;

no.

That is, Prolog has told us what every member of a list is. This is an extremely common use of member/2 . In effect, by using the variable we are saying to Prolog: “Quick! Give me some element of the list!”. In many applications we need to be able to extract members of a list, and this is the way it is typically done.

One final remark. The way we defined member/2 above is certainly correct, but in one respect it is a little messy.

Think about it. The first clause is there to deal with the head of the list. But although the tail is irrelevant to the first clause, we named the tail using the variable T . Similarly, the recursive rule is there to deal with the tail of the list. But although the head is irrelevant here, we named it using the variable H . These unnecessary variable names are distracting: it’s better to write predicates in a way that focuses attention on what is really important in each clause, and the anonymous variable gives us a nice way of doing this. That is, we can rewrite member/2 as follows:

member(X,[X|_]).
member(X,[_|T]) :- member(X,T).

This version is exactly the same, both declaratively and procedurally. But it’s just that little bit clearer: when you read it, you are forced to concentrate on what is essential.