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將它們保持爲單獨的參數。但是這兩者之間的差別就在這裏。算法行爲是相同的。

一個真正的差分列表是一個列表結構與其中T沒有（在時間直到稍後點也許）實例化在其中的「洞」，像X-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 = [] 

Answer 2

你的例子中有什麼是而不是的差異列表。比較http://en.wikibooks.org/wiki/Prolog/Difference_Lists。差異列表使用將尾部保持爲已知且可以直接更改的變量的技巧。因此，它允許不斷的時間追加到列表中。但這不是你在你的例子中所做的。

看着你的例子，rev1真的只是使用-作爲分隔符，就好像它是一個逗號。我認爲唯一的區別是，在rev2中，prolog解釋器有機會以提高性能的方式對規則進行索引。不知道在這種情況下是否會有所作爲。從美學角度而言，第二種解決方案對我來說似乎也更加清潔。

Answer 3

我從來沒有見過使用'out-of-context'的差異列表，主要的上下文是DCG的實現。

這是一個基於DCG的逆向（好吧，我自己寫的，但是你也可以在基督徒鏈接的頁面中找到它）。

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