CODEWITHSUNDEEP
listprolog
John
John

Reputation: 847

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

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!

Upvotes: 2

Views: 2037

Answers (2)

repeat
repeat

Reputation: 18726

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.

Upvotes: 2

CapelliC
CapelliC

Reputation: 60004

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

Upvotes: 1

Related Questions