如何在 Prolog 解释器中使用差异列表 [英] How to use difference lists in a Prolog interpreter

问题描述

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

When I was writing down this question on an empty list as a difference list I wanted to test what I knew about those structures. However, when I tried something as simple as comparing different notations it seemed that I was wrong and that I did not understand what is actually going on with difference lists.

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

我在 SWI-Prolog 和 SICStus 上对此进行了测试.我验证了这个符号，因为它是 Bratko 的 Prolog Programming for AI，第 210 页中的编写方式，但显然无法统一.这是为什么?这些符号不是具有相同的声明性含义吗?

I tested this on SWI-Prolog as well as SICStus. I verified the notation as this is how it is written in Bratko's Prolog Programming for AI, page 210, but apparently unification is not possible. Why is that? Don't these notations have the same declarative meaning?

推荐答案

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

I think you have the idea that the Prolog interpreter treats difference lists as something special. That is not the case: Prolog is not aware of the concept of a difference list (nor of nearly every concept except some syntactical sugar). He only sees:

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

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

where -/2 and |/2 are functors, and a, b, c, d, e and [] are constants.

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

Difference lists are simply a programming technique (like for instance dynamic programming is a technique as well, the compiler cannot detect nor treat dynamic programming programs differently). It is used to efficiently unify a (partially) ununified part deep in an expression.

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

Say you want to append/3 two lists. You can do this as follows:

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

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

But this runs in O(n): you first need to iterate through the entire first list. If that list contains thousands of elements, it will take a lot of time.

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

Now you can define yourself a contract that you will feed an append_diff/3 not only the list, but a tuple -(List,Tail) where List is a reference to the beginning of the list, and Tail is a reference to the end of the not unified list. Examples of structures that fulfill this requirement are Tail-Tail, [a|Tail]-Tail, [1,4,2,5|Tail]-Tail.

现在你可以在O(1)中有效地append_diff/3:

Now you can effectively append_diff/3 in O(1) with:

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

为什么?因为您统一第一个列表的未统一尾部与第二个列表.现在，第二个列表的未统一尾部成为最终列表的尾部.举个例子:

Why? Because you unify the ununified tail of the first list with the second list. Now the ununified tail of the second lists becomes the tail of the final list. So take for instance:

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 不会不将语义附加到函子上.如果您使用 + 而不是 -，那不会有丝毫的不同.

If you call the predicate, as you see above, T1 will unify with [1,4,2,5|T2], so now the first list collapses to [a|[1,4,2,5|T2]] or shorter [a,1,4,2,5|T2], since we also have a reference to T2, we can "return" (in Prolog nothing is returned), [a,1,4,2,5|T2]-T2: a new difference list with an open tail T2. But this is only because you give - a special meaning yourself: for Prolog - is simply -, it is not minus, it does not calculate a difference, etc. Prolog does not attach semantics to functors. If you would have used + instead of -, that would not have made the slightest difference.

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

So to return back to your question: you simply state to Prolog that L = -([a,b,c,d,e],[d,e]) and later state that L = [a,b,c]. Now it is clear that those two expressions cannot be unified. So Prolog says false.

这篇关于如何在 Prolog 解释器中使用差异列表的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！