Prolog的轉換與仿函數差函子列出

Question

我的工作我的家庭作業的Prolog（SWI），但無法弄清楚如何得到這個工作：

我有仿函數：

palindrome([]). 
palindrome([_]). 
palindrome([A|T]) :- 
     append(Middle,[A],T), 
     palindrome(Middle). 

它告訴給定的列表是否是迴文。

對於我的作業，我必須寫一個仿函數palindrome/2而不是append/3和差異列表。

我知道一個差異列表是[Y|X]-X的一種形式，但我不明白如何使用它以及它如何替換追加函數。

有人可以向我解釋這個嗎？

Answer 1

對於長度Ñ的一個給定的列表中，解決方案需要一些O（Ñ）推論：Ñ（實際上 N/2）爲palindrome/1和我每個append/3，它只是搜索和比較結束。

重新定義定義的最直接的方法是使用語法（DCG），這是一種使用差異列表的便捷方式。請注意，每個語法規則都對應於程序中的一個子句。

palindrome --> 
    []. 
palindrome --> 
    [_]. 
palindrome --> 
    [A], 
    palindrome, 
    [A]. 

palindrome(T) :- 
    phrase(palindrome,T). 

爲了方便起見，這裏寫的是更緊湊相同的語法：

palindrome --> [] | [_] | [A], palindrome, [A]. 

現在，如何在這些語法規則來實現？最簡單的方法是用listing(palindrome)查看實際定義。

?- listing(palindrome). 
palindrome(A, A). 
palindrome([_|A], A). 
palindrome([C|A], D) :- 
    palindrome(A, B), 
    B=[C|D]. 

所以這現在是您的定義使用差異列表。

Answer 2

只要自己寫下來。你有

palindrome([]).   % palindrome(Z-Z). 
palindrome([_]).   % palindrome([_|Z]-Z). 
palindrome([A|T]) :-  % palindrome([A|T]-Z):- 
    append(Middle,[A],T), % append(Middle-Z2,[A|Z3]-Z3,T-Z), 
    palindrome(Middle).  % palindrome(Middle-Z2). 

追加爲DIF-列表爲append(A-B,B-C,A-C)，所以追加期權給予我們Z2=[A|Z3], Z3=Z, Middle=T，等（寫出一個DIF列表的兩個部分作爲兩個參數謂詞），

palindrome(Z,Z). 
palindrome([_|Z],Z). 
palindrome([A|T],Z) :- 
    palindrome(T, [A|Z]). 

現在你可以運行它

10 ?- palindrome(X,[]). 

X = [] ; 
X = [_G340] ; 
X = [_G340, _G340] ; 
X = [_G340, _G346, _G340] ; 
X = [_G340, _G346, _G346, _G340] ; 
.... 

11 ?- X=[a,b,c|_],palindrome(X,[z]). 

X = [a, b, c, b, a, z] ; 
X = [a, b, c, c, b, a, z] ; 
X = [a, b, c, _G460, c, b, a, z] ; 
X = [a, b, c, _G460, _G460, c, b, a, z] ; 
.... 

16 ?- palindrome([1,2,2,1,0],Z). 

Z = [1, 2, 2, 1, 0] ; 
Z = [2, 2, 1, 0] ; 
Z = [0] ; 
No 

當然，DCG規則差異，列表提供一個舒適的界面。