Why is SWI-Prolog only giving one solution?

Question

I'll be honest, I'm a Prolog newbie, so please excuse my ignorance.

I have a simple predicate to count the occurences of an atom in a list, as follows:

count(L, B, C) :-
    L = [], C = 0, !;
    L = [H|T], H \= B, count(T, B, C), !;
    L = [H|T], H = B, count(T, B, C1), C is C1 + 1.

The following queries return the correct results:

?- count([a, c, g, t], a, C).
C = 1.

?- count([a, c, g, t], c, C).
C = 1.

?- count([a, c, g, t], g, C).
C = 1.

?- count([a, c, g, t], t, C).
C = 1.

However, if I try to find all possible solutions, it only gives one.

?- count([a, c, g, t], X, C).
X = a,
C = 1.

How do I get it to give all the solutions? I though it could have something to do with the cut operator, but removing it doesn't seem to work either.

Answer 1

The cuts are indeed one problem: Try for example the most general query

?- count(Ls, L, C).

and see that it yields only a single solution, although there clearly should be infinitely many because the first argument can be a list of arbitrary length. So first remove all cuts. The other problem is (\=)/2, which is not a true relation: It is only sound if its arguments are ground. Instead of (\=)/2, use the more general predicate dif/2, which is available in SWI-Prolog as well as other systems and constrains its arguments to be different terms. Your predicate will then work in all directions.

EDIT: I expand on the "usable in all directions" point. Consider the following version of list_term_count/3, which relates a list to the number of occurrences of a term in that list, using clpfd constraints in addition to dif/2:

list_term_count([], _, 0).
list_term_count([L|Ls], L, N) :-
        list_term_count(Ls, L, N0),
        N #= N0 + 1.
list_term_count([L|Ls], E, N) :-
        dif(L, E),
        list_term_count(Ls, E, N).

We can use it in the most general way imaginable, which is leaving all arguments unspecified, and obtain correct answers:

?- list_term_count(Ls, E, N).
Ls = [],
N = 0 ;
Ls = [E],
N = 1 .

To fairly enumerate all solutions, we can use length/2:

?- length(Ls, _), list_term_count(Ls, E, N).
Ls = [],
N = 0 ;
Ls = [E],
N = 1 ;
Ls = [_G167],
N = 0,
dif(_G167, E) .

Notice the dif/2 constraint which occurs as a residual goal, and which constrains the list's element to be distinct from E when N is 0. This is how we can express an infinite set of terms that is not restricted in any other way except for being different from E.

Any other instantiation pattern is also admissible. For example:

?- list_term_count([a], E, N).
E = a,
N = 1 ;
N = 0,
dif(E, a).

Or for example:

?- list_term_count([X], a, N).
X = a,
N = 1 ;
N = 0,
dif(X, a).

This generality is one of the benefits of using pure monotonic predicates in your programs. Using pure goals also allows us to quite freely reorder them.