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

Haskell

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モナドでなんで状態の持ちまわしができるんでしょう？そこのところがまだ理解できてません．