Найти общий элемент в различных фактах в swi-prolog

Question

Я пытаюсь получить список фильмов и найти актеров, которые играют в тех же фильмах. Вопрос: Учитывая список фильмов, отобразите их ссылку набором звездочек, используя рекурсию. Вот примеры фактов:

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

Пример ввода и вывода:

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

Правило написано:

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

Я новичок и не могу найти аналогичного решения в Интернете для моей проблемы, я не понимаю, что я делаю неправильно, или что мне нужно добавить.

Answer 1

Вот еще один (я наконец нашел способ)

Никакой рекурсии, просто родственник findall, setof/3:

С учетом базы данных "актеров, снимающихся в кино":

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

Мы делаем некоторое отражение (описано в setof / 3 внутри setof / 3, не работает, но почему? ), а затем:

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

Бонус-раунд: В R

Совершенно не связано, но я думал о том, как это сделать в R.

После некоторого возни:

# 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)
}

Результаты?

Приведенный выше подход имеет другое мнение о том, кто находится в пустом наборе mov ie:

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

Но:

> 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

Вот код

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

Пример выполнения, как показано в вопросе.

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

---

Объяснение кода

Это всего лишь несколько предикатов, работающих рекурсивно вместе с одной сложной частью.

Сложная часть заключается в том, что обычно, когда вы получаете значение из фактов, а результат может быть из более чем одного факта, и если код рекурсивный, затем каждый раз, когда вы используете цель для доступа к фактам, всегда выбирается первый совпадающий факт, и поэтому код переходит в бесконечное число l oop. Уловка, чтобы остановить это - та же самая уловка, используемая, делая поиск графика, у которого могут быть циклы, и который отслеживает, где вы были. В этом случае цель, которая обращается к фактам, проверяется сразу после того, как найдены значения для совпадающего факта, и затем выполняется проверка. Если проверка не проходит, то цель переоценивается, но поскольку использовался первый факт, следующий факт устает. Это продолжается до тех пор, пока факт не пройдет проверку или не произойдет сбой всего предиката.

Цель для фактов - starsin(Movie,Actor), а проверка - \+ member(Actor,Collected). Так как этот ответ попросил код не использовать findall / 3, а вместо этого использовать рекурсивный код, что и делается здесь. В реальном мире код findall / 3 должен использоваться вместо того, что делается здесь, потому что он крайне неэффективен.

При этом остальная часть кода легко понимается как рекурсивный код, который разбирает список на части и список конструкций с использованием оператора конкатенации | .

---

Копирование части моего ответа из другого ответа .

Список в Прологе строится с использованием оператор конструктора списка, | и рекурсивно построены и деконструированы с использованием | оператор. Поскольку 0 является начальным значением для подсчета целых чисел, [], известное как пустой список, является начальным значением для закрытого списка. Затем для рекурсивного построения переднего плана закрытого списка используется текущий список и | оператор. При использовании | в Прологе принято называть элемент, добавляемый в качестве заголовка, (H), а текущий закрытый список, добавляемый в качестве хвоста, (T), и именно поэтому вы часто видите обозначение [H | T], когда говоря о списке в Прологе.

Таким образом, для построения списка [1,2,3] было бы [], а затем добавить 1, [1]. Для добавления 2 было бы [1,2].

Для деконструкции списка [1,2,3] использовались бы переменные, поэтому [H | T] станет [1 | T] с T, равным [2, 3]. Когда вы дойдете до конца списка, это просто [] без головы.

---

Комментарии в коде объясняют, что происходит на более высоком уровне.