na_o_ysのブログ

プログラミングのメモ

join から理解する State モナド

すごいH本 14 章に出てきた State モナドの理解が難しかったので, まとめてみました.

State モナドとは

  • 状態付き計算を表現するモナド
  • 現状態 s1 を受け取り, 値 a と次状態 s2 のペアを返す関数
  • newtype State s a = State { runState :: s -> (a, s) }
    • s: 状態の型
    • a: 値の型
  • (現状態, (値, 次状態)) の集合ともみなせる

利用例

詳しくはすごいH本の 14.3 章や 解説記事 を参照.

難しい

これまでのモナドと比べて, bind の定義が複雑で難しいです.

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

f の引数は何だ?とか, newState の型は?とか考えて, 頭がこんがらがります.

そこで, bind を少し回り道して考えてみます.

bind を fmap, join に分解する

モナドの bind は fmap, join の 2 つの成分に分解することができます. また, 逆に fmap と join から bind を構成することが出来ます.

モナドの種類によって, fmap に特徴があるものと join に特徴にあるものに分かれます.

State モナドは join に特徴があるようです.

以下では, State モナドの join, fmap を順番に定義してみます.

join

join は入れ子になったモナドを潰して一つにする操作です.

join :: Monad m => m (m a) -> m a で表されます.

List モナドだと平坦化 (flatten) と同じですね.

State モナドの join は, 入れ子になった状態付き計算を順に適用する, 関数合成のようなイメージです.

join' :: State s (State s a) -> State s a
join' (State outer) = State $
  \s ->                                     -- 現状態 s を受け取り
    let ((State inner), newState) = outer s -- outer に適用してから
    in  inner newState                      -- inner に適用

join' は入れ子の State モナドを受け取り, 「現状態 s に対して outer, inner を順に適用した結果を返す」State モナドを返します.

入れ子になった State モナドの文脈 (状態付き計算) が, join' によって単一の文脈に糊付けされます.

State モナドは「現状態 s1 を受け取り, 値 a と次状態 s2 のペアを返す関数」なので, ここで定義した join' が State モナドの文脈に沿っていることは納得できると思います.

これが State モナドの核となる部分のようです.

fmap

fmap は単に計算結果の値を map するだけです.

(s -> (a, s)), (s -> (b, s)) はそれぞれ State モナドを構成する関数を表しています.

mapValue :: (a -> b) -> (s -> (a, s)) -> (s -> (b, s))
mapValue f runState' = \s ->
                          let (a, newState) = runState' s
                          in  (f a, newState)  -- 計算結果 a を変換

fmap' f (State h) = State $ mapValue f h

fmap, join から bind を導く

bind は fmap, join を使って次のように構成できます.

m >>= f = join $ fmap f m

f :: Monad m => a -> m b ですので, fmap f m で入れ子モナド m (m b) が作られます.

この入れ子モナドを join で糊付けすれば bind が出来上がります.

instance Monad (State s) where
  return a = State $ \s -> (a, s)
  s >>= f  = join' $ fmap' f s

この宣言で State はモナドとして正しく動作します.

また join', fmap' を前述の定義式に置き換えて適当に式変形をすれば bind の定義式そのものを導くこともできます.

参考文献