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.

I'm afraid your `freq` predicate is a bit off. For example, the `grab(A,Init,_)` is using only the head of the initial list `A` as its first argument, but you need the whole list (or at least `L`). You'll want to think of its recursive definition logically, *freq([A|L], [cnt(A,C)|Cs])* would be one reasonable predicate to try and define, and when you do the `grab`, you'll need to get the length of `Init` for the value of `C`, etc. You can get rid of `cnt(letter, number).` it is not needed. Finally, `Cs` would be determine with a recursive call to `freq`. — lurker, Jun 08 '14 at 03:49

false · Accepted Answer · 2022-08-19T17:54:20.793

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

joel76 · Answer 2 · 2014-06-08T12:38:21.973

4

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.

edited Jun 08 '14 at 12:38

answered Jun 08 '14 at 09:04

joel76

5,565
1
18
22

1

I don't think `freq([], [cnt(0,_)])` is a correct base case. If you don't have any elements, then there's nothing to count, so the cnt(0,_)` is meaningless. The count list should truly be `[]` and the base case `freq([], [])` as the OP originally had it is a perfectly good base case. The recursive case will reduce down to it properly. – lurker Jun 08 '14 at 20:07
@luker : May be you're right. One can say that an empty list contains 0 element of anything, or freq can fails with an empty list, I really don't know the good answer. – joel76 Jun 08 '14 at 21:20

Nicholas Carey · Answer 3 · 2014-06-09T18:12:37.593

I'd go at it like this (assuming the list is already ordered)

frequency( []     , [] ) .   % the frequency table for the empty list is the empty list
frequency( [X|Xs] , F  ) :-  % for a non-empty list,
  tabulate( Xs , X:1 , F )   %   we just invoke the tabulation predicate, seeding the accumulator with the initial count.
  .                          %

tabulate( []     , C:N , [C:N] ) .    % if the source list is exhausted, we're done: shift the accumulator to the result list.
tabulate( [X|Xs] , X:N , F ) :-       % otherwise, 
  ! ,                                 % - and we haven't yet hit a sequence break,
  N1 is N+1 ,                         % - increment the frequency
  tabulate( Xs , X:N1 , F )           % - and recurse down.
  .                                   %
tabulate( [X|Xs] , C:N , [C:N|F] ) :- % finally, if we have a sequency break: shift the accumulator to the result list
  tabulate( Xs , X:1 , F )            % and recurse down
  .                                   %

This sorts the list and then makes a single pass over the list, counting as we go.

Prolog getting frequency of list

3 Answers3

Linked