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]).

由于两者都做同样的事情，使用差异列表有什么好处？

4

3 回答 3

11

在给出的示例中，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 = []
于 2014-01-18T04:09:59.487 回答
4

您在示例中的内容不是差异列表。比较http://en.wikibooks.org/wiki/Prolog/Difference_Lists。差异列表使用将尾部保持为已知且可以直接更改的变量的技巧。因此，它允许恒定时间附加到列表。但这不是您在示例中所做的。

然后看看你的例子，rev1真的只是-用作分隔符，就好像它是一个逗号。我认为唯一的区别是，rev2prolog 解释器有机会以提高性能的方式索引规则。不确定在这种情况下是否会有所作为。从美学上讲，第二种解决方案对我来说似乎也更干净。

于 2014-01-18T05:24:00.963 回答
3

我从未见过使用“脱离上下文”的差异列表，主要上下文是 DCG 的实现。

这是一个基于 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 ...

于 2014-01-18T17:51:14.927 回答