如何使用差異表的Prolog的解釋

Question

當我寫下this question on an empty list as a difference list我想考什麼，我知道那些結構。但是，當我嘗試一些比較不同符號的簡單事情時，似乎我錯了，並且我確實知道實際上差異列表正在發生什麼。

?- L = [a,b,c|[d,e]]-[d,e], L = [a,b,c]. 
false % expected true 

我在SWI-Prolog和SICStus上測試了這個。我驗證了這個符號，因爲它是如何寫在Bratko的人工智能Prolog編程中，第210頁，但顯然統一是不可能的。這是爲什麼？這些符號不具有相同的聲明意義嗎？

Answer 1

我認爲你有這樣的想法，Prolog解釋器將差異列表視爲特殊的東西。情況並非如此：Prolog沒有意識到差異列表的概念（幾乎除了某些語法糖之外的幾乎所有概念）。他只看到：

L=-(|(a, |(b, |(c, |(d, |(e, []))))), |(d, |(e, []))) 

其中-/2和|/2是仿函數，並a，b，c，d，e和[]是常數。

差異列表是一個簡單的編程技術（例如像動態規劃是一種技術，以及時，編譯器無法檢測，也不區別對待動態編程程序）。它用於高效地將表達式中的（部分）非統一部分統一起來。

說要append/3兩個列表。你可以這樣做如下：

%append(A,B,C). 
append([],L,L). 
append([H|T],L,[H|B]) :- 
    append(T,L,B). 

但這運行在O（n）的：您首先需要通過整個第一個列表進行迭代。如果該列表包含數千個元素，則需要很長時間。

現在，您可以定義自己合同，你會養活append_diff/3不僅列表中，但一個元組-(List,Tail)其中List是到列表的開始時的參考，並Tail是的末尾引用沒有統一的名單。符合此要求的結構示例爲Tail-Tail,[a|Tail]-Tail,[1,4,2,5|Tail]-Tail。

現在可以有效append_diff/3在O（1）有：

append_diff(H1-T1,T1-T2,H1-T2). 

爲什麼？因爲你統一第一個列表的非統一的尾巴與第二個列表。現在第二個列表的非統一尾部成爲最終列表的尾部。因此，採取例如：

append_diff([a|T1]-T1,[1,4,2,5|T2]-T2,L). 

如果調用謂詞，正如你看到的上面，T1將與[1,4,2,5|T2]統一，所以現在第一個列表摺疊到[a|[1,4,2,5|T2]]或更短[a,1,4,2,5|T2]，因爲我們也有一個參考T2，我們可以「返回」（在Prolog中沒有任何內容是返回），[a,1,4,2,5|T2]-T2：帶有開尾的新差異列表T2。但是，這僅僅是因爲你給-特殊的含義自己：爲序言-簡直是-，它不是減去，它不計算差值等Prolog的不不重視語義函子。如果你會使用+而不是-，那就不會有絲毫的區別。

所以要回到你的問題：你只需向Prolog說明L = -([a,b,c,d,e],[d,e])和後來的狀態即L = [a,b,c]。現在很明顯，這兩種表達方式是不能統一的。所以Prolog說false。