Search code examples
prolog

Finding most occurrences in set of prolog rules

I can't seem to wrap my head around how Prolog actually works. I'm very used to other programming languages like Java and Python but Prolog seems to be very different since it is based on a set of logical statements.

If someone can explain to me how I would approach a situation where I am given a set of rules such as

likes(john,mary).
likes(mary,adam).
likes(adam,mary).
likes(jack,destiny).
likes(destiny,adam).
likes(brianna,adam).

and I want to find out how to see who is the most liked person (in this case adam = 3), how would I do this?

Solution

  • Maybe it's easier if you think of Prolog as a special database retrieval language that can morph into functional programming in the same line.

    Here we we have a relation likes/2 over which we want to run statistics.

    One could use predicates from library(aggregate) or similar, but let's not

    Suggestion is to chain three operations:

    1. Create a nicer structure to run stats
    2. Run stats over nicer structure
    3. Find the best

    Create nicer structure to run stats

    Collect

    • the vector (in the form or a Prolog list) of persons that occur as second argument in predicate likes/2 (so that we have something to count), and
    • the set of persons (also in the form of a Prolog list) so that we can iterate over something.

    The key are the collection predicates findall/3 and setof/3

    • findall/3 is used to collect all the Person that appear on second argument position of likes/2,
    • setof/3 is used to collect the set of all Person that appear on first or second argument position of likes/2. To make that work, setof/3 needs to be told that the argument on the other position is unimportant by "existentially quantifying" it with X^.
    person_occurrences(PersonVec) :- 
   findall(Person,likes(_,Person),PersonVec).
   
person_set(PersonSet) :-
   setof(Person,X^(likes(Person,X);likes(X,Person)),PersonSet).

    Alternativey for person_set/2, more comprehensible:

    person(Person) :- likes(Person,_).
person(Person) :- likes(X,Person).

person_set(PersonSet) :- setof(Person,person(Person),PersonSet).

    Trying this on the "Prolog Toplevel" shows we are on the right track:

    ?- person_occurrences(PersonSet).
PersonSet = [mary, adam, mary, destiny, adam, adam].

?- person_set(PersonSet).
PersonSet = [adam, brianna, destiny, jack, john, mary].

    We can easily count how often a person occurs in the vector of persons, by using findall/3 to create an arbitrary list of x (for example), one x for each occurrence, then determining the length of that list:

    count(Person,PersonVec,Count) :-
   findall(x,member(Person,PersonVec),Xs),length(Xs,Count).

    Trying this on the "Prolog Toplevel" shows we are on the right track:

    ?- person_occurrences(PersonVec),count(mary,PersonVec,Count).
PersonVec = [mary, adam, mary, destiny, adam, adam],
Count = 2.

    We now have the "nicer structure" that we can use to do stats, namely the "vector of persons" and the "set of persons".

    Run stats over nicer structure

    The result here, called Stats shall be a list (it's always lists) of pairs -(NumberOfOccurrencesOfPersonInPersonVector,Person), which can be more easily written "infix": Count-Person, for example 2-mary.

    This is a recursive definition (or an inductive definition) whereby we "count" for each person element in PersonSet until the PersonSet is the empty set (or rather, the empty list), upon which we are done and succeed. The result is constructed in the third argument:

    % stats(PersonVec,PersonSet,Stats)

stats(_,[],[]).

stats(PersonVec,[Person|MorePersons],[Count-Person|MoreStats]) :-
     count(Person,PersonVec,Count),           % count them
     stats(PersonVec,MorePersons,MoreStats).  % recursion

    Trying this on the "Prolog Toplevel" shows we are on the right track:

    ?- person_occurrences(PersonVec),stats(PersonVec,[mary],Stats).
PersonVec = [mary, adam, mary, destiny, adam, adam],
Stats = [2-mary] ;   % Maybe more solutions?
false.               % Nope.

    New we can build the whole of the stats list:

    stats(Stats) :- 
   person_occurrences(PersonVec),
   person_set(PersonSet),
   stats(PersonVec,PersonSet,Stats).

    Trying this on the "Prolog Toplevel" shows we are on the right track:

    ?- stats(Stats).
Stats = [3-adam, 0-brianna, 1-destiny, 0-jack, 0-john, 2-mary] ;
false.

    Find the best

    Given Stats, we can find a BestPerson by maximizing over the list of pairs.

    This can be done directly by selecting the pair which is "largest" according to "the standard order of term": the numeric count comes first so a term with a larger numeric count is "larger" than one with a smaller numeric count, which is what we want. The predicate max_member/2 does what we want:

    best(Stats,BestPerson,BestCount) :-
   max_member(BestCount-BestPerson,Statss).

    Alternatively, we can program-out the max_member/2 (and keep it to numeric comparison of the first argument, AND get several answers in case there are several persons with the same "likes" count), like so:

    % start the maximization over Stats with a dummy "(-1)-nobody"

best(Stats,BestPerson,BestCount) :-
   best2(Stats, (-1)-nobody, BestCount-BestPerson).

% best2(Stats,BestCountSoFar-BestPersonSoFar,Result).

best2([],BestCountSoFar-BestPersonSoFar,BestCountSoFar-BestPersonSoFar).

best2([Count-_|MoreStats],BestCountSoFar-BestPersonSoFar,Result) :-
   Count < BestCountSoFar,
   best2(MoreStats,BestCountSoFar-BestPersonSoFar,Result). % keep best
   
best2([Count-_|MoreStats],BestCountSoFar-BestPersonSoFar,Result) :-
   Count == BestCountSoFar,
   best2(MoreStats,BestCountSoFar-BestPersonSoFar,Result). % keep best (2nd possibility below)
   
best2([Count-Person|MoreStats],BestCountSoFar-_,Result) :-
   Count >= BestCountSoFar,
   best2(MoreStats,Count-Person,Result). % take new, better, pair

    Conclude

    We run it together:

    ?- stats(Stats),best(Stats,BestPerson,BestCount).
Stats = [3-adam, 0-brianna, 1-destiny, 0-jack, 0-john, 2-mary],
BestPerson = adam, BestCount = 3 ;  % maybe more solutions?
false.                              % no

    Complete code

    likes(john,mary).
likes(mary,adam).
likes(adam,mary).
likes(jack,destiny).
likes(destiny,adam).
likes(brianna,adam).

person_occurrences(PersonVec) :- 
   findall(Person,likes(_,Person),PersonVec).
   
person_set(PersonSet) :-
   setof(Person,X^(likes(Person,X);likes(X,Person)),PersonSet).

count(Person,PersonVec,Count) :- 
   findall(x,member(Person,PersonVec),Xs),length(Xs,Count).

% stats(PersonVec,PersonSet,Stats)
   
stats(_,[],[]).

stats(PersonVec,[Person|MorePersons],[Count-Person|MoreStats]) :-
     count(Person,PersonVec,Count),           % count them
     stats(PersonVec,MorePersons,MoreStats).  % recursion
   
stats(Stats) :- 
   person_occurrences(PersonVec),
   person_set(PersonSet),
   stats(PersonVec,PersonSet,Stats).
   
% start the maximization over Stats with a dummy "(-1)-nobody"

best(Stats,BestPerson,BestCount) :-
   best2(Stats, (-1)-nobody, BestCount-BestPerson).

% best2(Stats,BestCountSoFar-BestPersonSoFar,Result).

best2([],BestCountSoFar-BestPersonSoFar,BestCountSoFar-BestPersonSoFar).

best2([Count-_|MoreStats],BestCountSoFar-BestPersonSoFar,Result) :-
   Count < BestCountSoFar,
   best2(MoreStats,BestCountSoFar-BestPersonSoFar,Result). % keep best
   
best2([Count-_|MoreStats],BestCountSoFar-BestPersonSoFar,Result) :-
   Count == BestCountSoFar,
   best2(MoreStats,BestCountSoFar-BestPersonSoFar,Result). % keep best (2nd possibility below)
   
best2([Count-Person|MoreStats],BestCountSoFar-_,Result) :-
   Count >= BestCountSoFar,
   best2(MoreStats,Count-Person,Result). % take new, better, pair