5

Prolog では、テンプレート (変数を含む構造体) を提供し、それに対する一連の制約を満たすことで問題を解決することがよくあります。些細な例は次のとおりです。

go(T) :-
    T = [_, _, _],
    member(cat, T),
    member(dog, T),
    member(mouse, T).

実際には、一連の制約は修正されるのではなく、別の方法で生成されます。各制約を順に満たすために、再帰的な述語を記述する必要があります。

go(T) :-
    T = [_, _, _],
    findall(A, animal(A), As),
    % satisy member(A, T) for each A in As
    fill_in_animals(T, As)

fill_in_animals(T, []).
fill_in_animals(T, [A|Rest]) :-
    member(A, T),
    fill_in_animals(T, Rest).

私の質問はリスト関連の制約に関するものではなく、制約へのパラメーターでさえ、上記で使用されている比較的単純なヘルパー述語に渡されるリストとして常に簡単に生成できるとは限らないことに注意してください。実際には、ヘルパーは、私が毎回書くかなり不格好な述語であることがわかりました。

  1. テンプレート、制約に使用されるいくつかのパラメーター (したがって、テンプレートの変数を有用な値にバインドするため)、およびそれがどの制約に従っているかを示すための変数を受け入れます。
  2. この反復で満たす制約を生成し、それをテンプレートに適用します。
  3. 残りの制約を満たすことができるように、再帰的に自分自身を呼び出します。

私が探しているのはfindall、一連の目標を次々と満たす、などの行に沿った述語です。何かのようなもの：

% satisfyall(:Goal)
% backtracks on Goal but keeps all bindings from each fully satisfied goal.

satisfyall((animal(A), member(A, T)))

私が探している答えは、この形である必要はありません。実際には、目標をバックトラックすることと、そこから生じるバインディングの各セットを維持することの間には矛盾があるかもしれません。

何が役立つかが合理的に明確になるように、私の問題を説明できたことを願っています。（そうでない場合はお知らせください。）長々とした質問を事前にお詫びします！

更新（2年後）

今日の後半に試して、質問を更新します。

を試したのと同じ日に質問を更新するとは決して言わなかったことに注意してください。;-)

@CapelliC は私を正しい方向に導いてくれました。かなりうまく機能しているように見えるパターンを見つけました。

?- Gs = [member(red),member(blue)], T = [_,_], foreach(member(G, Gs), call(G, T)).
T = [red, blue] ;
T = [blue, red] ;
4

2 に答える 2

3

satisfyall/1質問に記載されている状況は、あなたが与えた述語の署名とは少し異なります。fill_in_animalsこの例には、少なくとも から流出する変数に関しては、後戻りはありませんgo/1。サブゴールの達成には「わずかな後戻り」があるかもしれませんが、バインディングをそのまま残しながら、全体的なゴールが失敗することはありません。

陳腐でおそらく役に立たない解決策は、 を使用することmaplist/2です。たとえば、あなたの例はこの方法で簡単に実現できます:

?- length(L, 3), maplist(animal, L).
L = [cat, cat, cat] ;
L = [cat, cat, dog] ;
L = [cat, cat, mouse] ;
L = [cat, dog, cat] ;
...
L = [mouse, mouse, dog] ;
L = [mouse, mouse, mouse].

述語を 1 つ追加するだけで、実体化されたデータベースを使用できます。

% just flips the arguments of member/2
memberof(L, A) :- member(A, L).

次にfindall/3、作業を行うために使用できます。

?- findall(A, animal(A), Animals), 
   length(L, 3), 
   maplist(memberof(Animals), L).

Animals = [cat, dog, mouse],
L = [cat, cat, cat] ;
Animals = [cat, dog, mouse],
L = [cat, cat, dog] ;
Animals = [cat, dog, mouse],
L = [cat, cat, mouse] ;
...
Animals = [cat, dog, mouse],
L = [mouse, mouse, dog] ;
Animals = [cat, dog, mouse],
L = [mouse, mouse, mouse].

これにより、lambda.pl が役立つ理由が明確になります。ヘルパー述語は必要ありません。単純に次のように記述できます。

?- findall(A, animal(A), Animals), 
   length(L, 3), 
   maplist(\Animal^member(Animal, Animals), L).

(未テスト)

変数のバインドとバインド解除を本当に回避するつもりなら、自分でデバッグの悪夢を作成することになると思いますが、SWI-Prolog には、使用できるグローバル変数機能があります。asserta/retractこのタスクには不十分であるとどこかで読んだことをぼんやりと思い出します。

考えれば考えるほど、satisfyall/1と実質的に異なるの意味のある実装はないように感じますがmaplist/2、私が間違っていることを発見するのを楽しみにしています.

于 2013-06-19T15:11:37.327 に答える
1

バックトラックでは、機能するために行った変更を元に戻す必要があることをご存じでしょう。それが Prolog アルゴリズムの核心であり、Prolog の力の源です。

また、必然的に副作用やループに関係するような、より一般的な計算に関しては、弱点でもあります。

ルールを決定論的なパスに沿って機能させる正しい方法を見つけるのは難しい場合があります。おそらく、それは Prolog が機能するはずの方法ではないからです。

さて、ここで、哲学の暴言を止めて、Prolog の達人が私たちに利用可能にしたものを見てみましょう: SWI-Prolog は、あなたがforeachを見つける場所であるlibrary( aggregate ) を提供します。

?- foreach(animal(X), member(X,L)).
L = [cat, dog, mouse|_G10698] .

このような複雑なビルトインを調べると、実装のアイデアが得られる可能性があります (?- edit(foreach).コンソールから使用してソースを調べます)。

あなたの質問では、それらは絶望的に結合されていますが、それはジェネレーターとゴールを分離していることに注意してください。もちろん、ジェネレーター部分のみをバックトラックできるようにするために必要です。

ところで、doc ページにリストされている小さな例を理解してみてください。dif/2 では非常に複雑ですが、再帰的な述語を一般化できるようにするには、バインディングの動作を把握する必要があります。

HTH

于 2013-06-20T10:12:38.890 に答える