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)
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...
Clarify the problem:
Sets are represented by lists without duplicates, possibly ordered.
- Given a Set of Movies
MovIn
- ... Find the Set of Actors
ActOut
- ... ... Such that: Every Actor in
ActOut
appeared in (at least) all the movies inMovIn
- ... ... Reformulated: The Set of Movies
MovAx
for any actorAx
ofActOut
is a superset ofMovIn
.
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.
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].
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 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),!.
What did I miss in
actors_appearing_in_movies(MovIn,ActOut) :-
setof(Ax, ( setof(Mx,starsin(Mx,Ax),MovAx) , subset(MovIn, MovAx) ) , ActOut).
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].