Prolog getting frequency of list

Question

Working on a prolog assignment.

I have a structure cnt(letter,number).

I need to return a list of cnt where each cnt is the number of times each character appears (assuming that each item has already been sorted to place the same item one after each other).

I have this so far:

cnt(letter,number).

freq([],[]).

freq([A|L],Y) :- grab(A,Init,_), freq(L,[Init|Y]).

grab works correctly takes a list of items and returns the list of the first duplicates as Init

e.g grab([a,a,a,b,c], Init, Rest). will return Init = [a,a,a].

Assuming I have a list [a,a,a,b,b,b,c,c] i need freq to return Y = [cnt(a,3), cnt(b,3), cnt(c,2)].

I think what I have so far is near correct, except that it returns false.

Is there anyway to step through to see what it is doing to get there? Or can anyone see any obvious problems.

Answer 1

Let's start with your definition, which is already very close to what you want.

freq([],[]).
freq([A|L],Y) :- grab(A,Init,_), freq(L,[Init|Y]).

freq/2 defines here something for each element of the list. To see this, I will look at the following part of your definition:

freq([],_).
freq([A|L],_) :- ..., freq(L,_).

Is this what you want? You said that the list contains the same elements consecutively only. So if we have [a,a] you do want this freq/2 to be applied once, not twice.

The other problem is this. Again, I am looking only at a part of your program:

freq(_,[]).
freq(_,Y) :- ..., freq(_,[Init|Y]).

So you have here a goal freq(_,[Init|Y]) which has a list of at least one element in the second argument. Do you see any clause in your definition which applies to such lists? The fact freq(_,[]). never applies, so the only rule left is the very rule where this goal appears in. In short, a goal freq(_,[Init|Y]) will never succeed. No matter what Init and Y are.

Here is now your corrected version, which is almost what you want:

freq([],[]).
freq([A|L],[As|Y]) :-
   grab([A|L],As,K),
   freq(K,Y).

Lets see:

?- freq([a,a,a,b,b,b,c,c],Ys).
Ys = [[a,a,a],[b,b],[c,c]].

So instead of those elements that are lists, we need a structure cnt(a,3) with the character and the length of the list.

freq([],[]).
freq([A|L],[cnt(A,N)|Y]) :-
   grab([A|L],As,K),
   length(As, N),
   freq(K,Y).

Answer 2

I'll try explain what you can do (sorry for my poor English).

Your base case freq([], []) looks good, but you want to count elements, so it would be

freq([], [cnt(0, _)])

which looks odd.

Interesting is the base case of a list with only one element :

freq([A], [cnt(1,A)]).

Now, in Prolog when we process a list, we keep the first element and process the rest of the list, then we look at the result :

freq([A | T], R) :-
    freq(T, R1),
    process(A, R1, R).

Now, how is R1, two possibilities : R1 = [cnt(V, A) | L] or R1= [cnt(V, B)|L] with A different of B.

So we can write

process(A, [cnt(V, A)|L], [cnt(V1, A) | L]) :-
    V1 is V+1.

process(A, [cnt(V, B)|L], [cnt(1, A), cnt(V, B) | L]) :-
    A \= B.