6

特にこの述語では、差分リストを理解するのに苦労しています:

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

何が起こっているのかを追跡するのを手伝ってくれる人はいますか?

4

2 に答える 2

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

この述語への引数を差分リストとして見ると、最初の節は、リスト from Ato A(つまり、空のリスト) は回文であると述べています。

2 番目の節は、その 1 つの要素が何であれ、1 つの要素のリストは回文であると述べています。

パニックにならない！  差分リストは、明示的な終了「ポインター」を持つ単なるリストです

通常のリスト、たとえば[1,2,3]は、その開始と終了の違いです。通常のリストの末尾は常に空のリストです[]。つまり、リストの場合、この述語を次のように呼び出す必要[1,2,3]があります。つまり、差分リストが回文であるかどうかを確認します。palindrome( [1,2,3], [])[1,2,3] - []

運用上の観点からは、差分リストは、明示的に維持された「エンド ポインター」を含む (場合によっては制限のない) リストに他なりません。たとえば、A - ZwhereA = [1,2,3|Z]とZ = []. 確かに、[1,2,3|[]]と同じ[1,2,3]です。しかし、Zまだインスタンス化されていない場合、リストAはまだオープンエンドです-その「エンドポインター」Zは何にでもインスタンス化できます（ただし、もちろん、バックトラッキングなしで1回だけです）。

Z後で無限リストにインスタンス化する場合、たとえば 、Z = [4|W]新しく拡張された差分リストを取得します。A - WここでA = [1,2,3,4|W]. 古いものは になります。つまり、まだ制限のないリストのA - Z = [1,2,3,4|W] - [4|W]プレフィックスを表しています。などで閉じられると、logvar のすべてのペアは、対応する差分リスト (つまり、...) を表しますが、もはや制限のないものではないため、これ以上拡張することはできません。[1,2,3][1,2,3,4 ...]W = [5]A - ZA - WA

ファンクターを使用する代わりに-、差分リスト定義の両方の部分を述語への個別の引数として使用するのが通例です。それらをペアの 2 つの部分であるかのように常に使用/扱う場合、概念的にはペアを形成します。それは同じことです。

つづく。3 番目の節は、回文であるため[C|A]-Dには、回文であるA-B必要があり、 である必要があると述べていBます[C|D]。A, D, BはリストでCあり、リストの要素です。これは紛らわしいかもしれません。V代わりに使いましょう。また、 and の代わりに and を使用ZしYてD、Bリストの「終わり」を思い出させてください。

palindrome([V|A], Z):- palindrome(A, Y), Y=[V|Z].

V ................. V ----
  ^                 ^ ^
  |                 | |
  |                 | Z
  A                 Y = [V|Z]

実際、コアが回文の場合、その周りに......を 2 つ置くと、別の回文になります。V

于 2013-12-07T12:41:08.523 に答える
1

以下は、これまでの議論の最良の部分を要約したものであり、1 つの小さいながらも重要な簡略化を追加したものです。

最初に、元の質問は目前の問題のコンテキストで理解する必要があります。これは、リストが回文であるかどうか、またはより一般的には回文を生成するかどうかをチェックする Prolog 述語を定義することとして定式化できます。差分リストを使用して実装を検討したいので、次のように開始できます。

% List is a palindrome if List - [] is a palindrome:
palindrome( List ) :- palindrome(List, []).

(他の場所で説明したように、リスト List が Front と Back の 2 つのリストを連結したものである場合、Front は List と Back の違いと見なすことができます。つまり、Front は (List - Back) と同等と見なすことができます。 .)

回文/2 を定義するには、2 つの「基本ケース」、空のリストとシングルトンから始めます。

% The empty list (L-L) is a palindrome:
palindrome(L, L).

% A singleton list, ([X|L] - L), is a palindrome:
palindrome([X|L], L).

ここで、一般的なケースに移りましょう。

複数の要素を持つリストが回文になる場合、次のようになります: E ... E

ここで ... は (おそらく空の) 回文です。

テール、テール、私たちのリストは次のようになります: E ... E テール

この通常のリストを [E|Rest] と書くと、(Rest - [E|Tail]) が回文である場合、元のリスト ( [E|Rest] - Tail ) が回文であることがわかります。述語回文/2 :

palindrome( [E|Xs], Tail ) :- palindrome(Xs, [E|Tail]).

これが元の定式化と同等であることは容易にわかります。

それでおしまい！たとえば、回文のテンプレートを生成できます。

?- palindrome( X ).
X = [] ;
X = [_G1247] ;
X = [_G1247, _G1247] ;
X = [_G1247, _G1253, _G1247] ;
X = [_G1247, _G1253, _G1253, _G1247] 
....
于 2014-03-01T01:30:40.850 に答える