0

min_of_list のこの実装 (SO 3965054 から) がプロローグで機能する理由を誰かが明確に説明できますか?

% via: http://stackoverflow.com/questions/3965054/prolog-find-minimum-in-a-list
min_of_list_1( [H], H).
min_of_list_1([H,K|T],M) :- H =< K, min_of_list_1([H|T],M). 
min_of_list_1([H,K|T],M) :- H > K,  min_of_list_1([K|T],M).

この実装では、誤った出力が生成されます。

min_of_list_2( [H], H).
min_of_list_2( [H| T], X) :- compare(<, X, H), min_of_list_2(T, X).
min_of_list_2( [H| T], H) :- compare(>, X, H), min_of_list_2(T, X).
min_of_list_2( [H| T], H) :- compare(=, X, H), min_of_list_2(T, H).

エピローグ。これは機能します。

min_of_list_3( [H], H).
min_of_list_3( [H| T], X) :- min_of_list_3(T, X), compare(<, X, H).
min_of_list_3( [H| T], H) :- min_of_list_3(T, X), compare(>, X, H).
min_of_list_3( [H| T], H) :- min_of_list_3(T, X), compare(=, X, H).

?

私が得た動作は、min_of_list_2 がリストの最後の要素を返すことです。ありがとう。

4

2 に答える 2

2

min_of_list_2/2 の最初の節はOKです。単一の要素を持つリストの最小値はその要素であると言っています。2 番目の節はあまり問題ありません。X がリスト T の最小値であり、X が H より小さい場合、X もリスト [H|T] の最小値であり、これはcompare/3 が真のリレーションのように動作する場合は意図したとおりに動作しますが、残念ながらそうではありません:

?- compare(<, a, b).
true.

しかし、より一般的なクエリは、解決策がないかのように失敗します (少なくとも 1 つあることはわかっていますが!)。

?- compare(<, a, X).
false.

min_of_list_2/2 の一般的な使用法 (たとえば、3 番目の句での使用を含む) の 1 つでは、2 番目の引数がインスタンス化されないままになるため、この問題が発生します。min_of_list_2/2 のそれぞれの再帰呼び出しの後に compare/3 のすべての呼び出しを配置すると、コードは期待どおりに機能します。結果として、投稿した他のプログラムとは対照的に、述語は末尾再帰ではなくなりました。最後の句の compare/3 呼び出しは削除する必要があります (この場合の X は何ですか?)。これは常に失敗します。

于 2012-05-07T21:52:22.713 に答える
1

最初のものは、リストの最初の 2 つの要素を比較し、要素が 1 つだけになるまで最小値をリストに入れます。

2番目のものは...リストの先頭を取り、Xと比較します。Xは最初の呼び出しでインスタンス化されていないため、compare(<、X、_any_number)はtrueになります。X はインスタンス化されないため、返されるリスト内の要素が 1 つだけになるまで同じことが繰り返されます* (最後の要素)。

'* 返される場所 = 第 2 引数と統一。

于 2012-05-07T21:39:30.583 に答える