Stateモナドを考える（その4）

モナド則の確認

一個一個モナド則を確認してみます．Haskellの表記としては間違っているかもしれませんが，意味が通じるように書きます．

-- return a >>= k == k a

runState (return a) s = (a,s)
runState (m >>= k) s = let (a, s') = runState m s
                       in runState (k a) s'
m = return a
runState (m >>= k) s = let (a, s') = (\s -> (a,s)) s
                       in runState (k a) s'
                     = runStatte (k a) s

return a >>= k == k a

次は

-- m >>= return  ==  m

runState (m >>= return) s = let (a, s') = runState m s
                            in runState (return a) s'
                          = let (a, s') = runState m s in (a,s')
                          = runState m s

m >>= return  ==  m

そして，

-- m >>= (\x -> k x >>= h) ==  (m >>= k) >>= h

runState (m >>= (\x -> k x >>= h)) s
= let (a,s') = State m s
  in runState ((\x -> k x >>= h) a) s'
= let (a,s')   = State m s
      (a',s'') = State ((\x ->k x) a) s'
  in runState (h a) s''
= let (a,s')   = State m s
      (a',s'') = State (k a) s'
  in runState (h a') s''
= let (a',s'') = runtate (m>>=k) s
  in runState (h a') s''
= runState ( (m >>= k) >>= h ) s

m >>= (\x -> k x >>= h) ==  (m >>= k) >>= h

最後に

-- fmap f m  ==  m >>= return . f

(fmap f m) s = let (a,s') = runState m s
               in (f a, s')
             = let (a,s') = runState m s
               in runState ((return.f) a) s'
             = runState (m >>= return.f) s

fmap f m  ==  m >>= return . f

ということで，State sはモナドでfunctorのインスタンスであることが分かりました．

Stateモナドから状態と値を引っ張り出す関数も定義されています．

evalState :: State s a -- 評価される状態
          -> s         -- 初期値
          -> a         -- 初期値が適用された結果の値
evalState m s = fst (runState m s)

execState :: State s a -- 評価される状態
          -> s         -- 初期値
          -> s         -- 初期値が適用された状態
execState m s = snd (runState m s)

また，注意しなければいけないのは，Stateモナドといってますが，実際にMonadクラスのインスタンスになっているのはState sなので，本当はState sモナドとでもいうべきだろうということです．State s aとした場合，Mayby aとの類推でいけば，MaybeにあたるものはState sでしょう．したがって，do記法で <- ででてくる値は a の部分であり，>>= も aの値が渡っていくのです．

MonadStateクラス

さらに，MonadStateなるもののインスタンスでもあります．

class (Monad m) => MonadState s m | m -> s where
    get :: m s
    put :: s -> m ()

modify :: (MonadState s m) => (s -> s) -> m ()
modify f = do s <- get
              put (f s)

gets :: (MonadState s m) => (s -> a) -> m a
gets f = do
    s <- get
    return (f s)

instance宣言で，``|''があったり，型変数が複数ありますが，これは型変数が複数あると型推論が怪しくなることがあるので，| の右側に型推論のための補助情報（関数従属性）を与える構文だそうです．この場合，モナドであるmからsが一意に定まるということです．

MonadStateクラスは，モナドの中から状態を取り出すget，逆にモナドの中の状態を取り替えるputをクラスメソッドとして必要とします．これらを用いて，modify/getsが定義されています．modifyはgetで得た状態をfで変換してそれをputで戻す，getsはgetで得た状態をfで変換した状態を作り出すものです．

次のように宣言されることで，StateモナドがMonadoStateモナドのインスタンスになります．

instance MonadState s (State s) where
    get   = State $ \s -> (s, s)
    put s = State $ \_ -> ((), s)

これらのクラスメソッドは型を明示すると分かりやすいと思います．

get :: (MonadState s m) => m s
put :: (MonadState s m) => s -> m ()

今は，mがState sのケースなので，

get :: State s s
put :: s -> State s ()

です．これをみると，getはStateモナドそのもの，putはStateモナドを値にとる関数です．

これがなぜ｢状態の取得」や「状態の取替え」になるのでしょうか？

シンプルな例：tick

Control.Monad.State.Lazyにあるサンプルtickを考えます．オリジナルはIntなのですが，どっちが状態（State）でどっちが値（Value）なのか分からなくなりそうなのでtypeで別名をつけました．

import Control.Monad.State

type St  = Int
type Val = Int

tick :: State St Val
tick = do n <- get
          put (n+1)
          return n

都合上，do記法をやめて，見やすいように補助的な関数を追加します．

tick = get >>= g
g :: Val -> State St Val -- あえてwhereにしない
g n = put (n+1) >> return n

まず，gを考えます．

(>>) :: forall a b. m a -> m b -> m b
m >> k = m >>= \_ -> k
       = State $ \s -> let (a.s') = runState m s 
                       in runState k s' 

であることに留意すると，

g n = put (n+1) >> return n
= State $ \s -> let (a.s') = runState (put (n+1)) s 
                in runState (return n) s'
= State $ \s -> let s'=n+1 in runState (return n) s'
= State $ \s -> runState (return n) (n+1)
= State $ \s -> (\s->(n,s)) (n+1)
= State $ \s -> (n,n+1)

となります．値と状態がしっかり入り込みました．本体のtickを考えると，

tick = get >>= g
= State $ \s -> let (a,s')= runState get s
                in runState (g a) s'
= State $ \s -> let (a,s')= (\s->(s,s)) s
                in runState (g a) s'
= State $ \s -> let (a,s')= (s,s)
                in runState (g a) s'
= State $ \s -> runState (g s) s
= State $ \s -> (\_ -> (s,s+1)) s
= State $ \s -> (s,s+1)

となります．感動物です．do記法にもどると

tick = do n <- get
          put (n+1)
          return n

でした．このdo記法はStateがつきますがgetで「状態s」を得て，次の「状態s+1」と「値s」を取得するということを直観的に（手続き的にというべき）表記してくれています．つまり，どこかに「代入可能な変数」があって，getがその変数から「種」をとってきて，putがその「変数」の状態部分を更新して，returnが値部分を更新するように見えます．

さて，このtickの実行例をあげてみます．

runState tick 0 -- (0,1)
runState tick 1 -- (1,2)
runState tick 2 -- (2,3)
runState (tick >> tick) 1 -- (2,3)
runState (tick >> tick >> tick) 1 -- (3,4)
runState (tick >> tick >> tick >> tick) 1 -- (3,4)

tick =State $ \s->(s,s+1)なので，最初の三つはすぐ理解できます．次の三つ，モナドの(>>)を使ってるのは，sからスタートして(>>)を超えるときに(s,s+1)が次に伝わるのでこのような結果になります．(>>)の定義にしたがって展開してみます．

tick >> tick = tick >>= (\_ -> tick)
= State $ \s -> let (a,s') = runState tick s
                in runState ((\_ -> tick) a) s'
= State $ \s -> let (a,s')=(s,s+1)
                in runState tick s'
= State $ \s -> runState tick s+1
= State $ \s -> (s+1,s+2) -- runState tick s = (s,s+1)に注意

あとは全く同様です．

(>>=)とreturnの巧妙な構成，(State s)がモナド（クラスのインスタンス）であること，モナド則やdo記法が絡み合って，よく出来ているとしかいえません．また，この「状態の受け渡し」は，いわば一個の（モナドによる）計算の中だけで閉じているという点で，しっかり関数の中で閉じているのです．