Prolog members of lists

Question

Prolog newbie here who would like to know why these rules cannot stand on their own if I want to find out if something is the member of a list.

member(X, [X|_]).

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

If I ask the following for the above rules:

member(will, [anna, eddie, pat, will, marjorie, donna]).

I get true, however if I remove:

member(X, [X|_]).

Just leaving the second rule, I get false. Why would this be if the second rule states that "X is a member of the list if X is a member of the tail of the list"

"will" is a member of the tail of this list.

And, why can

member(X, [X|_]).

stand alone and tell me when X is the head of the list (when the second rule cannot)?

Thank you.

If the first clause `member(X, [X|_]).` doesn't exist, ask yourself the question, "At what point will `member(X, Y)` in the second clause ever become true (succeed)?". Remember: it's a recursive query. — lurker, May 05 '14 at 13:18
Consider [`memberd/2`](http://stackoverflow.com/questions/21971037/prolog-removing-unique-elements-only/21971885#21971885) which is essentially the same but with no redundant answers. — false, May 05 '14 at 16:04

Shevliaskovic · Accepted Answer · 2014-05-05T13:25:44.023

If you only have member(X, [X|_]). and you execute this query: member(will, [will,anna]).

You will get true. because according to your rule, the X, which is will, is the head of the list.

But if you only have that rule and you execute member(anna, [will,anna])., you will get false because anna is not the head of your list.

Let's see your second rule.

You create your program as member(X, [_|Y]) :- member(X,Y).

You execute the query member(will, [anna, eddie, pat, will, marjorie, donna]).

And this is what Prolog sees:

take the list and remove the head. Do the same for the rest of the list, until the tail is empty.

You get false. because there aren't any elements left in your list.

Your problem is that you don't check if X is a member of your list. You could as well rename that rule as removehead(X,[_|Y]):-removehead(X,Y).

Sergey Kalinichenko · Answer 2 · 2014-05-05T13:38:48.217

Just leaving the second rule, I get false.

The reason the rule with no base case fails is that when the list is down to a single item, there is no rule to unify with its right side, when the list becomes empty.

You can play it out on a piece of paper using a shorter list:

Start with member(will, [anna, will]).
This unifies with the rule, unifying anna to _, and keeping [will] at Y
This unifies with the rule again, unifying will to _ and keeping [] at Y
Now that Prolog tries member(will, []) the rule no longer unifies with it, because member(X, [_|Y]) requires the second argument to be a list with at least one item.
Once this last unification fails, the failure propagates up the chain, resulting in returning a false back to the top caller.

And, why can member(X, [X|_]). stand alone and tell me when X is the head of the list

This is because the rule succeeds immediately, without having to unify with any other rule on the right.

In general, when you deal with recursive processing of data structures, you need to look for two things:

The base case, which tells what to do in the simplest of the cases or when the recursive data structure is reduced to a degenerate case (e.g. an empty list, a single-node "leaf" tree, and so on).
The reduction step, which tells how to bring the problem closer to the base case.

Treating the base case alone will sometimes give you results; treating the reduction step alone never gives you right results, because it does all the reduction work for nothing.

This bit in your answer "The reason the rule with no base case fails is that when the list is down to a single item, there is no rule to unify with it" is incorrect. A single item list does unify with the rule head. — Paulo Moura, May 05 '14 at 13:25
@PauloMoura I am sorry I wasn't clear on this - I meant that when the list that comes into the rule has one item, noting unifies with the right side of the rule. I edited the answer to clarify. Thanks! — Sergey Kalinichenko, May 05 '14 at 13:40

score 2 · Answer 3 · answered May 05 '14 at 13:11

member(X, [_|Y]) (1) only matches lists of the form [_|Y], and (2) never looks at the actual elements. Try tracing the execution:

?- trace.
true.

[trace]  ?- member(foo, [foo, bar]).
   Call: (6) member(foo, [foo, bar]) ? creep
   Call: (7) member(foo, [bar]) ? creep
   Call: (8) member(foo, []) ? creep
   Fail: (8) member(foo, []) ? creep
   Fail: (7) member(foo, [bar]) ? creep
   Fail: (6) member(foo, [foo, bar]) ? creep
false.

As was to be expected, your version of member just skips over the element because it wants to look at the tail only, until it hits [] which does not match the pattern in the head.

The other version, member(X, [X|_]) can match the head per definition. It looks at the head and unifies it with the item you're looking for.

Prolog members of lists

3 Answers3