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).

I can see at least one problem here: `[L|[X,C]]` will produce a plain list. L is a head (single element) and [X,C] is a tail list. Upd: oh, you have edited it already.. — Eugene Sh., Nov 20 '14 at 21:16
@EugeneSh. actualy it was a mistake when I tried to simplify my code to the basic problem, rather than the full implementation of it that it includes more predicates that are irrelevant to the problem. — JmRag, Nov 20 '14 at 21:20
In your `append` base case you need `append([ ],Y,[Y]).` if I understand right it's intention. — Eugene Sh., Nov 20 '14 at 21:26
@EugeneSh. append works fine as is it. Changing it to what you propose, it works fine again (the predicate of append).But the problem in count remains in both cases.. — JmRag, Nov 20 '14 at 21:34
See [this answer](http://stackoverflow.com/questions/26927602/why-do-we-use-in-prolog/26936836#26936836). — false, Nov 20 '14 at 23:08

score 3 · Answer 1 · edited May 23 '17 at 10:27

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]].

CapelliC · Answer 2 · 2014-11-20T21:48:53.103

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 ...)

edited Nov 20 '14 at 21:48

answered Nov 20 '14 at 21:40

CapelliC

59,646
5
47
90

wow your answer made me look like an idiot. I am not very familiar with prolog yet and my I think as I would at declerative programming. Thx a lot for your answer and explanation! Yeah what you point in bold is a typo, I edited the question to be correct. – JmRag Nov 20 '14 at 21:53

score 2 · Accepted Answer · edited May 23 '17 at 12:23

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).

So in theory it would still be better for `?- list_rle(Xs,[2*a,1*b,3*c,1*d,2*e]). Xs = [a,a,b,c,c,c,d,e,e] ; false.` to be deterministic right? and not have a choice point ? — user27815, Oct 18 '15 at 12:34
@user27815. It would. But we have to strike a balance and prioritize: correctness > versatility > efficiency. — repeat, Oct 18 '15 at 13:05

score 0 · Answer 4 · answered Nov 21 '14 at 01:06

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
  .                               %

pasaba por aqui · Answer 5 · 2015-05-21T19:09:34.340

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].

count successive occurrences of number in Prolog

5 Answers5

Linked