6

このページhttp://www.ic.unicamp.br/~meidanis/courses/mc336/2009s2/prolog/problemas/の演習 09 では、繰り返される要素をサブリストにパックする述語を作成するよう求められます。

簡単な解決策は簡単です

pack([], []).
pack([H|T], [I|U]) :-
    split(H, T, I, P),
    pack(P, U).

ここで、分割はsplit(Head, Tail, HeadGroup, Rest)次のように定義されます

split(A, [], [A], []).
split(A, [B|T], [A], [B|T]) :- A \= B.
split(A, [A|T], [A|U], B) :- split(A, T, U, B).

これは問題なく動作し、上記の Web ページで提供されているサンプル ソリューションとほぼ一致しています。

このソリューションが失敗するのは、のようなクエリですpack(X, [[a], [b, b]]).。2 つの解セット間の対応は全単射 (すべてAのpack(A, B)には 1 つしかないBため) であるため、より良い解が存在するはずです。

それを解決する1つの方法は、評価の順序を変更することです。これにより、プロローグが次のような引数のタイプに応じて非無限分岐を選択できるようになります

pack([], []).
pack(A, B) :-
  ( var(A) ->
    A = [H|T],
    B = [I|U],
    pack(P, U),
    split(H, T, I, P)
  ; A = [H|T],                                                                                                                                                                                                                                
    B = [I|U],
    split(H, T, I, P),
    pack(P, U)
  ).

これに関して2つの質問。

まず、これは信じられないほど醜いので、引数の型に応じてルールの順序を選択するより良い方法はありますか?

第二に、おそらくもっと複雑な質問ですが、 を使わずvar(A)にソリューションを書き直す方法はありますか? そうでない場合、その理由は?

4

1 に答える 1

4

宣言的な観点からは、非単調構造は や のようvar/1に (\=)/2非常に問題があります。

なんで？見てみな：

?- var(A), A=a.
A = a.

?- A=a, var(A).
false.

したがって、これは、論理プログラムについて実際に推論するときに依存するコアプロパティの1つである、論理積の可換性を破ります。

2 つの用語が異なることを表すと思われるについて(\=)/2はどうですか? 見てみな：

?- X \= Y.
 false.

2 つの異なる用語は存在しません。控えめに言っても、私には少し奇妙に思えますが、どうやら述語は実際には何か別の意味を持っているようです。

幸いなことに、あなたの場合、解決策は非常に簡単です。純粋な制約dif/2を使用して、2 つの用語が異なることを示します。詳細については、 を参照してください。コードを 1 行変更するだけで、ソリューションをより一般的なものにすることができます。それ以外の：

split(A, [B|T], [A], [B|T]) :- A \= B.

単に使用しますdif/2：

split(A, [B|T], [A], [B|T]) :- dif(A, B) .

この変更により、例は期待どおりに完全に機能します。

?- pack(X, [[a], [b, b]]).
X = [a, b, b] ;
false.

既存の Prolog 文献はかなり時代遅れであり、そのようなソリューションのセットのほとんどはdif/2、ほとんどの Prolog システムでは利用できなかった時代のものであり、確かに無料のシステムでは利用できなかったことに注意してください。

于 2016-07-22T13:45:42.783 に答える