I want to count the occurrences of an element in a list

Question

I want to count the occurrences of an element in a list, and if there is one then the predicate unique would be true, else false. However, if the element occurs more than once, Prolog finds it true. I don't know what to do...

count([], X, 0).
count([X|T], X, Y) :- count(T, X, Z), Y is 1+Z, write(Z).
count([_|T], X, Z) :- count(T, X, Z).

unique(St, [Y|RestList]) :- count([Y|RestList], St, N), N =:= 1.

Answer 1

The solution works as far as the first argument is a ground list. In some other cases, it is incorrect:

?- count([E], a, 0).
   false.

Here we ask

How must the element E of a list of length 1 look like such that the list contains 0 occurences of a?

And in fact there are answers to this, like E = b or E = c:

?- count([b],a,0).
   true.
?- count([c],a,0).
   true.

For this reason Prolog's answer was incomplete. It should have said, yes. But how?

count([], _, 0).
count([E|Es], F, N0) :-
   count(Es, F, N1),
   if_(E = F, D = 1, D = 0),
   N0 is N1+D.

This uses if_/3 and (=)/3.

?- length(Xs, I), count_dif(Xs, a, N).
   Xs = [], I = N, N = 0
;  Xs = [a], I = N, N = 1
;  Xs = [_A], I = 1, N = 0, dif(_A, a)
;  Xs = [a, a], I = N, N = 2
;  Xs = [_A, a], I = 2, N = 1, dif(_A, a)
;  Xs = [a, _A], I = 2, N = 1, dif(_A, a)
;  Xs = [_A, _B], I = 2, N = 0, dif(_A, a), dif(_B, a)
; ... .

To further improve this, we might use library(clpfd) as it is available in SICStus, YAP, and SWI.

:- use_module(library(clpfd)).

count([], _, 0).
count([E|Es], F, N0) :-
   N0 #>= 0,
   if_(E = F, D = 1, D = 0),
   N0 #= N1+D,
   count(Es, F, N1).

Now even the following terminates:

?- count([a,a|_], a, 1).
   false.
?- N #< 2, count([a,a|_], a, N).
   false.

Answer 2

Using your own clauses, I just optimize a little the program:

• replace singleton variables by anonymous variable
• Add a cut on the second clause of the count predicate
• Delete second condition of the unique clause.

This is the program now:

count([],_,0).

count([X|T],X,Y):- !, count(T,X,Z), Y is 1+Z.

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

unique(St,L):- count(L,St,1).

consult:

?- count([2,3,4,3], 3,N).
N = 2.

?- unique(3, [2,3,4,5]).
true.