Понимание списков различий

Question

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

app(X, Y, Z) :- Z = [X|Y].

?- app([a,b,c], [z], Z).
Z = [[a,b,c],z].

ИЛИ ЖЕ

app(X, Y, Z) :- Z = [X|Hole], Hole = Y.

Те же результаты, что и в первом (они, похоже, в основном одинаковы). У меня есть пример в книге, которая работает (хотя это не предикат), и я не понимаю разницу. X становится конкретным для правильного ответа [a,b,c,z]чем это сильно отличается от моего второго примера?

X = [a,b,c|Y], Y = [z].

Что мне не хватает? Благодарю.

Answer 1

Ключом к пониманию списков различий является понимание того, что они находятся на уровне вложенного составного термина, представляющего списки. Обычно мы видим такой список:

[a, b, c]

Теперь это список с тремя элементами. Точно такой же вложенный термин, использующий точку в качестве функтора списка, ./2 и атом [] как пустой список, будет:

.(a, .(b, .(c, [])))

Здесь важно, чтобы функтор списка представлял собой составной термин с двумя аргументами: элементом и остальной частью списка. Пустой список - это атом, который, неофициально, можно рассматривать как составной термин с арностью 0, то есть без аргументов.

Теперь это список с тремя элементами, где последний элемент является свободной переменной:

[a, b, Last]

что так же, как:

.(a, .(b, .(Last, [])))

С другой стороны, это список с двумя элементами и свободной переменной как остальная часть списка, или хвост:

[a, b|Tail]

что так же, как:

.(a, .(b, Tail))

Вы видите как .(a, .(b, .(Last, []))) это не то же самое, что .(a, .(b, Tail))?

Примеряю это с верхнего уровня (я использую SWI-Prolog 7, который нуждается в --traditional флаг для лечения ./2 как термин списка):

$ swipl --traditional
Welcome to SWI-Prolog (Multi-threaded, 64 bits, Version 7.1.26)
Copyright (c) 1990-2014 University of Amsterdam, VU Amsterdam
SWI-Prolog comes with ABSOLUTELY NO WARRANTY. This is free software,
and you are welcome to redistribute it under certain conditions.
Please visit http://www.swi-prolog.org for details.

For help, use ?- help(Topic). or ?- apropos(Word).

?- [a, b, Last] = [a, b|Tail].
Tail = [Last].

?- .(a, .(b, .(Last, []))) = .(a, .(b, Tail)).
Tail = [Last].

Теперь "список различий" - это такой список: [a, b|Tail] идентично .(a, .(b, Tail)) где вы держите переменную Tail который держит хвост. Это неправильный список до Tail был создан в надлежащий список!

?- L = [a, b|Tail], is_list(L).
false.

?- L = [a, b|Tail], Tail = [c,d,e], is_list(L).
L = [a, b, c, d, e],
Tail = [c, d, e].

Вы можете посмотреть на предыдущие запросы, чтобы понять, что именно Tail = [c, d, e] делает в этом сочетании.

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

% using two arguments
foo([a,b|Tail], Tail).
% using a pair
foo([a,b|Tail]-Tail).

Первый foo/2 имеет два аргумента, второй имеет один, который является "парой". Современный код на Прологе, кажется, предпочитает два аргумента паре, но вы часто видите эту пару в учебниках и учебных пособиях.

К вашему приложению или app/3: Когда вы работаете со списками различий, вам нужен дополнительный аргумент (или пара), чтобы вы могли получить доступ к концу списка, с которым вы имеете дело. Если у вас есть только хвост списка, который будет впереди, вы все равно можете написать добавление, которое имеет только три аргумента, потому что все, что вам нужно, это объединить хвост первого списка со вторым списком:

% app(List1, Tail1, List2)
app(List1, Tail1, List2) :- Tail1 = List2.

или объединяясь прямо в голову:

app(_L1, L2, L2).

?- L1 = [a,b|Tail], app(L1, Tail, [c]).
L1 = [a, b, c],
Tail = [c].

Это точно такой же код, как в ссылке, предоставленной @Wouter.

Если у вас были хвосты обоих списков, вы замените хвост первого списка вторым списком и сохраните хвост второго списка.

app(List1, Tail1, List2, Tail2) :- Tail1 = List2.

Опять же, вы могли бы сделать объединение в голове.

РЕДАКТИРОВАТЬ:

Вы не можете сделать "дыру", когда список уже полностью создан. Как бы вы пошли от этого .(a, .(b, .(c, []))) к этому: .(a, .(b, .(c, Tail)))? Вы не можете, за исключением обхода списка до конца и замены [] с Tail, но это именно то, что обычные append/3 делает. Пытаться:

?- L = [a,b,c,d], append(L, Back, Front), Back = [x,y,z].
L = [a, b, c, d],
Back = [x, y, z],
Front = [a, b, c, d, x, y, z].

Или, если у вас есть diflist_append/3 определяется как:

diflist_append(Front, Back, Back).

Который объединяет Back списка с третьим аргументом:

?- L = [a,b,c,d], append(L, Back, Front), diflist_append(Front, Back, [x,y,z]).
L = [a, b, c, d],
Back = [x, y, z],
Front = [a, b, c, d, x, y, z].

Что касается вашего примера, X = [a,b,c], Y = [X|Z], Z = [z], это так же, как:

X = .(a, .(b, .(c, []))),
Y = .(X, Z), % Y = .(.(a, .(b, .(c, []))), Z)
Z = [z] % Y = .(.(a, .(b, .(c, []))), .(z, []))

Так ты видишь это сейчас?

Answer 2

Пол Брна объяснил это очень хорошо. Он использует переменные OpenList# а также Hole# в его версии различий добавить:

difference_append(OpenList1-Hole1, Hole1-Hole2, OpenList1-Hole2).

Пример использования:

?- difference_append([a,b,c|H1]-H1, [d,e,f|H2]-H2, L).
H1 = [d, e, f|H2],
L = [a, b, c, d, e, f|H2]-H2.