2010-06-06 [長年日記]
λ. STモナドとSTRefをHaskell上で実装する
[FAQ]Haskellには副作用があるのか、ないのか の話。 kazu-yamamotoさんはSTモナドを、「処理系の力を借りないといけないモナド」で、副作用や参照透明性の観点からはStateモナドと本質的に違うものだと主張している。 だけど、STモナドが処理系に組み込まれている理由は効率のためであって、意味的にはStateモナドと大差ないし、効率とあと細かい点を気にしなければHaskellレベルでも実装できるはず。 というわけで書いてみたのが以下のコード。
{-# LANGUAGE Rank2Types, ExistentialQuantification #-}
import Control.Monad.State
import qualified Data.IntMap as IntMap
import Unsafe.Coerce
type ST s a = State (IntMap.IntMap U) a
data U = forall a. U a
newtype STRef s a = STRef Int
runST :: (forall s. ST s a) -> a
runST m = evalState m IntMap.empty
newSTRef :: a -> ST s (STRef s a)
newSTRef x = do
h <- get
let key = IntMap.size h
put (IntMap.insert key (U x) h)
return (STRef key)
readSTRef :: STRef s a -> ST s a
readSTRef (STRef key) = do
h <- get
case h IntMap.! key of
U x -> return (unsafeCoerce x)
writeSTRef :: STRef s a -> a -> ST s ()
writeSTRef (STRef key) x = modify (IntMap.insert key (U x))
あくまで proof of concept なので、コードを単純にするためにIntが溢れることとかは無視している。 それから、細かい点と書いたのは反則技である unsafeCoerce を使ってしまっているところ。ここでは等しい型と分かっている型の間でしか変換しないので、安全ではあるんだけれどね。
ST は破壊的代入をすることが本質だと思っています。破壊的代入をしない State のような実装を見せられても、それは ST ではないとしか、僕には言えません。小さなデータなら State でもいいですが、大きな配列だと State ではダメでしょう？なお、本当は IO で議論したいのですが、Haskell の中では runIO main ができないので、ST を持ち出しました。
もちろん、性能は本物のSTモナドとは違いますが、それは今回の話である副作用の有無には性能は関係しないでしょう。<br>性能以外全く同じ振る舞いをする二つの関数の一方にのみ副作用がある、なんてことは定義上あり得ないでしょうから、これに副作用があるならば本物のSTにもあるし、これに副作用がないならば本物のSTにも副作用はないと思います。
やっぱり議論しているレベルが違うようです。。。僕もブログを書いてみます。
というわけで、 http://d.hatena.ne.jp/kazu-yamamoto/20100607/1275872735 へと続く。