prolog: fixing multiple answers (using cut?)

Question

i'm counting number of instances in a list...

count(_,[],N,N).
count(Elem,[Elem|List],N,M) :- !, N1 is N+1, count(Elem,List,N1,M). 
count(Elem,[_|List],N,M) :- count(Elem,List,N,M).

So, i wrote this up two ways in prolog, and the first one works (above), but i was curious to know why the second doesnt (or rather, will give me multiple answers - only the first of which is correct) why is this?

many thanks

count(Z,X,R) :- count2(Z,X,R,0).
count2(W,[H|T],L,A):- (W == H), Lnew is A+1, count2(W,T,L,Lnew).
count2(W,[H|T],L,A):- count2(W,T,L,A).
count2(W,[],A,A).

Answer 1

Your question includes the answer...the cut. The cut always succeeds and has the side effect of "cutting off" the derivation tree. Basically you cannot backtrack pass a cut.

The first example will execute the cut if the goal unifies with the second rule. In a sense, that choice becomes fixed. If there is failure or backtracking after it does not bacjtrack over the cut thus eliminating multiple answers. The cut is useful when the answers are mutually exclusive. That is, when you find the first answer no others will make sense.

Answer 2

got it!

here is a solution that works:

count(Z,X,R) :- count2(Z,X,R,0).
count2(W,[H|T],L,A):- (W == H), !, Lnew is A+1, count2(W,T,L,Lnew).
count2(W,[H|T],L,A):- count2(W,T,L,A).
count2(W,[],A,A).

Thanks Vincent - you made me revisit the cut!

Answer 3

The reason why your second attempt produces multiple solutions is that the second count2 clause does not prevent W and H from taking the same values. So even if the first clause of count2 succeeds, it can backtrack and succeed again on the the second clause.

You can fix this by using a cut as Vincent Ramdhanie says, or if you prefer to avoid the use of a cut you can just add an explicit check in the second clause to prevent W and H from unifying, like this:

count(Z,X,R) :- count2(Z,X,R,0).
count2(W,[W|T],L,A):- Lnew is A+1, count2(W,T,L,Lnew).
count2(W,[H|T],L,A):- W \= H count2(W,T,L,A).
count2(_,[],A,A).

Also note that the first count2 clause now uses implicit unification. Rather than an explicit check. This is a bit shorter and easier to read in my opinion. Unless of course there was a reason why you were using equality rather than unification.