2

以下のコードを理解するのに苦労しています。
次の入力がある場合、誰かが何が起こっているのかを段階的に説明できますか: 

append([1,2,3], Lst).

実際には、結果として 1 と 2 がどのようにリスト Lst に追加されるのかわかりません。

append([_], []).    
append([H|T], [H|N]) :- append(T,N).
4

1 に答える 1

6

Prolog は初めてのようです。もしそうなら、ようこそ！これを分析してみましょう。

この残念な名前の関数には 2 つの節があります。Prolog は、どの句が適用されるかを確認するために句を調べます。一致するものを見つけると、それを実行しようとします。実行中にどこかでエラーが発生した場合は、バックアップして次のオプションを試します。これらの選択ポイントが正確にどこにあるかは、プログラムによって異なります。このプログラムでは、使用するルールを決定するのは句レベルのみです。

最初の規則の 1 つの見方は、「1 つの要素を持つリストは、その要素が何であるかに関係なく、空のリストに関連している」ということです。を見ると、append([_], [])と があれば成立します。なぜなら、は 1 項目のリストであり、 は空リストだからです。この規則は、インスタンス化に関係なく機能するため、優れた Prolog スタイルです。X = [foo]Y = [][foo][]

2 番目の節も非常に単純です。左の引数と右の引数が両方とも同じ項目で始まり、リストの残りの部分もこの同じ述語によって関連付けられている場合、それらは関連付けられていると言います。言い換えれば、2 つのリストがXあり、Yそれappend(X, Y)が true である場合、thenappend([H|X], [H|Y])も true です。によって暗示される場合を除いて、H が何であるかは問題ではなく、X と Y が何であるかは問題ではありませんappend/2。

論理的に考えて、1 つの項目のリストが空のリストに関連し、任意のリストが同じ項目で始まるリストに関連し、それ以外は同じであることがわかっている場合、そのように関連できる唯一の種類のリストは次のとおりです。左のリストの最後にはもう 1 つの項目があり、右のリストにはありません。したがって、[1,2,3,4] は [1,2,3] に関連していますが、[1,2,3,foo] と [1,2,3] も関連しています。

手続き的に、この述語がこの一連の引数で処理されるときに何が起こるかを見てみましょう。

append([1,2,3], X).

最初のルールは [1,2,3] では一致しません。したがって、2 番目のルールを確認する必要があります。

append([1|[2,3]], [1|X]) :- append([2,3], X).

繰り返すことができます：

append([2|[3]], [2|Y]) :- append([3], Y).

これで、最初のルールが一致します:

append([3], []).

すべてをまとめると、次のようになります。

append([1,2,3], [1|X]) implies
  append([2,3], X=[2|Y]) implies
    append([3], Y=[])
  so Y = []
so X = [2]
so the right side is [1,2].

Prolog トレースでは、基本的に同じ情報が表示されます。

?- trace, append([1,2,3], X).
   Call: (7) append([1, 2, 3], _G1633) ? creep
   Call: (8) append([2, 3], _G1752) ? creep
   Call: (9) append([3], _G1755) ? creep
   Exit: (9) append([3], []) ? creep
   Exit: (8) append([2, 3], [2]) ? creep
   Exit: (7) append([1, 2, 3], [1, 2]) ? creep

この Prolog コードを混乱させているのは、Prolog に何かを行う方法を伝えたように見えないことです。確かにそうではありませんが、何が真であるかを論理的に指定することで、Prolog はそれを自分で判断することができます。これはかなり賢いコードです。これが Haskell の場合init、最後の項目を除くすべてのリストを返す組み込み関数 について話していることになります。

お役に立てれば！

于 2013-02-21T05:55:35.737 に答える