変換差が関手するプロローグファンクタは

Question

を示しています私は、プロローグ（SWI）のための私の宿題に取り組んでいるが、これを成し遂げる方法を見つけ出すことはできません。

私はファンクタを持っている：

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

は、指定されたリストが回文であるかどうかを示します。

私の宿題については、palindrome/2をappend/3なしで、違いリストとともに書く必要があります。

私は違いリストが[Y|X]-Xの形式であることを知っていますが、これをどのように使用するのか、これがどのようにして追加関数を置き換えることができるのか分かりません。

誰かが私にこれを説明できますか？長 Nの所定のリストについて

Answer 1

、ソリューションは、（ N）推論一部Oを必要とする：palindrome/1とため N（実際 N/2）I各々についてappend/3は、単に最後を検索して比較します。

定義を再定式化する最も簡単な方法は、差異リストを使用する便利な方法である文法（DCG）を使用することです。各文法ルールはプログラム内の節に対応しています。さて、どのようにこれらの文法規則が

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

を実装されています：

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

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

便宜上、ここではよりコンパクトに書かれた同じ文法がありますか？最も簡単な方法は、listing(palindrome)で実際の定義を見ることです。

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

これは、差分リストを使用した定義です。

Answer 2

自分で書き留めてください。あなたはappend(A-B,B-C,A-C) DIF-リストの

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

追加をされているので、追記コールは私たちにZ2=[A|Z3], Z3=Z, Middle=Tを与え、そう（述語のための2つの引数として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ルールが違い-リストに快適なインターフェースを提供し実行することができます。