prolog list of how many times an element occurs in a list?

Question

Well, I have a list, say [a,b,c,c,d], and I want to generate a list [[a,1],[b,1],[c,2],[d,1]]. But I'm having trouble with generating my list. I can count how many times the element occur but not add it into a list:

% count how much the element occurs in the list.
count([], _, 0).
count([A|Tail], A, K) :-
    count(Tail, A, K1),
    K is K1 + 1.
count([_|Tail], X, K) :-
    count(Tail, X, K1),
    K is K1 + 0.

% Give back a list with each element and how many times is occur
count_list(L, [], _).
count_list(L, [A|Tail], Out) :-
    count(L, A, K),
    write(K),
    count_list(L, Tail, [K|Out]).

I'm trying to learn Prolog but having some difficulties... Some help will be much appreciated... Thanks in advance!

score 2 · Answer 1 · edited May 23 '17 at 11:52

Let me first refer to a related question "How to count number of element occurrences in a list in Prolog" and to my answer in particular.

In said answer I presented a logically-pure monotone implementation of a predicate named list_counts/2, which basically does what you want. Consider the following query:

?- list_counts([a,b,c,c,d], Xs).
Xs = [a-1,b-1,c-2,d-1].          % succeeds deterministically

?- list_counts([a,b,a,d,a], Xs). % 'a' is spread over the list
Xs = [a-3,b-1,d-1].              % succeeds deterministically

Note that the implementation is monotone and gives logically sound answers even for very general queries like the following one:

?- Xs = [_,_,_,_],list_counts(Xs,[a-N,b-M]).
Xs = [a,a,a,b], N = 3, M = 1 ;
Xs = [a,a,b,a], N = 3, M = 1 ;
Xs = [a,a,b,b], N = M, M = 2 ;
Xs = [a,b,a,a], N = 3, M = 1 ;
Xs = [a,b,a,b], N = M, M = 2 ;
Xs = [a,b,b,a], N = M, M = 2 ;
Xs = [a,b,b,b], N = 1, M = 3 ;
false.

score 1 · Accepted Answer · answered Oct 25 '14 at 21:51

I cannot follow your logic. The easy way would be to use library(aggregate), but here is a recursive definition

count_list([], []).
count_list([H|T], R) :-
    count_list(T, C),
    update(H, C, R).

update(H, [], [[H,1]]).
update(H, [[H,N]|T], [[H,M]|T]) :- !, M is N+1.
update(H, [S|T], [S|U]) :- update(H, T, U).

the quirk: it build the result in reverse order. Your code, since it uses an accumulator, would give the chance to build in direct order....

prolog list of how many times an element occurs in a list?

2 Answers2