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

Question

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

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

Здесь важно, что список функтор термин соединения с двумя аргументами: элемент и остальную часть списка. Пустым списком является атом, который неофициально можно рассматривать как составной термин с arity 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). 

The первый foo/2 имеет два аргумента, второй - один, который является «парой». Современный код Prolog, кажется, предпочитает два аргумента для пары, но вы часто видите пару в учебниках и учебниках.

К вашей Append или 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. 

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

EDIT:

Вы не можете сделать «дыру» после того, как список уже полностью инстанцирован. Как вы идете от этого .(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

Paul Brna has explained this very well. Он использует переменные OpenList# и Hole# в его разностной список версии Append:

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.