了解差异列表

Question

我正在尝试理解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].

我错过了什么？谢谢.

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

第一个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)))？你不能,除了traversting表头结束和更换[]用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.