Counting in a Prolog List

Question

I'm trying to make a prolog function (I know it's not a function but I can't recall it's name) that given a list and a number N returns a list with the elements that repeat at least N times.

xpto(['a', 'a', 'a', 'b', 'b', 'c'], Out, 3) should return Out = ['a']

xpto(['a', 'a', 'a', 'b', 'b', 'c'], Out, 2) should return Out = ['a', 'b']

etc.

I currently have:

xpto([], _, _).

xpto([H | L], O, Num) :-
    count(H, [H | L], N),
    N = Num,
    xpto(L, [H | O], Num).

xpto([H | L], O, Num) :-
    count(H, [H | L], N),
    N \= Num,
    xpto(L, O, Num).

where in count(A, L, N) N is the number of times A repeats in L, however it doesn't work. I'm pretty sure my algorithm works on paper.

Any help is appreciated :)

score 3 · Answer 1 · edited May 23 '17 at 11:52

If your Prolog system supports clpfd, you could use the following implementation of xpto/3. The implementation preserves logical-purity!

Let's implement xpto/3 based on list_counts/2, the meta-predicates tfilter/3 and maplist/3, and on (#=<)/3. (#=<)/3 is a reified version of the constraint (#=</2).

:- use_module(library(clpfd)).
:- use_module(library(lambda)).

xpto(Xs,Ys,N) :-
   list_counts(Xs,Css0),
   tfilter(N+\ (_-V)^(N #=< V),Css0,Css1),
   maplist(\ (K-_)^K^true,Css1,Ys).

Let's run the queries you gave in your questions:

?- xpto([a,a,a,b,b,c],Out,3).
Out = [a].                        % succeeds deterministically

?- xpto([a,a,a,b,b,c],Out,2).
Out = [a,b].                      % succeeds deterministically

As the code used in this implementation is monotone, we can ask quite general queries and still get logically sound answers:

?- xpto([a,a,a,b,b,c],Out,N).
Out = [],      N in 4..sup ;
Out = [a],     N = 3       ;
Out = [a,b],   N = 2       ;
Out = [a,b,c], N in inf..1 .

Now what do the answers look like if the first argument contains variables?

?- Xs = [_,_],xpto(Xs,Out,N).
Xs = [_A,_A], Out = [],       N in 3..sup             ;
Xs = [_A,_A], Out = [_A],     N in inf..2             ;
Xs = [_A,_B], Out = [],       N in 2..sup, dif(_A,_B) ;
Xs = [_A,_B], Out = [_A, _B], N in inf..1, dif(_A,_B) .

score 0 · Answer 2 · 2011-05-11T23:26:58.990

Consider instead:

xpto(L, O, Num) :-
    % check Num is indeed a valid number
    number(Num), Num >= 0,
    % build element occurrence list EO
    elem_occ(L, EO),
    % extract all occurrences which occur at least C times
    findall(E, (member(E-Num0, EO), Num0 >= Num), O).

% computes occurrences O of elements E in a list as E-O
elem_occ([], []).
elem_occ([E|Es], [E-O|EOs]) :-
    filter([E|Es], E, ML, NL),
    length(ML, O),
    elem_occ(NL, EOs).

% filters occurrences of E from the input list and returns the remainder
filter([], _, [], []).
filter([E|Es], E, [E|Ms], Ns) :-
    !, filter(Es, E, Ms, Ns).
filter([E|Es], E0, Ms, [E|Ns]) :-
    filter(Es, E0, Ms, Ns).

Verifying with your examples:

?- xpto(['a', 'a', 'a', 'b', 'b', 'c'], Out, 3).
Out = [a].

?- xpto(['a', 'a', 'a', 'b', 'b', 'c'], Out, 2).
Out = [a, b].

This solution is likely to work on most variants of Prolog (SWI, GNU, SICStus, YAP).

Counting in a Prolog List

2 Answers2