4

Prolog (SWI) の宿題に取り組んでいますが、これを行う方法がわかりません。

私はファンクターを持っています:

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

これは、与えられたリストが回文であるかどうかを示します。

宿題として、差分リストを使用する場合と使用しpalindrome/2ない場合のファンクターを作成する必要があります。append/3

差分リストが の形式であることは知っていますが、[Y|X]-Xこれを使用する方法と、これが追加ファンクターをどのように置き換えることができるかがわかりません。

誰かが私にこれを説明してもらえますか?

4

2 に答える 2

6

長さnの特定のリストについて、ソリューションにはいくつかの O( n 2 ) 推論が必要です: /1の場合はn (実際にはn/2 )、それぞれの場合はiであり、単純に最後を検索して比較します。palindromeappend/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].

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

于 2012-03-13T13:08:09.027 に答える
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).

Append for dif-lists はappend(A-B,B-C,A-C)であるため、append 呼び出しは をZ2=[A|Z3], Z3=Z, Middle=T返し、(述語の 2 つの引数として dif-list の 2 つの半分を書き出す)、

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 ルールは差分リストへの快適なインターフェイスを提供します。

于 2012-03-17T12:20:34.180 に答える