如何使用差异表的Prolog的解释

Question

当我写下this question on an empty list as a difference list我想考什么，我知道那些结构。但是，当我尝试一些比较不同符号的简单事情时，似乎我错了，并且我确实知道实际上差异列表正在发生什么。

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

我在SWI-Prolog和SICStus上测试了这个。我验证了这个符号，因为它是如何写在Bratko的人工智能Prolog编程中，第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。

现在可以有效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说明L = -([a,b,c,d,e],[d,e])和后来的状态即L = [a,b,c]。现在很明显，这两种表达方式是不能统一的。所以Prolog说false。