我试图理解 Prolog 中的差异列表，但我正在努力正确地实现一个，每次我尝试这样做时，我都会得到一个列表列表，但这不是我想要的。我正在尝试实现附加谓词，但到目前为止运气不佳。很少尝试，所有这些都不起作用。
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].
我错过了什么？谢谢。
理解差异列表的关键是在表示列表的嵌套复合术语级别上理解它们是什么。通常，我们会看到这样的列表：
[a, b, c]
现在这是一个包含三个元素的列表。./2使用点作为列表函子、原子[]作为空列表的完全相同的嵌套项将是：
.(a, .(b, .(c, [])))
重要的是，列表函子是具有两个参数的复合项：元素和列表的其余部分。空列表是一个原子，非正式地，可以将其视为具有 arity 0 的复合项，即没有参数。
现在，这是一个包含三个元素的列表，其中最后一个元素是自由变量：
[a, b, Last]
这与以下内容相同：
.(a, .(b, .(Last, [])))
另一方面，这是一个包含两个元素和一个自由变量的列表，作为列表的其余部分，或tail：
[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有两个参数，第二个有一个，这是一个“对”。现代 Prolog 代码似乎更喜欢两个参数而不是一对，但你经常在教科书和教程中看到这对。
附加到您的附加或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, []))
所以你现在看到了吗？
Paul Brna 已经很好地解释了这一点。他使用变量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.