問題タブ [tying-the-knot]

Haskell 関連のものを読んでいると、「結び目を結ぶ」という表現に出くわすことがあります。

それで、この概念の説明を理解するのに適切で、基本的で、簡単なものはありますか?

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

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

これは言語です：

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

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

編集：

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

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

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

理論的には、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でできると確信しています。方法を教えてもらえますか？

次のようなばかげた小さなケース クラスがあるとします。

is 、 is 、isなどaをb不変に定義するにはどうすればよいですか? scala は「結び目を作る」方法を提供していますか? 私はこのようなことをしたいと思います:a.otherbb.othera

可能性

Haskell では、次のようにします。

aおよびへのバインディングがb同じlet式に含まれている場所、または最上位にある場所。

または、Haskell の自動 letrec 機能を悪用せずに:

遅延パターン に注意してください。これは~(a', b')重要です。

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

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

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

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

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

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

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

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

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

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

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

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

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

どうしていいかわからない問題があります。誰かが特定の問題について私を助けてくれるかどうか尋ねようとしていましたが、より一般的な質問をすることができ、結果としてより一般的な理解が得られることを願っています. うまくいけば。だからここに行きます：

たとえば、スペース リークなどの明らかな問題が発生するため、プログラムがあまりにも怠惰な場合は、通常は明らかです。逆の問題があります: 私のプログラムは厳しすぎます。私は結び目を作ろうとし ていますが、私がやろうとしている特定のことが、私が必要とする怠惰をどうにかして打ち負かすことがわかりました. 私の一般的な質問は、不要な厳密さをどのようにデバッグするのですか?

完全を期すために、ここに私の具体的なケースを示します。私はRWS、ライター コンポーネントがマップにデータを入力し、リーダー コンポーネントがそのマップの最終状態を観察します。マップへの入力が完了するまで、このマップに対して厳密なことを行うことはできません。次のように、マップ内の値を検索することは問題ないようです。

しかし、 の(!)使用errorに失敗します。代わりに、モナドの の使用に失敗することを好みfailます。だから私は次のようなことをしたいと思います：

これにより、私のプログラム<<loop>>は理解できません。これがを使用するよりも厳密であるようには思え(!)ませんが、明らかに私は間違っています...

数年前、私は次の問題 (またはそれに似た問題) を与えるアルゴリズムのコースを受講しました。

n一度に 2 階までしか上がらず、一度に 3 階までしか上がれないエレベータ付きの階数の建物があります。i動的計画法を使用して、エレベーターがフロアからフロアに移動するのに必要なステップ数を計算する関数を作成しますj。

これは、ステートフルなアプローチを使用すると明らかに簡単です。n 要素の長さの配列を作成し、値を入力します。結果を再帰的に渡すことで結果を蓄積する、技術的に非ステートフルなアプローチを使用することもできます。私の質問は、遅延評価を使用して結び目を作ることにより、非ステートフルな方法でこれを行う方法です。

私は正しい数式を考案したと思います：

ここでi+2、 とi-3は許容値の範囲内です。

残念ながら、私はそれを終了させることはできません。ケースを最初に置いてi+2から偶数階を選択すると、目標レベルより下の偶数階を評価することができますが、それだけです。他のすべての場合、それは最高の偶数階に向かってまっすぐに発射され、3 レベル下がってから繰り返され、上部のいくつかの階の間で永遠に振動しているのではないかと思います.

したがって、おそらく深さ優先の方法で無限空間 (または有限だがループあり) を探索しています。ステートフルなアプローチを効果的に模倣する間に大量のデータ構造を使用せずに、幅優先の方法でスペースを探索する方法を考えることはできません。

この単純な問題はがっかりするほど難しいですが、1 次元で解決策を見たので、問題の 2 次元バリエーションに対してもそれを機能させることができるのではないかと思います。

編集：多くの回答が別の方法で問題を解決しようとしました。問題自体は私にとって興味深いものではありません。問題は使用される方法に関するものです。minimal潜在的に無限の数を比較できる関数を作成する Chaosmatter のアプローチは、おそらく正しい方向への一歩です。残念ながら、100 階建ての建物を表すリストを作成しようとすると、サブ問題の解が再利用されないため、結果の計算に時間がかかりすぎます。

自己参照データ構造を使用しようとしましたが、終了しません。ある種の無限ループが発生しています。私が何をしようとしているのかを理解できるように、コードを投稿します。誰かが遅延を使用して自己参照データ構造で動的プログラミングを使用して実際に問題を解決し、複数回の計算を回避できる場合は、受け入れられた回答を変更します。

1 + levels !! i以前に計算された結果を参照しようとする方法と、 の値を有効なfilter (\n -> n >= 0 && n <= 10) [x+2,x-3]値に制限しようとする方法を確認できます。i私が言ったように、これは実際には機能しません。単に、この問題を解決したい方法を示しているだけです。それを解決する他の方法は私にとって興味深いものではありません。