Prolog差异列表

Question

考虑以下程序,一个使用差异列表,另一个不是:

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

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

Answer 1

在给出的示例中,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 = []