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

sampou.orgのhttp://www.sampou.org/cgi-bin/haskell.cgi?Memoiseをほとんど丸写しして，Stateモナドを使ってフィボナッチを書いてみました．

import Control.Monad.State

rfib :: Integer -> Integer
rfib 0 = 0
rfib 1 = 1
rfib n = rfib (n-1) + rfib (n-2)

type Cache = [(Integer,Integer)] -- キャッシュ

cfib :: Integer -> State Cache Integer
cfib 0 = return 0
cfib 1 = return 1
cfib n = do cache <- get 
            case (lookup n cache) of
                  Just k  ->  return k
                  Nothing ->  do num <- liftM2 (+) (cfib (n-1)) (cfib(n-2))
                                 cache <- get -- ここなぜ？
                                 put (cache++[(n,num)])
                                 return num

fib :: Integer -> Integer
fib = flip evalState [] . cfib

memoise関数のような汎用性は犠牲にして，do記法にして一行一処理で書いています．比較のためのシンプルなものも載せています．キャッシュするものは「それ以前に計算したフィボナッチの項数とその項の値のタプル」，すなわち(0,1)，(1,1)，(10,55)のようなものです．

StateモナドはState Cache Integer として，キャッシュと計算結果を入れるようにしました．

sampou.orgのhttp://www.sampou.org/cgi-bin/haskell.cgi?Memoiseを見る前に大体なんとか動くものは書いてみたのですが，まったくキャッシュされてませんでした．原因はNothingのところの``cache <- get''に相当する部分がなかったので，キャッシュされないということでした．

• caseでcacheを使ってるのにその下位のdoの中では使えない？
• 使えないなら使えないで「スコープ外」とかエラーがでない？
• nはずっと使えてる

という，変数のスコープ（束縛のスコープ？）でぐるぐる思考が循環．

要するに，分かってないだけなのですが(笑)，結局，cacheもnもきちんと使えてて，liftM2が再帰呼び出しになってるから，その中で変更されたキャッシュを入手しないといけないのに加えて，そもそも``cahce<-get''がなければ，再帰してる最中でもキャッシュは更新されるわけがないということに気がつきました．

あとは初期状態を「空っぽ」として，それを持ちまわしながら計算させていって最後に結果だけをもらってくればいいわけです．ポイントフリーの方がかっこいい(笑)かとということで，flipを使ってる式をそのままもらいました．

けど。。。根本的な問題が一個．Stateモナドでなんで状態の持ちまわしができるんでしょう？そこのところがまだ理解できてません．

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

分からないときは定義をみるのはお約束．ということでControl.Monad.Stateをみます．

module Control.Monad.State (
  module Control.Monad.State.Lazy
  ) where

import Control.Monad.State.Lazy

はうっ・・別の呼んでますね．本体はControl.Monad.State.Lazyであって，これがエクスポートしてるものは全部エクスポートしてるということは，どこかで名前（置き場所（階層））が変わったんでしょうね，きっと．

ということで本体はControl.Monad.State.Lazyです．この中にはStateTモナドもいますが，今回はパスです．

module Control.Monad.State.Lazy (
    module Control.Monad.State.Class,
    -- * The State Monad
    State(..),
    evalState,
    execState,
    mapState,
    withState,
    -- * The StateT Monad
(中略)
    module Control.Monad,
    module Control.Monad.Fix,
    module Control.Monad.Trans,
    -- * Examples
    -- $examples
  ) where

import Control.Monad               -- ここからexportされたのもexportされる
import Control.Monad.Cont.Class
import Control.Monad.Error.Class
import Control.Monad.Fix           -- ここからexportされたのもexportされる
import Control.Monad.Reader.Class
import Control.Monad.State.Class   -- ここからexportされたのもexportされる
import Control.Monad.Trans         -- ここからexportされたのもexportされる
import Control.Monad.Writer.Class

Stateモナド（というか，とりあえずはState型というべき？）の定義は

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

であって（Control.Monad.State.Lazyより），データコンストラクタStateがくっついた関数であって，その関数にフィールドラベルrunStateが付いています．sが「状態」の型であって，「a」が計算結果の型です．State s aは「State印つきの関数」です．

StateはFuntor

StateはFunctor，平たくいえばmap（fmap）があるということです．数学でいう関手（Functor）のうちの「共変関手」の性質（射の合成の順序を保存する，恒等射は恒等射に移す）をもつものを定義できることを意味します．Functorクラスの定義も併記しておきます．

-- Functorクラスの定義
class  Functor f  where
    fmap        :: (a -> b) -> f a -> f b

-- State sがFunctorクラスのインスタンスであること
instance Functor (State s) where
    fmap g m = State $ \s -> let (a, s') = runState m s
                             in (g a, s')

-- fmapがみたさなければいけない性質
-- fmap id  ==  id 
-- fmap (f . g)  ==  fmap f . fmap g

これはそのまま納得できます．お約束のようなものですが，正確にはState sがFunctorクラスのインスタンスであることが注意．fmapの性質もid a = aであることと，fmapの定義で関数部分が状態を変化させないことから，すぐに示すことができます．