Clever Geek Handbook

Counting the same Prolog element

I want to count one item in a list and stop counting when another item appears and move on to the next same item.

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

:

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 get it to return a list of numbers. Can anyone help me? Thank.

+3


source to share


2 answers


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

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.
+1


source


This is how you can do it and save logical-purity!

In what follows, we use meta-predicates ( splitlistIfAdj/3

, tfilter/3

and maplist/3

) and equality / inequality predicates for terms ( (=)/3

and dif/3

).

Take E = a

and Xs0 = [a,a,a,b,a,b,a,a,b,a,a,a,a]

and create count/3

step by step:

  • First let it Xs1

    contain the runs of the elements 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]].

  • The run list Xs1

    contains all runs. Let them Xs2

    contain only those that interest us:   

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

  • Almost done! Finally, match Xs2

    (list E

    -runs) with the corresponding 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, 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).

Run multiple 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

Since the code is monotonous , we also get logical answers for more general queries:

?- 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) .
+3


source






More articles:


All Articles