Пересечение в SWI-Пролог

Question

Я новичок в Прологе, и у меня возникли проблемы с пониманием рекурсии. Я пытаюсь написать отношение, которое находит пересечение двух отсортированных списков без использования встроенного пересечения SWI. Я использовал трассировку, чтобы увидеть, что происходит, и она ведет себя так, как я ожидаю, до того момента, когда я хочу, чтобы он завершился и возвратил новый список, содержащий пересечение. Это заставляет меня думать, что мой базовый случай неверен. Я поиграл с несколькими различными способами формирования базового варианта, но он не был плодотворным. Я использовал списки [1, 2, 3, 4] и [2, 4, 6] в качестве тестовых случаев со следующими отношениями (базовый случай сверху - это только один, который я добавил в качестве заполнителя... это не работает вообще):

intersectS([], [], []).
intersectS([A | B], [C | D], Z) :- A < C, intersectS(B, [C | D], Z).
intersectS([A | B], [C | D], Z) :- A > C, intersectS([A | B], D, Z).
intersectS([A | B], [C | D], Z) :- A = C, append(Z, [A], Y), intersectS(B, D, Y). 

Любая помощь приветствуется. Я видел примеры, где оператор cut (!) Используется вместе с членом / не членом, но я должен использовать тот факт, что списки отсортированы, поэтому я решил попробовать этот подход. Заранее спасибо.

Answer 1

В целом, у вас есть решение частично (как вы заметили). Я думаю, что есть две области, которые нужно исправить. Один из них, как вы указали, "базовый случай". Я бы сделал это следующим образом:

intersectS([], _, []).
intersectS(_, [], []).

Другими словами, все, что пересекается с пустым списком, пусто.

Вторым проблемным местом является пункт о A = C, У тебя есть:

intersectS([A | B], [C | D], Z) :- A = C, append(Z, [A], Y), intersectS(B, D, Y).

Что говорит, что если главы двух списков совпадают, то пересечение (Z) с добавлением [A] (совпадающая головка) - это пересечение хвостов двух списков. Это не кажется правильным. Я думаю, что вы хотите сказать, что пересечение (Z) это пересечение хвостов B а также D добавлен в [A], который выглядит так:

intersectS([A | B], [C | D], Z) :- A = C, append([A], Y, Z), intersectS(B, D, Y).

Так что все выглядит так:

intersectS([], _, []).
intersectS(_, [], []).
intersectS([A | B], [C | D], Z) :- A < C, intersectS(B, [C | D], Z).
intersectS([A | B], [C | D], Z) :- A > C, intersectS([A | B], D, Z).
intersectS([A | B], [C | D], Z) :- A = C, append([A], Y, Z), intersectS(B, D, Y).

Вы можете сделать еще один шаг и избавиться от append так как вы просто имеете дело с одним элементом. append([A], Y, Z) это то же самое, что сказать Z = [A|Y], Таким образом, вы можете заменить последнее предложение просто:

intersectS([A | B], [C | D], [A | Y]) :- A = C, intersectS(B, D, Y).

Запуск вашего теста:

?-  intersectS([1, 2, 3, 4], [2,4,6], L).
L = [2, 4] ;
false.

?-