如何在 Prolog 解释器中使用差异列表

Question

当我写下时，我想测试一下我对这些结构的了解。然而，当我尝试比较不同符号这样简单的事情时，我似乎错了，我确实不理解差异列表的实际情况。

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

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

Answer 1

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

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

其中 -/2 和 |/2 是函子，a、b、c、d、e [] 是常量。

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

假设您想要 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.

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

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 的引用，我们可以 "return" （在 Prolog 中没有什么是 returned），[a,1,4,2,5|T2]-T2：a带有开尾的新差异列表 T2。但这只是因为你自己给-一个特殊的意义：对于Prolog -只是-，它不是 minus，它不计算差异等。Prolog 不将语义附加到函子。如果您使用 + 而不是 -，那将不会产生丝毫差异。

因此 return 回到您的问题：您只需向 Prolog 声明 L = -([a,b,c,d,e],[d,e])，然后再声明 L = [a,b,c]。现在很明显，这两种说法不能统一。所以 Prolog 说 false.

如何在 Prolog 解释器中使用差异列表

How to use difference lists in a Prolog interpreter

prolog

difference-lists