4

Prologでリスト追加実装を行う-

append([],X,X). 
append([H|T1],X,[H|T2]) :- 
    append(T1,X,T2).

それは与える -

append([a,b,c],[d,e,f],X).

出力 -

X = [a,b,c,d,e,f].

T2どのように機能するのだろうか、関数呼び出しを追跡しようとしましたが、リストの末尾でXあるが、append([a,b,c],[d,e,f],X)呼び出しでまだ定義されていない末尾として持つことができる方法がわかりませんでした。この再帰を解決してくれませんか?

4

1 に答える 1

2

それは、Prolog で Unification がどのように機能するかにかかっています。基本的：

  • 原子は同一である場合にのみ結合します
  • 変数は何でも統合し、
  • 各コンポーネントが統合できる場合、化合物は統合されます

したがって、次のように呼びます:append([a, b, c], [d, e, f], Y)これが最初の目標です。見やすくするために、変数名を X から Y に変更したことに注意してください。

これは、事実または規則で統一する必要があります。append([], X, X) で統一するかどうか見てみましょう。

      (1)  append([a, b, c], [d, e, f], Y)
      (2)  append([], X, X)

(1) と (2) はどちらも同じ functor (append) を持っているので良いですし、両方とも 3 つの引数を持っているのでそれも良いです。しかし、対応する各引数を統一するには、統一する必要があります。したがって、(1) の最初のリスト [a, b, c] は (2) の空のリストと統合しようとしますが、(1) のリストは空のリストではないため、統合できません。だから統一は失敗する。

次に、append([H|T1],X,[H|T2]) で統合を試みることができます。

      (1)   append([a, b, c], [d, e, f], Y)
      (2)   append([H|T1],X,[H|T2])

今回は、(1) のリスト [a, b, c] を (2) のリスト [H|T1] と統合しようとします。これを可能にするために、変数 H はアトム a とバインドでき (H -> a)、リスト T1 は (1) のリストの末尾とバインドできます (T1 -> [b, c])。したがって、最初の引数が機能するので、次のようになります。

      (1)   append([a, b, c], [d, e, f], Y)
      (2)'   append([a, b, c],X,[a|T2])

X は変数であり、何にでもバインドされるため、2 番目の引数も単一化されます。X -> [d, e, f] したがって、次のようになります。

      (1)   append([a, b, c], [d, e, f], Y)
      (2)''   append([a, b, c],[d, e, f],[a|T2])

そして最後に、Y -> [a|T2] のため、最後の引数が統一されます。ルールのヘッドと統合したので、ルールの本体を作成する必要があります。これで、最終的append([b, c], [d, e, f], T2)にゴールになります。

再び最初の事実から始めて、このゴールがバインドされる節を探します。上記の同じ説明により、最初の節とは統一されませんが、束縛を持つ 2 番目の節とは統一されます: H -> b, T1 -> [c], X -> [d, e, f] および T2 -> [ b|T2']。

目標はappend([c], [d, e, f], T2')です。ここでも、最初の節とは統一されず、次のバインディングで 2 番目の節と統一されます: H -> c, T1 -> [], X -> [d, e, f], T2' -> [c|T2'' ]。

現在の目標は、append([], [d, e, f], T2'') です。

これを節 1 で統一しようとするとどうなるか見てみましょう。

     (1)   append([], [d, e, f], T2'')
     (2)   append([],X,X)

2 つの空のリストは、X -> [d, e, f] を統合し、T2''->X から T2'' -> [d, e, f] を統合します。ここで難しいのは、これまでの再帰呼び出しを追跡し、再帰に沿って戻って最終結果を確認することです。T2' -> [c | c] を思い出してください。T2''] したがって、T2' は実際には [c, d, e, f] です。T2 -> [b|を思い出してください。T2'] なので、T2 は実際には [b, c, d, e, f] です。

そして最後に Y -> [a|T2] なので、Y は [a, b, c, d, e, f] です。Y は外部変数であるため、元の目標が満たされていることが表示されます。

于 2013-01-16T17:54:03.257 に答える