CODEWITHSUNDEEP
listrecursionprologcounter
user2962883
user2962883

Reputation: 57

Prolog: Incrementing counter depending on elements in a list of lists

I'm trying to incremement 4 counters depending on if a list of lists has a certain element in it. For example, given:

check_occurences(A,B,C,D,List)

and:

  List = [[a,b,c],[a,b,c,d],[b,d],[a]]

I should get:

A = 3; B = 3; C = 2; D = 2

My attempt so far:

check_occurences(A,B,C,D,List) :- 
   helper(List,a,A), 
   helper(List,b,B), 
   helper(List,c,C), 
   helper(List,d,D).

helper([],_,A).
helper([H|T],Elt,X) :- member(Elt,H), Count = X + 1, helper(T,Elt,Count).
helper([H|T],Elt,X) :- helper(T,Elt,X).

The idea behind my code is I call helper for each counter. If The Elt is a member of X, I increment the counter. If not, I use the third fact to continue the recursion. I stop when the list is empty. However, the problem is incrementing the counter.

EDIT: Fixed mistake in code.

Upvotes: 1

Views: 935

Answers (2)

Nicholas Carey
Nicholas Carey

Reputation: 74227

If it was me, I'd probably first write a general-purpose predicate to compute the frequencies of list items, something like this:

frequencies( []     , Fs, Fs ) .    % once the source list is exhausted, the frequency table is complete
frequencies( [X|Xs] , Ts, Fs ) :-   % otherwise...
  increment(X,Ts,T1) ,              % - increment the frequency count for X
  frequencies(Xs,T1,Fs)             % - and recurse down.
  .                                 %

increment( X , Ts , Fs ) :-         % to increment the frequency list
  append( Pfx , [X:C|Sfx] , Ts ) ,  % - If X is already a key in the list
  !,                                % - cut off alternatives
  C1 is C+1 ,                       % - increment the count
  append( Pfx , [X:C1|Sfx] , T1 )   % - put the list back together to create the new list.
  .                                 % otherwise...
increment( X , Fs , [X:1|Fs] ).     % X is not in the list: add it.

Then your check_occurences/3 predicate is simple and declarative:

check_occurences(A,B,C,D,Xs) :- % to compute a frequency table,
  frequencies( Xs , [], Fs ) ,  % - invoke the helper to compute the frequency table
  frequency_of(a,Fs,A) ,        % - get the count for a
  frequency_of(b,Fs,B) ,        % - get the count for b
  frequency_of(c,Fs,C) ,        % - get the count for c
  frequency_of(d,Fs,D)          % - get the count for d
  .                             % Easy!

frequency_of( _ , []       , 0 ) .    % if the item is not a key in the list, the count is zero.
  frequency_of( X , [X:N|_]  , N ) :- % if the item is a key in the list, succeeed
  .                                   % 
frequency_of( X , [Y:_|Fs] , N ) :-   % otherwise....
  X \= Y ,                            % - assuming we haven't yet found the desired key
  frequency_of(X,Fs,N)                % - we recurse down
  .                                   %

Upvotes: 1

Wouter Beek
Wouter Beek

Reputation: 3407

Slightly generalizing the problem you describe: for a given list of lists you want to know:

  1. What elements occur in any of those lists.
  2. For each element in (1), the number of list in which it occurs one or more times.

Using some libraries, I come up with the following program that does this:

:- use_module(library(apply)).
:- use_module(library(lists)).
:- use_module(library(pairs)).

check_occurrences(Ls1, Ps3):-
  maplist(sort, Ls1, Ls2),
  append(Ls2, L),
  map_list_to_pairs(count(L), L, Ps1),
  sort(Ps1, Ps2),
  transpose_pairs(Ps2, Ps3).
count(L, X, N):-
  aggregate(count, member(X, L), N).

Example of use:

?- check_occurrences([[a,a,b,c],[a,b,c,d,e,f,g],[b,d,f,g],[a]], Counts).
Counts = [a-3, b-3, c-2, d-2, e-1, f-2, g-2].

Upvotes: 2

Related Questions