Find mutual element in different facts in swi-prol

Question

i am trying to have an input of a list of movies and find the actors who play at the same movies. Question : Given a list of movies, display their link by a set of stars using recursion. these are an example of facts :

fact(movie,actor).

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

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

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

Example of input and out put :

?- sameActors([a,b,c],Y).
 Y = bob,maria,george.

Rule written so far :

sameActors(Actors,Movies) :-
      findall(Stars,(member(movie,Actors),starsin(movie,Stars)),Name),
      sum_list(Name,Movies).

I am quite new and can't find any similar solution online for my problem, i don't understand what i am doing wrong , or what i need to add.

Answer 1

Here is another one (I finally found a way)

No recursion, just a relative of findall, setof/3:

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).

We do some reflection (described in setof/3 inside setof/3 not working, but why?), and then:

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

This has the right feel of being an RDBMS operation!

Testing!

Note that for the empty set of movies, we get all the actors. This is marginally right: all the actors star in all the movies of the empty set.

Testing consists in running these goals and observing that they succeed:

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),!.

Bonus Round: In R

Completely unrelated, but I thought about how to do that in R.

After some fumbling:

# Load tidyverse dplyr

library(dplyr)

# Create a data frame ("tibble") with our raw data using `tribble`

t <- tribble(
        ~movie, ~actor
        ,"a"   , "bob"
        ,"c"   , "bob"
        ,"a"   , "maria"
        ,"b"   , "maria"
        ,"c"   , "maria"
        ,"a"   , "george"
        ,"b"   , "george"
        ,"c"   , "george"
        ,"d"   , "george")

# The function!

actors_appearing_in_movies <- function(data, movies_must) {
   # (movie,actor) pairs of actors active in movies we are interested in 
   t1 <- data %>% filter(is.element(movie, movies_must))

   # (actor, (movies)) pairs of actors and the movies they appear in
   # for movies we are interested in 
   t2 <- t1 %>% group_by(actor) %>% summarize(movies = list(unique(movie)))   

   # Retain only those which appear in all movies
   t3 <- t2 %>% rowwise() %>% filter(setequal(movies_must,movies))

   # Select only the actor column
   # ("Select" works columnwise, not rowwise as in SQL)   
   t4 <- t3 %>% select(actor)

   return(t4)
}

Results?

The above approach has a different opinion on who is in the empty movie set:

> actors_appearing_in_movies(t, c())
# A tibble: 0 x 1
# … with 1 variable: actor <chr>

But:

> actors_appearing_in_movies(t, c("a"))

# A tibble: 3 x 1
  actor 
  <chr> 
1 bob   
2 george
3 maria 

> actors_appearing_in_movies(t, c("a","b"))

# A tibble: 2 x 1
  actor 
  <chr> 
1 george
2 maria 

> actors_appearing_in_movies(t, c("a","b","c"))

# A tibble: 2 x 1
  actor 
  <chr> 
1 george
2 maria 

> actors_appearing_in_movies(t, c("a","b","c","d"))

# A tibble: 1 x 1
  actor 
  <chr> 
1 george

Answer 2

Here is the code

sameActors([Movie|Movies],Actors) :-
    actors(Movie,[],Actors0),   % prime the list with the full set of actors from first movie
    prune_actors(Movies,Actors0,Actors). % prune out actors not in all movies
sameActors([],[]).

actors(Movie,Collected,Actors) :-
    starsin(Movie,Actor),
    \+ member(Actor,Collected),
    actors(Movie,[Actor|Collected],Actors), !.
actors(_,Actors,Actors).

% Prune actors based on a set of movies.
prune_actors([],Actors,Actors).
prune_actors([Movie|Movies],Actors0,Actors) :-
    prune_actors_2(Movie,Actors0,Actors1),
    prune_actors(Movies,Actors1,Actors).

% Prune actors based on a single movie
prune_actors_2(_,[],[]).
prune_actors_2(Movie,[Actor|Actors0],[Actor|Actors]) :-
    starsin(Movie,Actor),
    prune_actors_2(Movie,Actors0,Actors), !.
prune_actors_2(Movie,[Actor|Actors0],Actors) :-
    \+ starsin(Movie,Actor),
    prune_actors_2(Movie,Actors0,Actors).

Example run as shown in question.

?- sameActors([a,b,c],Y).
Y = [george, maria, bob].

---

Explanation of code

This is just a few predicates working recursively together with one tricky part.

The tricky part is that normally when you get a value from facts and the result could be from more than one fact and if the code is recursive, then each time you use the goal to access the facts, the first fact that matches is always chosen and so the code goes into an infinite loop. The trick to stop this is the same trick used when doing a search of a graph that can have cycles and that is to keep track of where you have been. In this case the goal that accesses the facts has check right after the values for the matching fact is found and then the check is made. If the check fails, then the goal is reevaluated, but because the first fact was used, the next fact is then tired. This continues until a fact either passes the check, or the entire predicate fails.

The goal for the facts is starsin(Movie,Actor) and the check is \+ member(Actor,Collected). Since this answer asked for the code not to use findall/3 and instead use recursive code that is what is done here. In real world code findall/3 should be used instead of what is done here because it is extremely inefficient.

With that out of the way the rest of the code is easily understood as recursive code that takes list apart and constructs list using the concatenation operator |.

---

Coping part of my answer from another answer.

List in Prolog are build using the list constructor operator, | and recursively constructed and deconstructed using the | operator. As 0 is the initial value for counting integers, [ ], known as the empty list, is the initial value for a closed list. Then to recursively build to the front of a closed list one uses the current list and the | operator. When using | it in Prolog is is common to refer to the item being added as the head, (H) and the current closed list being added to as the tail, (T), and this why you often see the notation [H|T] when talking about list in Prolog.

So to construct the list [1,2,3] would be [] then add 1, [ 1]. To add 2 would be [1,2].

To deconstruct the list [1,2,3] would use variables so [H|T] will become [1|T] with T being [2,3]. When you get to the end of the list it is just [] with out a head.

---

The comments in the code explain what is going on at a higher level.