A function that counts the number '1's, '2's and '3's in a list, with count represented as, for example, s(s(s(0))) = 3

Question

I want to create a predicate over the alphabet {1,2,3}, f/4(N1,N2,N3,L), such that N1, N2 and N3 are a count of the number of times a 1, a 2, and a 3 appeared in a list, respectively. The predicate should operate as the following:

?- f(N1,N2,N3,[1,2,3,3]).
N1 = s(0), N2 = s(0), N3 = s(s(0))

?- f(N1,N2,N3,L).
N1 = N2, N2 = N3, N3 = 0, L = [] ;
N1 = s(0), N2 = N3, N3 = 0, L = [1] ;
N1 = N3, N3 = 0, N2 = s(0), L = [2] ;
N1 = N2, N2 = 0, N3 = s(0), L = [3] ;
N1 = s(s(0)), N2 = N3, N3 = 0, L = [1,1] ;
...

I have come up with the following solution:

f(0,0,0,[]).
f(s(N1),N2,N3,[1|Xs]) :- f(N1,N2,N3,Xs).
f(N1,s(N2),N3,[2|Xs]) :- f(N1,N2,N3,Xs).
f(N1,N2,succ(N3),[3|Xs]) :- f(N1,N2,N3,Xs).

This solution works for the first query, however, for the second query, it outputs the following:

?- f(N1,N2,N3,L).
N1 = N2, N2 = N3, N3 = 0, L = [] ;
N1 = s(0), N2 = N3, N3 = 0, L = [1] ;
N1 = s(s(0)), N2 = N3, N3 = 0, L = [2] ;
N1 = s(s(s(0))), N2 = N3, N3 = 0, L = [3] ;
N1 = s(s(s(s(0)))), N2 = N3, N3 = 0, L = [1,1] ;

This seems to be an unfair enumeration, how do I fix this?

Answer 1

Due to the order of the clauses in your solution, each recursive call choose to increment N1, before trying to increment N2 or N3 (which are never incremented at all).

A possible solution is:

f(0, 0, 0, []).
f(N1, N2, N3, [X|Xs]) :-
   f(M1, M2, M3, Xs),
   member(X - [N1, N2, N3],
         [1 - [s(M1), M2, M3],
          2 - [M1, s(M2), M3],
          3 - [M1, M2, s(M3)]]).

Here are some examples:

?- f(N1, N2, N3, [1,2,3,3,1,1,1]).
N1 = s(s(s(s(0)))),
N2 = s(0),
N3 = s(s(0)) ;
false.

?- forall( limit(20, f(N1,N2,N3,L)), writeln(L -> [N1,N2,N3]) ).
[] -> [0,0,0]
[1] -> [s(0),0,0]
[2] -> [0,s(0),0]
[3] -> [0,0,s(0)]
[1,1] -> [s(s(0)),0,0]
[2,1] -> [s(0),s(0),0]
[3,1] -> [s(0),0,s(0)]
[1,2] -> [s(0),s(0),0]
[2,2] -> [0,s(s(0)),0]
[3,2] -> [0,s(0),s(0)]
[1,3] -> [s(0),0,s(0)]
[2,3] -> [0,s(0),s(0)]
[3,3] -> [0,0,s(s(0))]
[1,1,1] -> [s(s(s(0))),0,0]
[2,1,1] -> [s(s(0)),s(0),0]
[3,1,1] -> [s(s(0)),0,s(0)]
[1,2,1] -> [s(s(0)),s(0),0]
[2,2,1] -> [s(0),s(s(0)),0]
[3,2,1] -> [s(0),s(0),s(0)]
[1,3,1] -> [s(s(0)),0,s(0)]
true.