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

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 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.