Prolog count frequencies

Question

Is it possible to write a predicate which takes an input list and "outputs" (succeeds) an output list with key-value pairs

example:

freqs([a,b,a,a,b,c],L).
L = [(a,3),(b,2),(c,1)]

I'd prefer to do this in O(n) if possible. The furthest I've gotten is this

freqs([],[]).
freqs(In,Out):-
    freqs(In,[],Out).

freqs([],Out,Out).
freqs([X|Xs],Table,Out):-
    \+ member((X,_),Table),
    freqs(Xs,[(X,1)|Table],Out).

freqs([X|Xs],Table,Out) :-
    member((X,N),Table),
    % stuck

more specifick, how to increment N? And is there an other solution possible which doesn't need an auxiliary predicate?

Paulo Moura · Accepted Answer · 2018-08-23T19:23:28.663

You could use the common library predicate select/3 (or selectchk/3 if also available) instead of member/2. Something like (for the third clause):

freqs([X|Xs],Table,Out) :-
    selectchk((X,N),Table, Others),
    M is N + 1,
    freqs(Xs, [(X,M)| Others], Out).

However, as you seem to be concerned about performance, it would be faster if you combine the second and third clauses, resulting in the following complete predicate definition:

freqs([], Out, Out).
freqs([X| Xs], Table, Out) :-
    (   select((X,N), Table, Others) ->
        M is N + 1,
        freqs(Xs, [(X,M)| Others], Out)
    ;   freqs(Xs, [(X,1)| Table], Out)
    ).

This way you only look for the presence of a (X,N) term in the table once per input list element.

Sample call:

?- freqs([a,b,a,a,b,c],L).
L = [(c, 1),  (b, 2),  (a, 3)].

Another solution would be to first sort the input list using the standard sort/2 predicate, which is usually O(n log(n)), and then walk the resulting sorted list once, which will be, of course, O(n). So O(n*log(n)) + O(n) complexity. But, as Will Ness explained, if your input list is large, it may be worth looking into your Prolog system libraries for a good dictionary implementation.

could you give some example links for those dictionary implementations? — Will Ness, Aug 22 '18 at 14:25
@WillNess A candidate dictionary implementation would be the Red-Black trees implementation found in YAP, SWI-Prolog, Logtalk, possibly others. It provides a `partial_map/4` meta-predicate that takes a closure that can be used to update the counter. — Paulo Moura, Aug 22 '18 at 14:33
thanks for the [reference](http://www.swi-prolog.org/pldoc/doc/_SWI_/library/rbtrees.pl)! — Will Ness, Aug 22 '18 at 17:54

Will Ness · Answer 2 · 2018-08-22T15:17:15.060

Write your predicate function in a state-passing style, updating the table while traversing the list, as you'd do in a functional programming language, making an altered copy instead of (the impossible) mutation of a value.

With linear table it will be O(n²) of course.

Maintaining it as an open binary search tree (with uninstnatiated logvars at the leaves, for the tree to be extended when a new key is encountered) will bring the complexity down to O(n log n), as usual. Your keys will have to be comparable for that. Atoms are.

See attr/2 for an example of extendable look-up table (only that it's a list, there; making it a tree is perfectly doable, too).

Prolog count frequencies

2 Answers2