Python counter in Prolog

Question

In Python you can do

>>> import from collections counter
>>> Counter(['a','b','b','c'])
>>> Counter({'b': 2, 'a': 1, 'c': 1})

Is there something similar in Prolog? Like so:

counter([a,b,b,c],S). 
S=[a/1,b/2,c/1].

This is my implementation:

counter([],List,Counts,Counts).

counter([H|T],List,Counts0,[H/N|Counts]):-
  findall(H, member(H,List), S),
  length(S,N),
  counter(T,List,Counts0,Counts).

counter(List,Counts):-
  list_to_set(List,Set),
  counter(Set,List,[],Counts).

It's rather verbose, so I wondered if there was a builtin predicate or a more terse implementation.

Answer 1

I also like @joel76 solution (and @mbratch suggestions, also). Here I'm just to note that library(aggregate), if available, has a count aggregate operation, that can be used with the ISO builtin setof/3:

counter(L, Cs) :-
    setof(K-N, (member(K, L), aggregate(count, member(K, L), N)), Cs).

yields

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

If the selection operation was more complex, a nice way to avoid textually repeating the code could be

counter(L, Cs) :-
    P = member(K, L),
    setof(K-N, (P, aggregate(count, P, N)), Cs).

edit

Since I'm assuming library(aggregate) available, could be better to task it the set construction also:

counter(L, Cs) :-
    P = member(E,L), aggregate(set(E-C), (P, aggregate(count,P,C)), Cs).

Answer 2

I like @joel76's solution. I will add a few more variations on the theme.

VARIATION I

Here's another simple approach, which sorts the list first:

counter(L, C) :-
    msort(L, S),             % Use 'msort' instead of 'sort' to preserve dups
    counter(S, 1, C).
counter([X], A, [X-A]).
counter([X,X|T], A, C) :-
    A1 is A + 1,
    counter([X|T], A1, C).
counter([X,Y|T], A, [X-A|C]) :-
    X \= Y,
    counter([Y|T], 1, C).

Quick trial:

| ?- counter([a,b,b,c], S).

S = [a-1,b-2,c-1] ?

yes

This will fail on counter([], C). but you can simply include the clause counter([], []). if you want it to succeed. It doesn't maintain the initial order of appearance of the elements (it's unclear whether this is a requirement). This implementation is fairly efficient and is tail recursive, and it will work as long as the first argument is instantiated.

VARIATION II

This version will maintain order of appearance of elements, and it succeeds on counter([], []).. It's also tail recursive:

counter(L, C) :-
    length(L, N),
    counter(L, N, C).
counter([H|T], L, [H-C|CT]) :-
    delete(T, H, T1),          % Remove all the H's
    length(T1, L1),            % Length of list without the H's
    C is L - L1,               % Count is the difference in lengths
    counter(T1, L1, CT).       % Recursively do the sublist
counter([], _, []).

With some results:

| ?-  counter([a,b,a,a,b,c], L).

L = [a-3,b-2,c-1]

yes
| ?- counter([], L).

L = []

yes

VARIATION III

This one uses a helper which isn't tail recursive, but it preserves the original order of elements, is fairly concise, and I think more efficient.

counter([X|T], [X-C|CT]) :-
    remove_and_count(X, [X|T], C, L),  % Remove and count X from the list
    counter(L, CT).                    % Count remaining elements
counter([], []).

% Remove all (C) instances of X from L leaving R
remove_and_count(X, L, C, R) :-
    select(X, L, L1), !,               % Cut to prevent backtrack to other clause
    remove_and_count(X, L1, C1, R),
    C is C1 + 1.
remove_and_count(_, L, 0, L).

This implementation will work as long as the first argument to counter is instantiated.

---

SIDEBAR

In the above predicates, I used the Element-Count pattern rather than Element/Count since some Prolog interpreters, SWI in particular, offer a number of predicates that know how to operate on associative lists of Key-Value pairs (see SWI library(pairs) and ISO predicate keysort/2).

Answer 3

There is no builtin predicate, here is another way to do that :

counter([X], [X/1]).

counter([H | T], R) :-
    counter(T, R1),
    (   select(H/V, R1, R2)
    ->  V1 is V+1,
        R = [H/V1 | R2]
    ;   R = [H/1 | R1]).