問題タブ [monadfix]

更新:最終的な解決策を説明する回答を追加しました(ヒント: 単一のExprデータ型では不十分でした)。

私は小さな式言語のエバリュエーターを書いLetRecていますが、構造に行き詰まっています。

これは言語です：

そして、これはこれまでの評価者です:

これは、評価したいテスト関数です。

編集：

Travis の回答と Luke のコメントに基づいて、エラー モナドに MonadFix インスタンスを使用するようにコードを更新しました。前の例は問題なく動作します。ただし、次の例は正しく機能しません。

これを評価するとき、エバリュエーターはループし、何も起こりません。ここで少し厳しすぎるものを作ったと思いますが、それが何であるかはわかりません。MonadFix 法の 1 つに違反していますか?

System.Random.MWC.Monadから Rand モナドを使用して無限の数のストリームを生成したいと思います。このモナドの MonadFix インスタンス、または次のようなインスタンスがある場合のみ:

次に、次のように書くことができます。

しかし、1つもありません。

私はMonadFix のドキュメントを調べていましたが、このインスタンスを実装する明確な方法がわかりません。

結び目を結ぶことで、洗練されたコードを書きたいと思います（そうでなければ実装する時間を大幅に節約できます）。ざっくりこんな感じで、

理論的には、myinstrを実行xして値を取得する必要があり、これは になりnます。モナドmyinstr内で実行される は状態に入りますが、これはの計算には影響しません。Statenx

DoRecの単純な実装を使用してみましたがmfix、

しかし、物事は凍結します。コードを修正する方法 (または最初から正しく設計するための方法論) はありますか?

私は Haskell でブレインファック インタープリターを書いていますが、プログラムの非常に興味深い説明であると思われるものを思いつきました。

ただし、brainfuck プログラムのテキスト表現をこのデータ型に解析するのは難しいです。角かっこを正しく解析しようとすると問題が発生します。これは、ループ内の最後の部分が再びInstructionループにリンクするように結び目を作る必要があるためです。Control

もう少し予備的な情報。すべての詳細については、github リポジトリでこのバージョンを参照してください。

これが私が試したことです：

'['ケースからケースへ、またはその逆に情報を伝達するために何らかの形で継続を使用できると考えましたが']'、実際に何かを行うのに十分な Cont の把握がありません。上記のようにpushとpop. これはコンパイルして実行しますが、結果はガベージです。

Contこの状況で結び目を適切に結ぶために使用できますか? そうでない場合、実装するにはどの手法を使用する必要がありますtoProgramか?

注 1: 以前、微妙な論理エラーloopControl = branch is0がありました。ブール値が逆になっていたのです。

注2：解決策を考え出すためにMonadFix（jberrymanの提案に従って）使用することができました（ githubリポジトリの現在の状態をState参照してください）。代わりにこれをどのように行うことができるかを知りたいです。Cont

注 3: 私の Racketeer メンターは、同様の Racket プログラムをまとめてくれました (すべてのリビジョンを参照)。彼のパイプ/パイプアウト手法は、を使用して Haskell に変換できますContか?

tl;dr私は MonadFix を使用してこれを行うことができ、他の誰かが Racket の継続コンビネータを使用してそれを行うことができました。ContこれはHaskellでできると確信しています。方法を教えてもらえますか？

私は大きな結び目を結ぶことを含むHaskellプロジェクトに取り組んでいます：グラフのシリアル化された表現を解析しています。各ノードはファイルにオフセットされており、そのオフセットによって別のノードを参照する場合があります。したがって、解析中にオフセットからノードへのマップを作成する必要があります。これは、do recブロック内で自分自身にフィードバックできます。

私はこれを機能させており、ちょっと-ちょっと-合理的に抽象化されて-風のStateTモナド変換子になっています：

このtie関数は魔法が起こる場所です。呼び出しによってrunRecStateT値と状態が生成され、それを独自の未来としてフィードします。get過去と未来の両方の状態から読み取ることがputできますが、「現在」を変更することしかできないことに注意してください。

質問1：これは一般的にこの結び目を結ぶパターンを実装するための適切な方法のように見えますか？またはさらに良いことに、誰かがこれに対する一般的な解決策を実装しましたが、ハッキングを覗き見したときに見落としていましたか？モナドはおそらくもっとエレガントに見えたので（Dan Burtonからの同様の投稿Contを参照）、しばらくの間モナドに頭を打ちましたが、うまくいきませんでした。

完全に主観的な質問2：私の呼び出しコードが最終的にどのように見えるかについて私は完全にわくわくしていません：

ここでの実装の詳細は省略されています。明らかに重要な点は、pastand状態を取得し、letバインディング内futureでそれらをパターンマッチングして（または前のパターンを明示的に遅延させて）、気になるものを抽出してから、ノードを構築して更新する必要があることです。私の状態と最後にノードを返します。不必要に冗長に思えますが、特に、と状態を抽出するパターンを誤って厳密にすることがいかに簡単であるかが嫌いです。それで、誰かがより良いインターフェースを考えることができますか？pastfuture

binary簡単な質問ですが、パッケージは 2 つの型を定義しているGetことPutを願っています。前者は本質的に状態モナドであり、後者は本質的にライターです。状態とライターの両方に合理的なMonadFixインスタンスがあるため、私はそれを期待していますし、そうするGetでしょPutう。

Getします。Putしません。では、 (本当に) の適切なMonadFixインスタンスを定義することは可能ですか?PutPutM

より一般的な質問は、型クラスのインスタンスがその型クラスの法則を実際に満たしていることを通常どのように検証するのでしょうか?

のバグだと思われるものに出くわしましたが、これは私のHaskellData.Mapの知識のバグである可能性も十分にあります。誰かがそれが何であるかを明確にできることを願っています:)

この要点を参照してください。循環リンク リスト構造をバイトストリームにシリアル化しています。任意のノードに対して、次の形式をとります。

バイトのペアとしてシリアル化されることを期待しています。最初のバイトは を表し、2 番目のバイトはを配置できるvalバイトストリーム内のオフセットを表します。nextたとえば、次のことを期待しています。

として連載予定[0, 1, 1, 0]。大きな問題ではない。

ここで少しトリッキーな部分は、バイトストリーム オフセットの「結び目を結ぶ」MonadFixためにインスタンスを利用していることです。ノードからオフセットへのマップを維持し、シリアル化中にマップにデータを入力しますが、そうでないマップ内のエントリも参照します。RWSTシリアル化が完了するまで、まだ存在する必要があります。

これは、マップの実装がData.HashMap.Lazy( unordered-containersから) である場合にうまく機能します。ただし、実装が通常の場合Data.Map(コンテナーMapから)、プログラム スタックがオーバーフローします (しゃれは意図されていません) (==)。

私の質問は次のとおりです。これは のバグですか、それとも欠陥があるData.Map場合にこれらの構造がどのように動作するかについての私の仮定ですか?mfix

http://hackage.haskell.org/package/free inをControl.Monad.Free.Free使用すると、任意のの「無料モナド」にアクセスできますFunctor。ただし、MonadFixインスタンスはありません。これは、そのようなインスタンスを記述できないためですか、それとも単に省略されたためですか？

そのようなインスタンスを書き込めないのなら、どうしてですか？

私はOcamlでhaskellのようなdo表記のcamlp4拡張機能に取り組んでおり、GHCが再帰的なdo-bindings（-XDoRecで有効化）をコンパイルする方法を理解しようとしています。
モナディック不動点コンビネータが厳密な言語（Ocaml / F＃/ SML / ...など）で存在することは可能でしょうか？
はいの場合、どのように見えますか？とても便利でしょうか？

特定の効果がなくなるまでアクションを実行するという一般的なパターンに気付きましたが、これは固定点を意味する (つまり、将来の効果はあり得ない) ことがわかっている場合です。これには型クラスがありますか？

これはMonadFixでカバーされていますか? コードを見るとそのように見えますが、 wiki ページで「「再帰」を見て、アクションを再帰的にまたは繰り返し実行することを意味すると推測したくなります。いいえ。」に怖がっていました。

また、不動点は恒等の双対のようなものだと私には思えます。つまり、同一性は、非同一性 ((+) の場合は 0、(*) の場合は 1、追加の場合は [] など) と組み合わせると消えます。一方、固定点は、以下の「リラックス」操作で非固定点を非表示にします。この双対性を形式化する方法はありますか?そうすると便利ですか? つまり、MonadPlus および/または Monoid と MonadRelax の間に関係はありますか?

最後に、リラックスはほぼ展開/アナモフィズムであることに気付きました。と表現した方が良いでしょうか？