1

次のコードがあります。このコードはリストで機能しますが、これらのリストはセットを表すため、[1,1,2,2,3,3]と[1,2,3]は同等である必要があることに注意してください。

%contains(L1, L2), returns true if L1 contains L2
contains(_, []).
contains(L1, [Head|Tail]) :- member(Head, L1), contains(L1, Tail).
%equals(L1, L2), returns true if L1 is equal to L2
equals([X|L1],[X|L2]) :- equals(L1, L2).
equals(L1, L2) :- contains(L1, L2), contains(L2, L1).

equals（[1,2,3]、[1,2,1,3]）はtrueを返す必要があるという考え方です。ただし、上記の定義に基づいて、私が予想することは次のとおりです。

  1. equals（[1,2,3]、[1,2,1,3]）は最初のルールに一致し、equals（[2,3]、[2,1,3]]）を呼び出します。
  2. equals（[2,3]、[2,1,3]]）は2番目のルールに一致し、contains（[2,3]、[2,1,3]）、contains（[2,1,3]、 [2,3]）。
  3. contains（[2,3]、[2,1,3]）は失敗し、equalsはNoを返します。

それでも、それはまだ機能します。そして、それを混乱させる他の試みもそうです。誰かが私にそれを説明してもらえますか？

（Prologの実装：SWI-Prologバージョン2.7.12）

4

2 に答える 2

3

Prologは「バックトラッキング」と呼ばれる手法を使用しています。

最初のステップであるステップ1を見てください。

Prologにはここで使用できる2つのルールがあります。説明で選択したルールを使用すると、常に失敗します。しかし、失敗すると、Prologはバックトラックして代替ルールを試します。

equals（[1,2,3]、[1,2,1,3]）：-contains（[1,2,3]、[1,2,1,3]）、contains（[1,2、 1,3]、[1,2,3]）

誤った答えを見つけた後に繰り返しバックトラックすることによって、最終的にPrologは真である解決策を見つけ、したがって、答えが真であることがわかります。

真の答えを見つけることなく、ルールを適用するためのあらゆる可能な方法を試した場合、答えは偽でなければなりません。

これはPrologの非常に基本的な部分です。あなたがそれを理解せずにここまで到達したことに私は驚いています。

于 2009-06-29T22:23:52.373 に答える
2

あなたのコードは非常に奇妙ですが、テスト目的でトレース述語を使用することをお勧めします。次に例を示します。

4 ?- trace([equals,contains]).
%         equals/2: [call, redo, exit, fail]
%         contains/2: [call, redo, exit, fail]
true.

[debug] 5 ?- equals([1,2,3],[1,2,1,3]).
 T Call: (7) equals([1, 2, 3], [1, 2, 1, 3])
 T Call: (8) equals([2, 3], [2, 1, 3])
 T Call: (9) equals([3], [1, 3])
 T Call: (10) contains([3], [1, 3])
 T Fail: (10) contains([3], [1, 3])
 T Fail: (9) equals([3], [1, 3])
 T Redo: (8) equals([2, 3], [2, 1, 3])
 T Call: (9) contains([2, 3], [2, 1, 3])
 T Call: (10) contains([2, 3], [1, 3])
 T Fail: (10) contains([2, 3], [1, 3])
 T Fail: (9) contains([2, 3], [2, 1, 3])
 T Fail: (8) equals([2, 3], [2, 1, 3])
 T Redo: (7) equals([1, 2, 3], [1, 2, 1, 3])
 T Call: (8) contains([1, 2, 3], [1, 2, 1, 3])
 T Call: (9) contains([1, 2, 3], [2, 1, 3])
 T Call: (10) contains([1, 2, 3], [1, 3])
 T Call: (11) contains([1, 2, 3], [3])
 T Call: (12) contains([1, 2, 3], [])
 T Exit: (12) contains([1, 2, 3], [])
 T Exit: (11) contains([1, 2, 3], [3])
 T Exit: (10) contains([1, 2, 3], [1, 3])
 T Exit: (9) contains([1, 2, 3], [2, 1, 3])
 T Exit: (8) contains([1, 2, 3], [1, 2, 1, 3])
 T Call: (8) contains([1, 2, 1, 3], [1, 2, 3])
 T Call: (9) contains([1, 2, 1, 3], [2, 3])
 T Call: (10) contains([1, 2, 1, 3], [3])
 T Call: (11) contains([1, 2, 1, 3], [])
 T Exit: (11) contains([1, 2, 1, 3], [])
 T Exit: (10) contains([1, 2, 1, 3], [3])
 T Exit: (9) contains([1, 2, 1, 3], [2, 3])
 T Exit: (8) contains([1, 2, 1, 3], [1, 2, 3])
 T Exit: (7) equals([1, 2, 3], [1, 2, 1, 3])
true
于 2009-06-30T20:58:50.883 に答える