6

>>=無料のモナドを使用して、Prolog のようなAND にマップされ、OR にマップされたAND/OR 決定木を構築するための EDSL を構築しようとしていますmplus。のようなものを記述できるようにしたいのA AND (B OR C) AND (D OR E)ですが、分配性によってこれが に変わることは望ましくありません(A AND B AND D) OR (A AND B AND E) OR (A AND C AND D) OR (A AND C AND E)。最終的には、AND/OR ノードを制約ソルバーで具体化された制約に変換したいと考えています。ソルバーに処理させたい選択肢の数が爆発的に増えることはありません。

ではControl.MonadPlus.Free、の各モナドの下にあるそれぞれの葉に適用されるPlus ms >>= f原因。置換する葉ごとに異なる値が生成される可能性があるため、これが必要です。fPuremsfPure

ただし、 ではPlus ms >> g、gの葉の影響を受けないmsため、 に配布するPlus必要はないようです。

試行錯誤の結果、Control.MonadPlus.Freeモナドを新しいThenコンストラクタで拡張できることがわかりました。

data Free f a = Pure a
              | Free (f (Free f a))
              | Then [Free f ()] (Free f a)
              | Plus [Free f a]

ここで、新しいThenコンストラクタは、値を無視するモナドのシーケンスを保持し、その後に実際の値を生成する最後のモナドが続きます。新しいMonadインスタンスは次のようになります。

instance Functor f => Monad (Free f) where
    return = Pure

    Pure a >>= f = f a
    Free fa >>= f = Free $ fmap (>>= f) fa
    Then ms m >>= f = Then ms $ m >>= f
    Plus ms >>= f = Plus $ map (>>= f) ms

    Pure a >> mb = mb
    Then ms ma >> mb = Then (ms ++ [ma >>= (const $ return ())]) mb
    ma >> mb = Then [] ma >> mb

演算子は>>、既存の葉を で置き換えることによって「キャップ」Pure aしPure ()、キャップされたモナドをリストに追加し、値モナドを新しいものに置き換えます。新しいモナドを で追加することの非効率性は認識していますが、新しいモナドをチェーンの最後に でステッチ++するのと同じくらい悪いと思います (そして、継続を使用して全体を書き換えることができます)。>>=fmap

これは合理的なことのように思えますか? これはモナドの法則に違反していますか(これは問題ですか?)、または既存のを使用するより良い方法はありControl.Monad.Freeますか?

4

1 に答える 1

2

フリーモナドの別の解釈である、私の運用パッケージを見たいと思うかもしれません。

特に、BreadthFirstParsing.hsの例を見てください。自動的に分散しないようmplusに動作するのが特徴です。これにより、幅優先の方法でパーサー コンビネーターを実装できます。>>=

に翻訳するControl.Monad.Freeと、ポイントは、ファンクターを使用する場合

data F b = MZero | MPlus b b

その後、Free Fに自動的に配布さ>>=れmplusます。ファンクターを使用する必要があります

data F b = MZero | forall a. MPlus (Free f a) (Free f a) (a -> b)

MPlus代わりに、自動的に配布しないためのセマンティクスを実装したい場合>>=。(これが、私が無料のライブラリよりも運用ライブラリを好む主な理由です。)

于 2013-12-04T13:34:08.210 に答える