State モナドって...

前回 Writer、Reader、State モナドの理解を深めようと書いたので、State モナドについて詳しく見ていこうと思う。すごいHaskellたのしく学ぼう! を参考に進める。

State の定義

すごいHaskell P. 335 より。

newtype State s a = State { runState :: s -> (a, s) }

instance Monad (State s) where
    return x = State $ \s -> (x, s)
    (State h) >>= f = State $ \s -> let (a, newState) = h s
                                        (State g) = f a
                                     in g newState

まずは左辺のモナドから h を取り出して、それに状態 s を渡して結果と新しい状態 (a, newState) を得ている。次に右辺の f を結果の a に適用して、新しいモナド (State g) を得る。さらに、新しいモナドの中の g を新しい状態 newState に適用する。そうすると、最終的な結果と状態のペアが得られる。この一連の処理を State で包んでいる。

(a, newState) = h s この部分はわかる。うん。直感的。その後からがもやもやした感じ。

このままではよく分からないので、例を作って実際の動作を追おう。例示は理解の試金石、って言葉をどこかで聞いたような。

例

P.334, P.336 より、スタックを使った計算の例がある。まずはスタックに必須の push, pop の実装。ここでは State コンストラクタを使っているが、Control.Monad.State を使う場合、State コンストラクタは隠蔽されているので、代わりに state を使うらしい。

type Stack = [Int]

pop :: State Stack Int
pop = State $ \(x:xs) -> (x, xs)

push :: Int -> State Stack ()
push a = State $ \xs -> ((), a:xs)

P.337 より pusu, pop を使った計算の例。例としてはあまり面白くないかもしれないが、単純にする為に最後の pop を削ってある (本だと pop は 2回呼んでいる)。

stackManip :: State Stack Int
stackManip = do
    push 3
    pop

この stackManip を実行すると以下のようになる。runState は State の中にある s -> (a, s) を取り出すため。

ghci> runState stackManip [5, 8, 2, 1]
(3, [5, 8, 2, 1])

簡約?

stackManip は do 記法で書かれているので、>>= を使って書くようにしてみる。

stackManip = push 3 >> pop
           = push 3 >>= \_ -> pop

まあここまではOK。続き。

           = (State $ \xs -> ((), 3:xs)) >>= (\_ -> pop)                -- push 3 を簡約
           = State $ \s -> let (a, newState) = (\xs -> ((), 3:xs)) s    -- bind を適用
                               (State g) = (\_ -> pop) a
                            in g newState
           = State $ \s -> let (a, newState) = (\s -> ((), 3:s))        -- push を s に適用
                               (State g) = (\_ -> pop) a
                            in g newState

ここで、a が ()、newState が (3:s) であることがわかる。この場合 a は無視されるので、何でもよかったりするけど。

           = State $ \s -> let (State g) = (\_ -> pop) ()
                            in g (3:s)
           = State $ \s -> let (State g) = (State $ \(x:xs) -> (x, xs)) -- pop を簡約
                            in g (3:s)

g が *1 であることがわかる。最終的にはこんな感じ。

           = State $ \s -> (\(x:xs) -> (x, xs)) (3:s)
           = State $ \s -> \(3:s) -> (3, s)

うむ。どういう動きになっているのかはわかった。

*1:x:xs) -> (x, xs