Search code examples
prolog

Count occurrences Prolog

I'm new in Prolog and trying to do some programming with Lists
I want to do this : 

?- count_occurrences([a,b,c,a,b,c,d], X).
X = [[d, 1], [c, 2], [b, 2], [a, 2]].

and this is my code I know it's not complete but I'm trying:

count_occurrences([],[]).
count_occurrences([X|Y],A):-
   occurrences([X|Y],X,N).

occurrences([],_,0).    
occurrences([X|Y],X,N):- occurrences(Y,X,W), N is W + 1.
occurrences([X|Y],Z,N):- occurrences(Y,Z,N), X\=Z.

My code is wrong so i need some hits or help plz..

Solution

  • Here's my solution using bagof/3 and findall/3:

    count_occurrences(List, Occ):-
    findall([X,L], (bagof(true,member(X,List),Xs), length(Xs,L)), Occ).

    An example

    ?- count_occurrences([a,b,c,b,e,d,a,b,a], Occ).
Occ = [[a, 3], [b, 3], [c, 1], [d, 1], [e, 1]].

    How it works

    bagof(true,member(X,List),Xs) is satisfied for each distinct element of the list X with Xs being a list with its length equal to the number of occurrences of X in List:

    ?- bagof(true,member(X,[a,b,c,b,e,d,a,b,a]),Xs).
X = a,
Xs = [true, true, true] ;
X = b,
Xs = [true, true, true] ;
X = c,
Xs = [true] ;
X = d,
Xs = [true] ;
X = e,
Xs = [true].

    The outer findall/3 collects element X and the length of the associated list Xs in a list that represents the solution.

    Edit I: the original answer was improved thanks to suggestions from CapelliC and Boris.

    Edit II: setof/3 can be used instead of findall/3 if there are free variables in the given list. The problem with setof/3 is that for an empty list it will fail, hence a special clause must be introduced.

    count_occurrences([],[]).
count_occurrences(List, Occ):-
    setof([X,L], Xs^(bagof(a,member(X,List),Xs), length(Xs,L)), Occ).