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

当我把这个问题写在一个空列表上作为差异列表时,我想测试我对这些结构的了解.然而,当我尝试一些简单的事情,比如比较不同的符号时,似乎我错了,而且我不明白差异列表实际发生了什么.

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

我在SWI-Prolog和SICStus上测试了这个.我验证了符号,因为它是如何在Bratko的人工智能Prolog编程中编写的,第210页,但显然统一是不可能的.这是为什么？这些符号不具有相同的声明含义吗？

1> Willem Van O..：

---

我认为您认为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不会将语义附加到仿函数上.如果你会使用+而不是-,那就不会有任何影响.

所以回到你的问题:你只是说Prolog,L = -([a,b,c,d,e],[d,e])然后说明L = [a,b,c].现在很明显,这两个表达式无法统一.所以Prolog说false.

---

@BramVanroy:你可以使用`conc_d([a,b | T] -T,[d,e | T1] -T1,Temp),敲定(Temp,L)`然后处理`L`,即`[ A,b,C,d]`.重点主要是效率:算法将在O(1)而不是O(n)中运行.但正如Prolog之前所说的那样,没有解释任何结构:数据的语义只存在于程序员的*grace*,而不是functor本身.请注意,您不必使用`finalize/2`:您可以简单地编写一个程序,其中所有子句都将diff-lists作为参数.您可以像对待简单列表一样对差异列表进行分析和处理.