Prolog - Count the Number of Repetitions in a List

Question

I'm writing a program in Prolog that counts the number of uninterrupted occurrences of the first value in a list.

So given, repetitions(N, [a,a,a,a,a,b,c,a]), the program would return N = 5.

This is what my code looks like so far:

repetitions(A,[]).
repetitions(A,[A|T]) :- repetitions(A,[_|T]), A is 1+A.
repetitions(A,[_|T]) :- repetitions(A,[A|T]).

Answer 1

Here is a relational version:

repetitions(N, [First|Rest]) :-
        phrase(repetitions_(First, 1, N), Rest).

repetitions_(_, N, N) --> [].
repetitions_(First, N0, N) --> [First],
        { N1 #= N0 + 1 },
        repetitions_(First, N1, N).
repetitions_(First, N, N) --> [Other], { dif(First, Other) }, ... .

... --> [] | [_], ... .

The test case works as required:

?- repetitions(N, [a,a,a,a,a,b,c,a]).
N = 5 ;
false.

And moreover, we can also use this in other directions.

For example, what about a list with 3 element in general:

?- Ls = [A,B,C], repetitions(N, Ls).
Ls = [C, C, C],
A = B, B = C,
N = 3 ;
Ls = [B, B, C],
A = B,
N = 2,
dif(B, C) ;
Ls = [A, B, C],
N = 1,
dif(A, B) ;
false.

And what about all possible answers, fairly enumerated by iterative deepening:

?- length(Ls, _), repetitions(N, Ls).
Ls = [_8248],
N = 1 ;
Ls = [_8248, _8248],
N = 2 ;
Ls = [_8734, _8740],
N = 1,
dif(_8734, _8740) ;
Ls = [_8248, _8248, _8248],
N = 3 ;
Ls = [_8740, _8740, _8752],
N = 2,
dif(_8740, _8752) ;
etc.

It is a major attraction of logic programs that they can often be used in several directions.

See dcg, prolog-dif and clpfd for more information about the mechanisms I used to achieve this generality.

We can also use this to answer the following question

What does a list look like such that there are 3 repetitions of its first element?

Example:

?- repetitions(3, Ls).
Ls = [_2040, _2040, _2040] ;
Ls = [_2514, _2514, _2514, _2532],
dif(_2514, _2532) ;
Ls = [_2526, _2526, _2526, _2544, _2550],
dif(_2526, _2544) ;
Ls = [_2538, _2538, _2538, _2556, _2562, _2568],
dif(_2538, _2556) .

This requires only that a single further constraint be added to the solution above. I leave this as an easy exercise.

Answer 2

Here is a DCG-based solution somewhat a variation to @mat's:

repetitions_II(N, [X|Cs]) :-
   phrase( ( reps(X, N), no(X) ), [X|Cs]).

no(X) -->
   ( [] | [Y], {dif(X,Y)}, ... ).

reps(_X, 0) -->
   [].
reps(X, N0) -->
   [X],
   { N0 #> 0, N1 #= N0-1 },
   reps(X, N1).

Two notable differences:

1mo) There is no use of a difference for maintaining the counter. Thus, constraints on the number can help to improve termination. A perfect clpfd-implementation would (or rather should) implement this with similar efficiency to a difference.

2do) The end no//1 essentially encodes in a pure manner \+[X].

The downside of this solution is that it still produces leftover choicepoints. To get rid of these, some more manual coding is necessary:

:- use_module(library(reif)).

repetitions_III(N, [X|Xs]) :-
   reps([X|Xs], X, N).

reps([], _, 0).
reps([X|Xs], C, N0) :-
   N0 #>= 0,
   if_(X = C, ( N1 #= N0-1, reps(Xs, C, N1) ), N0 = 0 ).

Answer 3

Another approach close to what you've done so far, using CLPFD:

:- use_module(library(clpfd)).

repetitions(N,[H|T]):-repetitions(N,[H|T],H).

repetitions(0,[],_).
repetitions(0,[H|_],H1):-dif(H,H1).
repetitions(N,[H|T],H):-repetitions(N1 ,T, H), N #= N1+1.

Examples:

?- repetitions(A,[a,a,a,a,a,b,c,a]).
A = 5 ;
false.

?- repetitions(2,[a,Y]).
Y = a.

?- repetitions(N,[a,a|_]).
N = 2 ;
N = 2 ;
N = 3 ;
N = 3 ;
N = 4 ;
N = 4 ;
N = 5 ;
N = 5 ;
N = 6 ;
N = 6 ....and goes on

Answer 4

a compact definition, courtesy libraries apply and yall

?- [user].
repetitions(A,[H|T]) :- foldl([E,(C0,H0),(C1,H1)]>>(E==H0 -> succ(C0,C1), H1=H0 ; C0=C1, H1=_), T, (1,H), (A,_)).
|: true.

?- repetitions(A,[a,a,a,a,a,b,c,a]).
A = 5.