1

当我在一个空列表上写下这个问题作为差异列表时，我想测试我对这些结构的了解。然而，当我尝试像比较不同符号这样简单的事情时，似乎我错了，我不明白差异列表的实际情况。

?- L = [a,b,c|[d,e]]-[d,e], L = [a,b,c].
false % expected true

我在 SWI-Prolog 和 SICStus 上对此进行了测试。我验证了这个符号，因为这是 Bratko 的 Prolog Programming for AI，第 210 页中的写法，但显然不可能统一。这是为什么？这些符号不具有相同的声明意义吗？

4

1 回答 1

5

我认为您认为 Prolog 解释器将差异列表视为特殊的东西。情况并非如此：Prolog 不知道差异列表的概念（除了一些语法糖之外，几乎所有概念也不知道）。他只看到：

L=-( |(a, |(b, |(c, |(d, |(e, []))))), |(d, |(e, [] )))

其中-/2和|/2是函子，、a、b、c和是常数。de[]

差异列表只是一种编程技术（例如动态编程也是一种技术，编译器无法检测或区别对待动态编程程序）。它用于有效地统一表达式深处的（部分）未统一部分。

假设您想要append/3两个列表。您可以按如下方式执行此操作：

%append(A,B,C).
append([],L,L).
append([H|T],L,[H|B]) :-
    append(T,L,B).

但这在O(n)中运行：您首先需要遍历整个第一个列表。如果该列表包含数千个元素，则将花费大量时间。

现在您可以为自己定义一个合同，您将append_diff/3不仅提供列表，而且提供一个元组-(List,Tail)，其中List是对列表开头的引用，并且Tail是对非统一列表末尾的引用。满足此要求的结构示例有Tail-Tail, [a|Tail]-Tail, [1,4,2,5|Tail]-Tail.

现在您可以append_diff/3在O(1)中有效地使用：

append_diff(H1-T1,T1-T2,H1-T2).

为什么？因为您将第一个列表的未统一尾部与第二个列表统一起来。现在第二个列表的未统一尾部成为最终列表的尾部。所以举个例子：

append_diff([a|T1]-T1,[1,4,2,5|T2]-T2,L).

如果你调用谓词，如上所见，T1将与 统一[1,4,2,5|T2]，所以现在第一个列表折叠到[a|[1,4,2,5|T2]]或更短[a,1,4,2,5|T2]，因为我们也有对 的引用T2，我们可以“返回”（在 Prolog 中什么都不返回） ，：[a,1,4,2,5|T2]-T2一个新的区别带有开尾的列表T2。但这只是因为您自己赋予-了特殊含义：因为 Prolog-是简单-的，它不是减号，它不计算差异等。Prolog 不将语义附加到函子。如果您使用+而不是-，那将不会有丝毫不同。

所以回到你的问题：你只需向 Prolog 声明，L = -([a,b,c,d,e],[d,e])然后再声明L = [a,b,c]. 现在很清楚，这两种表达方式不能统一。所以 Prolog 说false。

于 2017-01-11T13:50:53.303 回答