問題タブ [free-monad]

FreeT / ProgramT によって作成されたモナド変換子の mtl のようなメカニズムはありますか?

私の歴史認識は以下の通りです。むかしむかし、モナド変換子が発明されました。その後、人々はモナド変換子を積み重ねるようになり、liftどこにでも挿入するのが煩わしいことに気づきました。その後、ask :: m r何人かの人々がモナドクラスを発明しましmたMonadReader r m。これは、すべてのモナドクラスがすべてのモナドトランスフォーマーを貫通するようにすることで可能になりました。

(Monoid w, MonadState s m) => MonadState s (WriterT w m)
MonadWriter w m => MonadWriter w (StateT s m)

モナド変換子のペアごとにこのようなインスタンス宣言のペアが必要なので、モナド変換子がn 個ある場合、 n ^2 のコストがかかります。しかし、これは大きな問題ではありませんでした。人々はほとんどの場合、定義済みのモナドを使用し、独自のモナドを作成することはめったにないからです。これまでの話は私が理解しており、次の Q&A などで詳しく説明しています。

Monad Transformer でリフトを回避する

次に、私の問題は、新しい Free モナドhttp://hackage.haskell.org/package/freeと Operational モナドhttp://hackage.haskell.org/package/operationalにあります。代数型として言語を定義するだけで、独自の DSL を記述してモナドとして使用できます(Operational はインスタンスdataさえ必要としません)。Functor良いニュースは、モナドとモナド変換子を無料で持てるということです。ではモナドクラスはどうだろうか？悪いニュースは、「独自のモナド変換子を定義することはめったにない」という仮定がもはや成り立たなくなったことです。

この問題を理解しようとして、2 つProgramTの を作成し、それらを互いに貫通させました。

https://github.com/nushio3/practice/blob/master/operational/exe-src/test-05.hs

このoperationalパッケージはモナド クラスをサポートしていないため、別の実装minioperationalを使用して、必要に応じて動作するように変更しました。https://github.com/nushio3/minioperational

それでも、特殊なインスタンス宣言が必要でした

instance (Monad m, Operational ILang m) => Operational ILang (ProgramT SLang m) where

次の形式の一般的な宣言は、決定不能なインスタンスにつながるためです。

instance (Monad m, Operational f m) => Operational f (ProgramT g m) where

私の質問は、どうすれば Operational モナドが互いに浸透しやすくなるかということです。または、不適切なポーズの操作モナドを貫通したいという私の願いです。

また、侵入の正しい専門用語も知りたいです:)

次のコードは論文 (RO Bjarnason, Stackless Scala With Free Monads) から改作されています。

この論文のタイトルは、提案されたデータ構造の一般的な目的を示しています。それは、一定のスタック空間で再帰処理を可能にし、ユーザーが明確な方法で再帰を表現できるようにすることです。

具体的には、私の目標は、昇順の定数スタック空間での単純なパターン マッチングに基づいて、ペアの不変ツリー (バイナリ ツリー) またはリスト (n-ary-tree) の構造的書き換えを可能にするモナド構造を持つことです。

Free を使用した書き換えはどのように行われますか?

パターンマッチャーのフックはどこにありますか? - パターン マッチャーは、昇順で各サブツリー全体に公開する必要があります。

これは for ブロック内で実行できますか?

【質問を編集しました。】

>>=無料のモナドを使用して、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コンストラクタで拡張できることがわかりました。

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

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

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

Konrad Hinsen、Jim Duey、およびLeonardo Borgesによる Clojure のモナドに関する優れた作業がいくつかあります。

私の質問は、Clojure で Free Monad を実行することは可能ですか?

これは、 Scala に関する記事のHaskell の例です。

これは対応する Scala の例です

次のような自由なモナド DSL が与えられた場合:

そして、のランダムインタプリタFoo:

手動で行うことに頼らずに、 printFoo の各反復に何かを散在させることが可能であるように私には思えます:

これは、オリジナルを「ラッピング」することで何とか可能printFooですか?

動機: バイナリ形式に「コンパイル」する小さな DSL を書いています。バイナリ形式には、各ユーザー コマンドの後にいくつかの追加情報が含まれています。そこにある必要がありますが、私のユースケースではまったく関係ありません。

フリーモナドのFunctorと法則を証明する方法を理解するのに少し苦労しています。Monadまず、私が使用している定義を挙げましょう。

私が物事を正しく理解していれば、方程式の証明には共導仮説へのアピールが必要であり、多かれ少なかれ次の例のようになります。

正しいことをしているかどうか確信が持てないステップを強調しました。

その証明が正しければFree、第 2 法則のコンストラクタの場合の証明は次のようになります。

私は最近、フリーFreeパッケージのモナドについて独学で学んでいますが、問題に遭遇しました。さまざまなライブラリにさまざまなフリーモナドを用意したいと考えています。基本的に、さまざまなコンテキストに対応する DSL を構築したいと考えていますが、それらを組み合わせることもできるようにしたいと考えています。例として：

今、私は両方のBellsAndWhistles機能を組み合わせることができるタイプを作成できるようにしたいと考えています。BellsWhistles

問題はモナドの結合にあるため、私が最初に考えたのはControl.Monad.Trans.Free、迅速かつ簡単な解決策を求めてモジュールを調べることでした。残念ながら、まばらな例があり、私がやりたいことを示すものはありません。また、2 つ以上のフリー モナドをスタックしMonadFreeても機能しないようですm -> f。基本的に、次のようなコードを記述できる機能が必要です。

しかし、別々のモジュールに存在することができ、お互いの実装について知る必要がないような方法Bellsで。Whistlesアイデアは、それぞれが独自の DSL を実装し、必要に応じてそれらを「より大きな」DSL に結合する方法を持つ、さまざまなタスク用のスタンドアロン モジュールを作成できるということです。これを行う簡単な方法はありますか？

play*おまけとして、既に記述されているさまざまな関数を活用して、それらを交換できるようになれば素晴らしいと思います。1 つの無料のインタープリターをデバッグ用に使用し、別のインタープリターを本番環境で使用できるようにしたいのですが、どの DSL を個別にデバッグするかを選択できると明らかに便利です。