count successive occurrences of number in Prolog

Question

Hello I am trying to make a program in Prolog that given a list it counts the occurrences of each successive element in the list as follows:

count(1,[1,1,1,2,2,2,3,1,1],0,X)

the result would be X=[ [1,3],[2,3],[3,1][1,2] ] aka each sublist is [element,occurrences]

In my case i believe there is something wrong with the base case but I cannot solve it. Can you help me?

%append an element to a list
append([ ],Y,Y).
append([X|Xs],Ys,[X|Zs]):-append(Xs,Ys,Zs).

%c is the counter beginning with 0 
count(_,[],_,[]).
count(X,[X],C,[L]):-count(X,[],C,[L|[X,C]]).

%increase counter
count(X,[X|Tail],C,L):-Z is C+1,count(X,Tail,Z,L).
count(X,[Head|Tail],C,[L]):-append(L,[X,C],NL),count(Head,Tail,1,NL).

Answer 1

Here's another try of doing run-length encoding, based on clpfd!

:- use_module(library(clpfd)).

Based on if_/3 and (=)/3, we define list_rle/2:

list_rle([],[]).
list_rle([X|Xs],[N*X|Ps]) :-
   list_count_prev_runs(Xs,N,X,Ps).

list_count_prev_runs(Es,N,X,Ps) :-
   N #> 0,
   N #= N0+1,
   list_count_prev_runs_(Es,N0,X,Ps).

list_count_prev_runs_([],0,_,[]).
list_count_prev_runs_([E|Es],N,X,Ps0) :-
   if_(X=E, 
       list_count_prev_runs(Es,N,X,Ps0),
       (N = 0, Ps0 = [M*E|Ps], list_count_prev_runs(Es,M,E,Ps))).

Sample queries:

• encode/decode #1

  ?- list_rle([a,a,b,c,c,c,d,e,e],Ys).
  Ys = [2*a,1*b,3*c,1*d,2*e].
  
  ?- list_rle(Xs,[2*a,1*b,3*c,1*d,2*e]).
    Xs = [a,a,b,c,c,c,d,e,e]
  ; false.
  

• encode/decode #2

  ?- dif(A,B),dif(B,C),dif(C,D),dif(D,E), list_rle([A,A,B,C,C,C,D,E,E],Ys).
  Ys = [2*A,1*B,3*C,1*D,2*E], dif(A,B), dif(B,C), dif(C,D), dif(D,E).
  
  ?- list_rle(Xs,[2*A,1*B,3*C,1*D,2*E]).
    Xs = [A,A,B,C,C,C,D,E,E], dif(A,B), dif(B,C), dif(C,D), dif(D,E)
  ; false.
  

• How about something a little more general?

  ?- list_rle([A,B,C,D],Xs).
    Xs = [4*A            ],     A=B ,     B=C ,     C=D
  ; Xs = [3*A,        1*D],     A=B ,     B=C , dif(C,D)
  ; Xs = [2*A,    2*C    ],     A=B , dif(B,C),     C=D
  ; Xs = [2*A,    1*C,1*D],     A=B , dif(B,C), dif(C,D)
  ; Xs = [1*A,3*B        ], dif(A,B),     B=C ,     C=D
  ; Xs = [1*A,2*B,    1*D], dif(A,B),     B=C , dif(C,D)
  ; Xs = [1*A,1*B,2*C    ], dif(A,B), dif(B,C),     C=D   
  ; Xs = [1*A,1*B,1*C,1*D], dif(A,B), dif(B,C), dif(C,D).
  

Answer 2

Why you are stating a relation between two lists with a predicate having 4 arguments ? Let's try to proceed step by step.

An empty list gives an empty list, an element counted gets incremented, otherwise, start counting...

count([],[]).
count([X|T],[[X,C1]|R]) :- count(T,[[X,C]|R]), !, C1 is C+1.
count([X|T],[[X,1]|R]) :- count(T,R).

?- count([1,1,1,2,2,2,3,1,1],R).
R = [[1, 3], [2, 3], [3, 1], [1, 2]].

so easy (of course, assuming X=[ [1,3],[2,3],[1,3][1,2] ] it's a typo ...)

Answer 3

Another solution (tail recursive) is this:

run_length_encode( Xs , Ys ) :- % to find the run length encoding of a list ,
  rle( Xs , 1 , Ys ) .          % - just invoke the helper

rle( []       , _ , []    ) .     % the run length encoding of the empty list is the empty list
rle( [A]      , N , [X:N] ) .     % A list of length 1 terminates the run: move the run length to the result
rle( [A,A|Xs] , N , Ys    ) :-    % otherwise, if the run is still going
  N1 is N+1 ,                     % - increment the count, 
  rle( [A|Xs] , N1 , Ys )         % - and recurse down
  .                               %
rle( [A,B|Xs] , N , [A:N|Ys] ) :- % otherwise, if the run has ended
  A \= B ,                        % - we have a break
  rle( [B|Xs] , 1 , Ys )          % - add the completed run length to the result and recurse down
  .                               %

Answer 4

If we skip usage of "is" we can have a solution like:

precondition(Clause):-
  Clause =.. [_|ARGS],
  ( maplist(var,ARGS) -> true; Clause ).

count( [], [] ).

count( [X], [(X,1)] ) :- !.

count( [H|Q], [(H,1),(HR,NR)|QR] ) :-
   count( Q, [(HR,NR)|QR] ),
   H \= HR,
   !.

count( [H|Q], [(H,NR)|QR] ) :-
   precondition( succ(N,NR) ),
   count( Q, [(H,N)|QR] ), 
   succ(N,NR).

that allows not only the usual query:

[debug]  ?- count([1,1,1,2,2,2,3,1,1],R).
R = [ (1, 3), (2, 3), (3, 1), (1, 2)].

but also the reverse one:

[debug]  ?- count(X, [ (1, 3), (2, 3), (3, 1), (1, 2)] ).
X = [1, 1, 1, 2, 2, 2, 3, 1, 1].

Answer 5

We can tackle your problem and preserve logical-purity!

In the following let Xs be [1,1,1,2,2,2,3,1,1], the list you used in your question.

First, we map Xs to a list of lists Yss such that every list Ys in Yss only contains equal elements taken from Xs. We do that by using the meta-predicate splitlistIfAdj/3 in tandem with the reified inequality predicate dif/3:

?- Xs = [1,1,1,2,2,2,3,1,1], splitlistIfAdj(dif,Xs,Yss).
Xs  = [ 1,1,1,  2,2,2,  3,  1,1 ],
Yss = [[1,1,1],[2,2,2],[3],[1,1]].

Second, we map the list of lists Yss to Zss. Each item in Zss has the form [Element,Amount]. Looking at the answer of above query, we see that all we need to do is map [1,1,1] to [1,3], [2,2,2] to [2,3], [3] to [3,1], and [1,1] to [1,2]. run_pair/2 does exactly that:

run_pair(Ys,[Element,Amount]) :-
   Ys = [Element|_],
   length(Ys,Amount).

Let's use run_pair/2 to map every item of Yss, with the help of meta-predicate maplist/3:

?- Yss = [[1,1,1],[2,2,2],[3],[1,1]], maplist(run_pair,Yss,Zss).
Yss = [[1,1,1],[2,2,2],[3]  ,[1,1]],
Zss = [[1,3],  [2,3],  [3,1],[1,2]].

Done! Time to put it all together:

count(Xs,Zss) :-
   splitlistIfAdj(dif,Xs,Yss),
   maplist(run_pair,Yss,Zss).

Let's see if above query still works :)

?- count([1,1,1,2,2,2,3,1,1],Zss).
Zss = [[1,3],[2,3],[3,1],[1,2]].      % succeeds deterministically

As the implementation of count/2 is monotone, we get logically sound answers even when working with non-ground terms. Let's see that in action!

?- Xs = [A,B,C,D], count(Xs,Zss).
Xs = [D,D,D,D],     A=B,      B=C ,     C=D , Zss = [                  [D,4]] ;
Xs = [C,C,C,D],     A=B,      B=C , dif(C,D), Zss = [            [C,3],[D,1]] ;
Xs = [B,B,D,D],     A=B,  dif(B,C),     C=D , Zss = [      [B,2],      [D,2]] ;
Xs = [B,B,C,D],     A=B,  dif(B,C), dif(C,D), Zss = [      [B,2],[C,1],[D,1]] ;
Xs = [A,D,D,D], dif(A,B),     B=C ,     C=D , Zss = [[A,1],            [D,3]] ;
Xs = [A,C,C,D], dif(A,B),     B=C , dif(C,D), Zss = [[A,1],      [C,2],[D,1]] ;
Xs = [A,B,D,D], dif(A,B), dif(B,C),     C=D , Zss = [[A,1],[B,1],      [D,2]] ;
Xs = [A,B,C,D], dif(A,B), dif(B,C), dif(C,D), Zss = [[A,1],[B,1],[C,1],[D,1]].