考虑以下程序，一个使用差异列表，另一个不使用:
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]).
既然两者都做同一件事，那么使用差异列表有什么好处？
最佳答案
在给出的示例中，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 = []
关于prolog - 序言差异列表，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/21199436/