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

user_12388634 0
Viewed 62

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?

prolog
1 Answers

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