Count number of occurrences in a list in Prolog

Question

I write this little code in Prolog that counts the number of occurrences of some term in a list. It works, but it is not tail recursive (so no recursive optimization).

How could I write the same program but with tail recursion?

counter(T,[],X) :- 
   X is 0.
counter(T,[T|D],X1) :-
   !,
   counter(T,D,X),
   X1 is X+1.
counter(T,[_|D],X1) :-
   counter(T,D,X1).

I think that I should use an accumulator but I've no idea how to implement. Any help?

Answer 1

Program readability

Indentation is welcome even in Prolog, to make programs understandable:

counter(T, [], X) :- 
    X is 0.
counter(T, [T|D], X1) :-
    !,
    counter(T, D, X),
    X1 is X+1.
counter(T, [_|D], X1) :-
    counter(T, D, X1).

Variable naming

It is also a good practice to properly name your variables, here we could use:

counter(Elem, [], Result) :- 
    Result is 0.
counter(Elem, [Elem|Tail], Result) :-
    !,
    counter(Elem, Tail, NewResult),
    Result is NewResult + 1.
counter(Elem, [_|Tail], Result) :-
    counter(Elem, Tail, Result).

Singleton variables

It's also a good practice to give a special name to singleton variables (prefixing them with a _):

counter(_Elem, [], Result) :- 
    Result is 0.
counter(Elem, [Elem|Tail], Result) :-
    !,
    counter(Elem, Tail, NewResult),
    Result is NewResult + 1.
counter(Elem, [_Head|Tail], Result) :-
    counter(Elem, Tail, Result).

Head unification

You can take advantage of the fact that Prolog uses unification in the heads of the clauses to rewrite your first clause:

counter(_Elem, [], Result) :- 
    Result is 0.

can become

counter(_Elem, [], 0).

Those clauses that consist only of a head are also called facts

Tail Recursion

The clause you have to change is the middle clause: the recursive call is not at the end of the predicate in it. Sadly it will impact the other clauses as well, let's see why.

To get tail recursion, we use an idiom called an accumulator: an additional argument that will hold intermediate results during the recursion. For example here:

counter(Elem, List, Result) :-
    counter(Elem, List, 0, Result).

counter(_Elem, [], Acc, Acc).
counter(Elem, [Elem|Tail], Acc, Result) :-
    !,
    NewAcc is Acc + 1,
    counter(Elem, Tail, NewAcc, Result).
counter(Elem, [_Head|Tail], Acc, Result) :-
    counter(Elem, Tail, Acc, Result).

As you can see we have now a predicate counter/3 that only calls counter/4 and the latter tracks the intermediate result in the Acc variable.

Getting a more general program

A problem remaining in your program is that you use is/2. That doesn't give you a general program: you can't call counter(X, [1, 2, 3, 4], R) and get an answer. To correct that you can use constraint programming:

:- use_module(library(clpfd)).

counter(Elem, List, Result) :-
    counter(Elem, List, 0, Result).

counter(_Elem, [], Acc, Acc).
counter(Elem, [Elem|Tail], Acc, Result) :-
    NewAcc #= Acc + 1,
    counter(Elem, Tail, NewAcc, Result).
counter(Elem, [Head|Tail], Acc, Result) :-
    Elem #\= Head,
    counter(Elem, Tail, Acc, Result).

Test:

?- counter(X, [1, 2, 3, 4], R).
X = R, R = 1 ;
X = 2,
R = 1 ;
X = 3,
R = 1 ;
X = 4,
R = 1 ;
R = 0,
X in inf..0\/5..sup.

Answer 2

Adding an accumulator can be done with a standard process:

counter( T , List , X ) :-
  counter( T , List , 0 , X ) .

counter( _ , [] , Acc , Acc ) .
counter( T , [T|D] , SoFar , Result ) :-
  Updated is SoFar+1 ,
  ! ,
  counter(T,D,Updated,Result) .
counter( T , [_|D] , SoFar , Result ) :-
  counter( T , D , SoFar , Result ) .

Answer 3

We can define counter/3 based on meta-predicate tcount/3 and reified term-equality (=)/3:

counter(E,Xs,N) :- 
   tcount(=(E),Xs,N).

Sample uses:

?- counter(a,[a,b,a,b,a,c],N).
N = 3.

?- counter(E,[a,b,a,b,a,c],N).
  N = 3,     E=a
; N = 2,               E=b
; N = 1,                         E=c
; N = 0, dif(E,a), dif(E,b), dif(E,c).

How about more general queries? Do we get logically sound answers?

?- counter(X,[A,B,C],2).
      A=X ,     B=X , dif(C,X)
;     A=X , dif(B,X),     C=X
; dif(A,X),     B=X ,     C=X
; false.

Yes. Let's generalize above query and compare the solution sets (and see monotonicity at work)!

?- counter(X,[A,B,C],N).
  N = 3,     A=X ,     B=X ,     C=X
; N = 2,     A=X ,     B=X , dif(C,X)
; N = 2,     A=X , dif(B,X),     C=X
; N = 1,     A=X , dif(B,X), dif(C,X)
; N = 2, dif(A,X),     B=X ,     C=X
; N = 1, dif(A,X),     B=X , dif(C,X)
; N = 1, dif(A,X), dif(B,X),     C=X
; N = 0, dif(A,X), dif(B,X), dif(C,X).