理解差异列表

Question

理解差异列表

20

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

我错过了什么？谢谢。

- hcaulfield57

这是一个古老而棘手的“以空间换时间”的问题。 - CapelliC

3

差分列表只是所谓“不完整数据结构”中更简单的一种。在Prolog中，基础知识是...你不应该尝试自己实现它们（当然可以研究其原理），而是应该学习应用的差分列表DGC。请参阅Markus页面进行介绍。 - CapelliC

@CapelliC 我同意DCGs在几乎所有情况下都更好。然而，至少SWI-Prolog有一些内置谓词可以使用差异列表（因为它们必须：例如read_pending_input/3），所以不幸的是，差异列表无法完全避免，至少在没有纯输入/输出的完整实现的情况下。 - user1812457

值得关注的是：SWI-Prolog讨论区论坛 - Wiki: 差分列表 - Guy Coder

2个回答

8

Paul Brna已经非常好地解释了这个问题。在他的差分列表版本的append中，他使用变量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.

- Wouter Beek

谢谢提供链接，我之前已经看过了，但现在能更好地理解实际发生的事情。 - hcaulfield57

Paul Brna的课程笔记可以在此PDF链接中找到：http://www.cs.fsu.edu/~cap5605/brna/bk.pdf。请前往第12.2节“开放列表和差异列表”以查看上述内容。 - Kristopher Johnson

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- user1812457 · Accepted Answer

理解差分列表的关键是理解它们在表示列表的嵌套复合术语层面上是什么。通常我们看到的是这样的一个列表：

[a, b, c]

这是一个有三个元素的列表。使用点作为列表构造器的嵌套术语，./2，以及原子 [] 作为空列表，将是：

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

在这里很重要的一点是，列表函子是一个具有两个参数的复合术语：元素和列表的其余部分。空列表是一个原子，可以非正式地看作是一个没有参数的元数为0的复合术语。

现在，这是一个具有三个元素的列表，其中最后一个元素是一个自由变量：

[a, b, Last]

这与以下内容相同：

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

另一方面，这是一个包含两个元素和自由变量作为列表其余部分（或称为 tail）的列表：

[a, b|Tail]

这与以下内容相同：

.(a, .(b, Tail))

你看到了如何使用.(a, .(b, .(Last, [])))和.(a, .(b, Tail))是不同的吗？

从顶层尝试这个（我正在使用需要--traditional标志将./2作为列表项处理的SWI-Prolog 7）:

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

将列表的后面与第三个参数统一：

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

现在你看到了吗？