CODEWITHSUNDEEP
listprolog
Pei Chuang
Pei Chuang

Reputation: 67

Counting same element Prolog

I want to count one element in the list and stop counting where different element appear, and jump to the next same element.

The answers should be like this:

?- count(a,[a,a,a,a,b,a,a,a],X).
X = [4,3]

?- count(a,[a,a,a,b,a,b,a,a,b,a,a,a,a],X).
X = [3,1,2,4]

The code I wrote for count/3 is: 

count(_, [], []).
count(X, [X | T], N) :-
   count(X, T, N1),
   !, 
   N is N1 + 1.
count(X, [_ | T], N) :-
   count(X, T, N).

I don't know how to make it return a list of number. Can anyone help me? Thanks.

Upvotes: 3

Views: 194

Answers (2)

repeat
repeat

Reputation: 18726

Here's how you can do it and preserve !

In the following, we use the meta-predicates (splitlistIfAdj/3, tfilter/3, and maplist/3) and reified term equality/inequality predicates ((=)/3 and dif/3).

Let's take E = a and Xs0 = [a,a,a,b,a,b,a,a,b,a,a,a,a] and build up count/3 step by step:

  1. First, let Xs1 contain the runs of items in Xs0: 

    ?- Xs0 = [a,a,a,b,a,b,a,a,b,a,a,a,a], splitlistIfAdj(dif,Xs0,Xs1).
Xs0 = [ a,a,a,  b,  a,  b,  a,a,  b,  a,a,a,a ],
Xs1 = [[a,a,a],[b],[a],[b],[a,a],[b],[a,a,a,a]].

  2. The list of runs Xs1 contains all runs. Let Xs2 contain only the ones we are interested in: 

    ?- Xs1 = [[a,a,a],[b],[a],[b],[a,a],[b],[a,a,a,a]], tfilter(\[X|_]^(X=a),Xs1,Xs2).
Xs1 = [[a,a,a],[b],[a],[b],[a,a],[b],[a,a,a,a]],
Xs2 = [[a,a,a],    [a],    [a,a],    [a,a,a,a]].

  3. Almost done! At last, we map Xs2 (a list of E-runs) to the respective run lengths Xs: 

    ?- Xs2 = [[a,a,a],[a],[a,a],[a,a,a,a]], maplist(length,Xs2,Xs).
Xs2 = [[a,a,a],[a],[a,a],[a,a,a,a]],
Xs  = [      3,  1,    2,        4].

Now, let's put it all together!

count(E,Xs0,Xs) :-
    splitlistIfAdj(dif,Xs0,Xs1),
    tfilter(E+\[X|_]^(X=E),Xs1,Xs2),   % works for _any_ item E
    maplist(length,Xs2,Xs).

Let's run some queries:

?- count(a,[a,a,a,a,b,a,a,a],Xs).
Xs = [4,3].                            % succeeds deterministically
?- count(a,[a,a,a,b,a,b,a,a,b,a,a,a,a],Xs).
Xs = [3,1,2,4].                        % succeeds deterministically

As the code is monotone, we get logically sound answers for more general queries, too:

?- count(E,[a,a,a,b,a,b,a,a,b,a,a,a,a],Xs).
Xs = [3,1,2,4], E = a              ;
Xs = [1,1,1],   E = b              ;
Xs = [],        dif(E,a), dif(E,b) .

Upvotes: 3

Kijewski
Kijewski

Reputation: 26022

The idea in my answer is to keep the list of run lengths open, and add a new element to it when a run is over:

count(_, [], []).
count(Item, [Head|Tail], Counts) :-
    count(Item, [Head|Tail], 0, Counts).
count(_, [], CurrentCount, [CurrentCount]).

count(Item, [Item|Tail], CurrentCount, Counts) :-
    CurrentCountP1 is CurrentCount + 1,
    count(Item, Tail, CurrentCountP1, Counts).
count(Item, [Head|Tail], CurrentCount, [CurrentCount|Counts]) :-
    dif(Head, Item),
    count(Item, Tail, 0, Counts).

?- count(a,[a,a,a,b,a,b,a,a,b,a,a,a,a], X).
X = [3, 1, 2, 4] ;
false.

Upvotes: 1

Related Questions