0

私はこのコードに出くわしました：

connectRow(_,_,0).
connectRow([spot(_,R,_,_)|Spots],R,K) :- K1 is K-1, connectRow(Spots,R,K1).

/*c*/
connectRows([]).
connectRows(Spots) :- 
   connectRow(Spots,_,9),
   skip(Spots,9,Spots1), 
   connectRows(Spots1).

connectRow（Spots、_、9）のワイルドカードはどのように機能しますか？チェックする値をどのように認識し、すべての可能な値をチェックしたことをどのように認識しますか？

編集：これが機能する理由は理解できたと思いますが、誰かがこれを確認してくれるといいのですが：connectRowをワイルドカードで「呼び出す」と、ワイルドカードがconnectRow述語の「R」と一致します。これでいいの？

4

1 に答える 1

2

は_他の変数と同じですが、表示される各変数は異なる変数として扱われ、Prolog はそれが何と統合されているかを表示しません。特別な動作はありません。動作について混乱する場合は、まったく新しい変数を発明し、そこに置いて、それが何をするかを確認してください。

Prolog が変数をどのように扱うかについて話しましょう。これは、役に立たない先入観を持っている場合にそれを弱体化させるための実験です。

?- length([2,17,4], X)
X = 3.

多くの Prolog はこのように見え、戻り値のように機能する指定された "out" 変数とパラメーターのように機能する指定された "in" 変数があると考えるのは簡単です。結局：

?- length([2,17,4], 3).
true.

?- length([2,17,4], 5).
false.

ここで、興味深いことが起こっていることがわかり始めます。この場合、Prolog が何らかの方法で入力変数と出力変数を追跡し、「チェック」しているという誤った直感があります。統一はそれよりも一般的であるため、それは起こっていることではありません。観察：

?- length(X, 3).
X = [_G2184, _G2187, _G2190].

ここで、従来のパラメーター/戻り値を頭に入れました。Prolog は、X が 3 項目の長さのリストであることを認識していますが、項目が実際に何であるかは認識していません。信じられないかもしれませんが、この手法は、必要な変数の数がわかっているが個別に名前を付ける必要がない場合に、変数を生成するためによく使用されます。

?- length(X, Y).
X = [],
Y = 0 ;

X = [_G2196],
Y = 1 ;

X = [_G2196, _G2199],
Y = 2 ;

X = [_G2196, _G2199, _G2202],
Y = 3

長さの定義は非常に一般的であり、Prolog はそれを使用して長さとともにリストを生成できます。この種の動作は、Prolog が「生成とテスト」ソリューションを得意とする理由の一部です。問題を論理的に定義すると、Prolog は論理的に適切な値を生成してテストできるはずです。

このバリエーションはすべて、非常に単純な長さの定義から生まれます。

length([], 0).
length([_|Rest], N1) :-
  length(Rest, N0), 
  succ(N0, N1).

重要なのは、これを長さを計算する手順のように読むのではなく、リストと数値の間の論理的な関係として見ることです。定義は帰納的で、空のリストを 0 に関連付け、いくつかの項目を含むリストを 1 + リストの残りの長さに関連付けます。この作業を行うエンジンは、統合と呼ばれます。

最初のケース ではlength([2,17,4], X)、値 [17,4] は Rest と統合され、N0 は 2 と統合され、N1 は 3 と統合されます。プロセスは再帰的です。最後のケースでは、X は [] で統一され、Y は 0 で統一されます。これは、次のケースに自然につながります。ここでは、いくつかのアイテムがあり、Y は 1 であり、リスト内のアイテムを表す変数には何も含まれていません。特に、その変数の値は決して使用されないため、統一することは問題ではありません。

あなたの問題を見ると、同じ種類の再帰構造が見られます。述語は非常に複雑なので、分解してみましょう。

connectRow(_, _, 0).

これはconnectRow(X, Y, 0)、X と Y に関係なく、真です。これが基本ケースです。

connectRow([spot(_, R, _, _)|Spots], R, K) :-

このルールは、最初のスポットの 2 番目の値 (R) が 2 番目のパラメーターと一致すると仮定して、特定の構造のスポットのリストに一致します。

K1 is K-1, connectRow(Spots, R, K1).

この句の本体は、基本的に、3 番目のパラメーターである K をデクリメントすることで繰り返されます。

これで、基本的に[spot(_, R, _, _), spot(_, R, _, _), ... spot(_, R, _, _)]length = K のようなリストが生成され、 の他の 3 つの位置に特定の値がないことは明らかですspot。実際、それをテストすると、次のようになります。

?- connectRow(X, Y, 0).
true ;
(infinite loop)^CAction (h for help) ? abort
% Execution Aborted

?- connectRow(X, Y, 2).
X = [spot(_G906, Y, _G908, _G909), spot(_G914, Y, _G916, _G917)|_G912] ;
(infinite loop)^CAction (h for help) ? abort

したがって、ここにはいくつかのバグがあるようです。これらがすべての話だと確信していたら、私はこう言うだろう：

  • 基本ケースでは、何かに一致するのではなく、空のリストを使用する必要があります
  • 帰納的なケースでは、K > 0 と規定する必要があります。
  • clpfdすべての可能性を生成できるようにしたい場合は、使用する必要があります

変更を加えると、動作がわずかに異なります。

:- use_module(library(clpfd)).

connectRow([], _, 0).
connectRow([spot(_, R, _, _)|Spots], R, K) :- 
  K #> 0, K1 #= K-1, connectRow(Spots, R, K1).

?- connectRow(X, Y, 0).
X = [] ;
false.

?- connectRow(X, Y, 1).
X = [spot(_G906, Y, _G908, _G909)] ;
false.

?- connectRow(X, Y, Z).
X = [],
Z = 0 ;

X = [spot(_G918, Y, _G920, _G921)],
Z = 1 ;

X = [spot(_G918, Y, _G920, _G921), spot(_G1218, Y, _G1220, _G1221)],
Z = 2

結果では、構造内に Y が立ってspotいますが、 などの他の位置に奇妙に見える自動的に生成された変数があることに気付くでしょう_G918。たまたま、_Y の代わりに使用して、同様の効果を確認できます。

?- connectRow(X, _, Z).
X = [],
Z = 0 ;

X = [spot(_G1269, _G1184, _G1271, _G1272)],
Z = 1 ;

X = [spot(_G1269, _G1184, _G1271, _G1272), spot(_G1561, _G1184, _G1563, _G1564)],
Z = 2

これらの奇妙に見える変数はすべて、 を使用したために存在します_。Prolog は の 2 番目のパラメーターをの 2 番目の位置にspot統合する必要があると言われたため、すべての構造体の 2 番目の位置にまったく同じ生成された変数があることに注意してください。R は connectRow への次の呼び出しに再帰的に「渡される」ため、どこでも当てはまります。connectRowspot

うまくいけば、これはあなたの例で何が起こっているのかを説明するのに役立ちます_.Prologの統合も一般的です.

編集：Rで何かを統一する

以下の質問に答えるには、R を値と直接統合するか、変数にバインドして変数を使用することで統合できます。たとえば、直接バインドできます。

?- connectRow(X, 'Hello, world!', 2).
X = [spot(_G275, 'Hello, world!', _G277, _G278), spot(_G289, 'Hello, world!', _G291, _G292)]

それをバインドして、後で割り当てることもできます。

?- connectRow(X, R, 2), R='Neato'.
X = [spot(_G21, 'Neato', _G23, _G24), spot(_G29, 'Neato', _G31, _G32)],
R = 'Neato'

と言うのは特別なことではありませんR=<foo>。式の両側を統一しますが、両側を変数ではなく式にすることができます。

?- V = [2,3], [X,Y,Z] = [1|V].
V = [2, 3],
X = 1,
Y = 2,
Z = 3.

したがって、別の述語でも同様に R を使用できます。

?- connectRow(X, R, 2), append([1,2], [3,4], R).
X = [spot(_G33, [1, 2, 3, 4], _G35, _G36), spot(_G41, [1, 2, 3, 4], _G43, _G44)],
R = [1, 2, 3, 4] ;

これにより、後戻りして他のソリューションを生成する機会が生じることに注意してください。例えば：

?- connectRow(X, R, 2), length(R, _).
X = [spot(_G22, [], _G24, _G25), spot(_G30, [], _G32, _G33)],
R = [] ;

X = [spot(_G22, [_G35], _G24, _G25), spot(_G30, [_G35], _G32, _G33)],
R = [_G35] ;

X = [spot(_G22, [_G35, _G38], _G24, _G25), spot(_G30, [_G35, _G38], _G32, _G33)],
R = [_G35, _G38] ;

お役に立てれば！

于 2013-01-23T22:49:35.427 に答える