Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Prolog list membership, multiple results returned

I have a standard procedure for determining membership of a list:

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

What I don't understand is why when I pose the following query:

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

The result is

True;  
False.

I would have thought that on satisfying the goal using the first rule (as a is the head of the list) True would be returned and that would be the end of if. It seems as if it is then attempting to satisfy the goal using the second rule and failing?

Prolog interpreter is SWI-Prolog.

like image 716
Justin Avatar asked Jan 30 '13 00:01

Justin


3 Answers

Let's consider a similar query first: [Edit: Do this without adding your own definition ; member/2 is already defined]

?- member(a,[b,a]).
   true.

In this case you get the optimal answer: There is exactly one solution. But when exchanging the elements in the list we get:

?- member(a,[a,b]).
   true
;  false.

Logically, both are just the affirmation that the query is true.

The reason for the difference is that in the second query the answer true is given immediately upon finding a as element of the list. The remaining list [b] does not contain a fitting element, but this is not yet examined. Only upon request (hitting SPACE or ;) the rest of the list is tried with the result that there is no further solution.

Essentially, this little difference gives you a hint when a computation is completely finished and when there is still some work to do. For simple queries this does not make a difference, but in more complex queries these open alternatives (choicepoints) may accumulate and use up memory.

Older toplevels always asked if you want to see a further solution, even if there was none.

Edit:

The ability to avoid asking for the next answer, if there is none, is extremely dependent on the very implementation details. Even within the same system, and the same program loaded you might get different results. In this case, however, I was using SWI's built-in definition for member/2 whereas you used your own definition, which overwrites the built-in definition.

SWI uses the following definition as built-in which is logically equivalent to yours but makes avoiding unnecessary choice points easier to SWI — but many other systems cannot profit from this:

member(B, [C|A]) :-
   member_(A, B, C).

member_(_, A, A).
member_([C|A], B, _) :-
   member_(A, B, C).

To make things even more complex: Many Prologs have a different toplevel that does never ask for further answers when the query does not contain a variable. So in those systems (like YAP) you get a wrong impression.

Try the following query to see this:

?- member(X,[1]).
   X = 1.

SWI is again able to determine that this is the only answer. But YAP, e.g., is not.

like image 138
false Avatar answered Oct 21 '22 17:10

false


Are you using the ";" operator after the first result then pushing return? I believe this is asking the query to look for more results and as there are none it is coming up as false.

like image 33
Dan Avatar answered Oct 21 '22 17:10

Dan


Do you know about Prolog's cut - !?

If you change member(X, [X|_]). to member(X, [X|_]) :- !. Prolog will not try to find another solution after the first one.

like image 43
Sergii Dymchenko Avatar answered Oct 21 '22 18:10

Sergii Dymchenko