prologprolog-setof

setof/3 inside setof/3 not working, but why?


Inspired by

Find mutual element in different facts in swi-prolog

I wanted to try my hand at "RDBMS operations in Prolog" (actually, this is more or less Datalog)

Problem statement

Given a database of "actors starring in movies":

starsin(a,bob).
starsin(c,bob).

starsin(a,maria).
starsin(b,maria).
starsin(c,maria).

starsin(a,george).
starsin(b,george).
starsin(c,george).
starsin(d,george).

And given set of movies, find those actors that starred in all the movies of said set.

I first had an ugly solution, but then...

Solution that is nice

Clarify the problem:

Sets are represented by lists without duplicates, possibly ordered.

  1. Given a Set of Movies MovIn
  2. ... Find the Set of Actors ActOut
  3. ... ... Such that: Every Actor in ActOut appeared in (at least) all the movies in MovIn
  4. ... ... Reformulated: The Set of Movies MovAx for any actor Ax of ActOut is a superset of MovIn.

setof/3 seems to be the correct toplevel predicate. An Ansatz for points 1 and 2 is:

setof(Ax, (... MovIn ...) , ActOut).

If MovAx is the Set of Movies that Ax appeared in, we can use

Let's use the subset/2.

Point 4 seems to make us write:

setof(Ax, (..., subset(MovAx, MovIn)) , ActOut).

Develop the ... ...

setof(Ax, ( setof(Mx,starsin(Mx,Ax),MovAx) , subset(MovIn, MovAx) ) , ActOut).

This seems to be it already!

The feel when there are λ Expressions but there is no λ on the keyboard or in the syntax.

Done!

Wrap up into predicate:

actors_appearing_in_movies(MovIn,ActOut) :-
   setof(Ax, ( setof(Mx,starsin(Mx,Ax),MovAx) , subset(MovIn, MovAx) ) , ActOut).

Unfortunately the above doesn't work.

There is backtracking going on, apparently I need to wrap everything into another setof/3, but why??

?- actors_appearing_in_movies([a,b],ActOut).
ActOut = [maria] ;
ActOut = [george].

Done, take two

The following does work:

subselect(Ax,MovIn) :- 
   setof(Mx,starsin(Mx,Ax),MovAx), subset(MovIn, MovAx).
actors_appearing_in_movies(MovIn,ActOut) :- 
   setof(Ax, subselect(Ax,MovIn) , ActOut).
?- actors_appearing_in_movies([a,b],ActOut).
ActOut = [george, maria].

Testing

Testing is just running a few goals.

Note that for the empty set of movies, we get all the actors. This is arguably correct: every actors stars in all the movies of the empty set.

actors_appearing_in_movies([],ActOut),permutation([bob, george, maria],ActOut),!. 
actors_appearing_in_movies([a],ActOut),permutation([bob, george, maria],ActOut),!.
actors_appearing_in_movies([a,b],ActOut),permutation([george, maria],ActOut),!.
actors_appearing_in_movies([a,b,c],ActOut),permutation([george, maria],ActOut),!.
actors_appearing_in_movies([a,b,c,d],ActOut),permutation([george],ActOut),!.

Question

What did I miss in

actors_appearing_in_movies(MovIn,ActOut) :-
   setof(Ax, ( setof(Mx,starsin(Mx,Ax),MovAx) , subset(MovIn, MovAx) ) , ActOut).

Solution

  • Try:

    actors_appearing_in_movies(MovIn,ActOut) :-
        setof(
            Ax,
            MovAx^(setof(Mx,starsin(Mx,Ax),MovAx), subset(MovIn,MovAx)),
            ActOut
        ).
    

    Without existentially qualifying the MovAx variable, you get a solution per each binding of the variable.

    Sample call:

    ?- actors_appearing_in_movies([a,b],ActOut).
    ActOut = [george, maria].