Prolog差异列表

Question

Prolog差异列表

7

考虑以下两个程序，一个使用差异列表，另一个则没有：

reverse1(List1,R) :- rev1(List1, R-[]).
rev1([], A-A).
rev1([H|T], C-A) :-rev1(T, C - [H|A]).

reverse2(List1,R) :- rev2(List1, R, []).
rev2([], A, A).
rev2([H|T], C, A) :- rev2(T, C, [H|A]).

既然两者都能完成同样的任务，使用差异列表的好处是什么？

- Melanie A

感谢大家及时的回答。 - Melanie A

3个回答

4

你的示例中使用的不是差异列表。请参阅http://en.wikibooks.org/wiki/Prolog/Difference_Lists。差异列表使用将尾部作为变量并直接更改它的技巧。因此，它允许在常数时间内添加到列表中。但这不是你在示例中所做的。

看着你的例子，rev1实际上只是使用-作为分隔符，就像逗号一样。我推测唯一的区别是，在rev2中，Prolog解释器有机会以提高性能的方式索引规则。不确定在这种情况下是否会有任何区别。从美学角度来看，第二个解决方案对我来说更加清洁。

- Christian Fritz

3

我从未见过差异列表在“非上下文”的情况下使用，主要上下文是DCGs实现。

这里是基于DCG的反转（虽然我自己写的，但你也可以在Christian链接的页面中找到它）。

reverse3(L,R) :- phrase(rev3(L),R).
rev3([]) --> [].
rev3([H|T]) --> rev3(T),[H].

列出它的证据可以说明你的reverse2几乎是完全相同的：

?- listing(rev3).
stackoverflow:rev3([], A, A).
stackoverflow:rev3([D|A], B, E) :-
    rev3(A, B, C),
    C=[D|E].

所有这些定义都存在一个问题：当在“反向”模式下使用时，即在第一个解决方案回溯后，它们会形成循环。

?- reverse1(R,[a,b,c]).
R = [c, b, a] ; (^C here)
Action (h for help) ? abort
% Execution Aborted

看看适当且高效的库实现将会很有趣：

?- listing(reverse).
lists:reverse(A, B) :-
    reverse(A, [], B, B).

lists:reverse([], A, A, []).
lists:reverse([B|A], C, D, [_|E]) :-
    reverse(A, [B|C], D, E).

这里没有区别列表！

关于你的问题，我会说区别列表唯一的好处就是更好地理解Prolog...

- CapelliC

1

实际上，lists:reverse/4 的第三个和第四个参数形成一个差异列表，它以空列表（B-B）开头，并在每一步中增加一个非约束元素的长度，因此第四个参数表示第三个参数的渐进尾部。 :) - Will Ness

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- lurker · Accepted Answer

在给定的例子中，reverse1并没有使用真正的差分列表，而只是reverse2的另一种表示形式。它们都以相同的方式使用相同的变量。reverse使用-函数符将它们连接起来，而reverse2将它们作为单独的参数维护。但这就是两者之间的全部区别。算法行为是相同的。

一个真正的差分列表是一个带有“洞”的列表结构，比如X-T，其中T没有被实例化（直到以后某个时间点），而X包含T（例如[a,b,c|T]-T）。这里的-函数符将“暴露”的未实例化变量与包含它的结构关联起来。

一个流行且简单的例子是使用差分列表实现append。传统的递归实现append的方法可能是这样的：

append([], Ys, Ys).
append([X|Xs], Ys, [X|Zs]) :- append(Xs, Ys, Zs).

这很简单，并且执行时间与第一个列表的长度成比例。

使用差异列表，您可以按如下方式实现append：

append(A-B, B-C, A-C).

使用差异列表添加列表所需的全部内容都在这里了。没有递归或其他任何东西。执行时间为O(1)，与列表长度无关。以下是一个示例执行：

append([1,2,3|T]-T, [4,5,6|W]-W, DL).

产出：

DL = [1,2,3,4,5,6|W]-W
T = [4,5,6|W]

在最后一个参数中使用空列表来“填充”空洞，即可得到具体的答案：

append([1,2,3|T]-T, [4,5,6|W]-W, L-[]).

你将获得：

L = [1,2,3,4,5,6]
T = [4,5,6]
W = []