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 の定義式そのものを導くこともできます.
