逆の状態のモナド


モンタナ州


我々は以前に、状態モナドが各々のステップが結果を生じて、また、実行している状態を更新する計算をつくるのに用いられることができると以前に見ました.たとえば、次のようにスタックの状態を保持する計算を作成できます.
let comp =
    state {
        let! a = popC
        do! pushC 5
        do! pushC 8
        let! b = popC
        return a - b
    }
英語では、この計算は以下のようになります.
  • スタックから先頭の値を取り出し、結果をa .
  • スタックに5を押します.
  • スタックに8を押します.
  • スタックから一番上の値を取り出します( 8は知っています)、結果を変数b .
  • 返り値a - b 計算の最終結果として.
  • このような特定のスタックで計算を実行できます.
    let stack = [9; 0; 2; 1; 0] |> Stack.ofList
    Stateful.run stack comp
    
    結果は9 - 8 = 1 スタックの最後の状態は[5; 0; 2; 1; 0] .

    逆状態モナド


    それは我々が結果(すなわち、計算の中の名前付きの値)が予想通りに流れ続けている類似のモナドをつくることができるということがわかります、しかし、まるで彼らが時間内に後方に旅行しているように、状態への変化は逆の順序で起こります!私は、そのような計算のために多くの実用的な用途があると思いません.
    我々が上を歩いた同じ計算を逆にすることから始めましょう:
    let rcomp =
        rstate {
            let! a = popC
            do! pushC 5
            do! pushC 8
            let! b = popC
            return lazy (a.Value - b.Value)
        }
    
    これは、逆の状態Monadのための計算ビルダーを使用している以外はほとんど同じですrstate ) の代わりにstate ビルダー.しかし、1つの非常に重要な違いは、すべての結果は怠惰な値です.これは無限の退陣を避けるために重要です.例えば、結果a and b 両方ともint 元の例では、ここでは、両方のタイプLazy<int> 代わりに.我々は計算の中で怠惰にこれらの結果を使用するには無料ですが、私たちは早急にその評価をトリガする何かを行うことはできません.これが返り値が計算に注意深く書かれている理由ですa - b 怠惰に.完全な計算式RStateful<Stack<int>, Lazy<int>> , これは、整数のスタックで動作し、最終結果として遅延整数を返す逆状態計算であることを意味します.
    この計算を実行するときに何が起こるかを示します.
  • 状態が逆の順序で流れているので、最初にトップ値がスタックからポップされ、b .
  • 後方に動く8 スタックにプッシュされます.
  • Then 5 スタックにプッシュされます.
  • 一番上の値はスタックからポップされます(5でなければならない)a .
  • 最後に、我々は帰りますa - b 怠惰に.
  • 注意:結果は流れます、しかし、州は流れます.
    この演算は、以前と同じ入力スタックで実行できます.
    let stack = [9; 0; 2; 1; 0] |> Stack.ofList
    RStateful.run stack rcomp   // reverse state monad
    
    結果は5 - 9 = -4 スタックの最後の状態は[8; 0; 2; 1; 0] .

    どうやって?


    これはばかげているようですが、うまくいきます.キーはいつものようにbind メソッド:
    let bind binder rstateful =
        RStateful (fun state ->
            let rec resultAfinal = lazy (run intermediate.Value rstateful)
            and resultA = lazy (fst resultAfinal.Value)
            and final = lazy (snd resultAfinal.Value)
            and resultBintermediate = lazy (run state (binder resultA))   // lazy result passed to binder
            and resultB = lazy (fst resultBintermediate.Value)
            and intermediate : Lazy<_> = lazy (snd resultBintermediate.Value)
            resultB.Value, final.Value)
    
    これは通常の状態モナドの対応するBINDよりかなり複雑であるので、詳細はそれを通して歩くつもりはありません.注目すべき重要なことはstate を2番目のステップに渡すbinder ), それからintermediate 状態は最初のステップに渡されるrstateful ). これは、通常の状態モナドがどのように動作するかの逆です.しかし、最初のステップの結果resultA ) は第2ステップにまだ渡され、乱暴に、そしてそのステップの結果resultB ) が返される.
    また、私はこれをする実用的な理由があまりないと強調したい.それができるので、それは私にとって十分です.

    参考文献


    狂った機能プログラミングアイデアは通常Haskellから出ます、そして、これは例外でありません.そこには多くの情報がありませんが、役に立つかもしれません.
  • What are some crazy things one can do with monads in Haskell?
  • Time travel in Haskell for dummies
  • The Curious Time-Traveling Reverse State Monad
  • Mindfuck: The Reverse State Monad