前回はSTモナドの基本的な特徴やSTモナドとかかわりのある拡張機能について説明しました。今回はそれらの知識を基にして,「STモナドのインタフェースとして提供されている関数」と「STモナドのさらなる性質」を説明します。
runST関数の働き
前回の拡張機能に対する説明で,runST関数を考察のための材料が揃いました。こうした知識を基に,runST関数について考えましょう。
まずはそれぞれの型について確認します。
STモナドは型ST sに対して定義されています。
Prelude Control.Monad.ST> :i ST newtype ST s a = GHC.ST.ST (GHC.ST.STRep s a) -- Defined in GHC.ST instance Monad (ST s) -- Defined in GHC.ST instance Functor (ST s) -- Defined in GHC.ST instance Show (ST s a) -- Defined in GHC.ST
したがって,STアクションの持つ型は「ST s a」です。
Prelude Control.Monad.ST> :t return 20::(Num a) => ST s a return 20::(Num a) => ST s a :: (Num a) => ST s a
一方,STアクションを実行するrunSTは,「(forall s. ST s a) -> a」というランク2の型を持つ関数として定義されています。
Prelude Control.Monad.ST> :t runST runST :: (forall s. ST s a) -> a
この結果,runSTは型変数sが多相的なままのSTアクションを実行できます。
Prelude Control.Monad.ST> :t runST (return 20) runST (return 20) :: (Num t) => t Prelude Control.Monad.ST> runST (return 20) 20
逆に,型変数sを単相型に固定した場合には実行できなくなってしまいます。あくまでrunST関数が型変数sを多相的に扱うのであり,ST型で型変数sが存在量化された型として定義されているわけではないからです。
Prelude Control.Monad.ST> runST (return 20::ST Int Integer) <interactive>:1:7: Couldn't match expected type `s' against inferred type `Int' `s' is a rigid type variable bound by the polymorphic type `forall s. ST s a' at <interactive>:1:0 Expected type: ST s Integer Inferred type: ST Int Integer In the first argument of `runST', namely `(return 20 :: ST Int Integer)' In the expression: runST (return 20 :: ST Int Integer) Prelude Control.Monad.ST> runST (return 20::ST RealWorld Integer) <interactive>:1:7: Couldn't match expected type `s' against inferred type `RealWorld' `s' is a rigid type variable bound by the polymorphic type `forall s. ST s a' at <interactive>:1:0 Expected type: ST s Integer Inferred type: ST RealWorld Integer In the first argument of `runST', namely `(return 20 :: ST RealWorld Integer)' In the expression: runST (return 20 :: ST RealWorld Integer)
では,STRefやSTArray,STUArrayの型はどうでしょうか? それぞれの型について調べればわかるように,これらのデータ型は「STRef s a」「STArray s i e」のように,型変数sを型の構成要素の一つとして抱えています。
Prelude Data.STRef> :i STRef data STRef s a = GHC.STRef.STRef (GHC.Prim.MutVar# s a) -- Defined in GHC.STRef instance Eq (STRef s a) -- Defined in GHC.STRef Prelude Data.STRef> :m Data.Array.ST Prelude Data.Array.ST> :i STArray data STArray s i e = GHC.Arr.STArray !i !i !Int (GHC.Prim.MutableArray# s e) -- Defined in GHC.Arr instance Eq (STArray s i e) -- Defined in GHC.Arr Prelude Data.Array.ST> :i STUArray data STUArray s i a = Data.Array.Base.STUArray !i !i !Int (GHC.Prim.MutableByteArray# s) -- Defined in Data.Array.Base instance Eq (STUArray s i e) -- Defined in Data.Array.Base
これらのデータ型の型変数sは,new*を使ってデータ型を作成する時点でSTモナドの型変数sに結び付けられます。
Prelude Data.STRef> :browse modifySTRef :: STRef s a -> (a -> a) -> GHC.ST.ST s () data STRef s a = GHC.STRef.STRef (GHC.Prim.MutVar# s a) newSTRef :: a -> GHC.ST.ST s (STRef s a) readSTRef :: STRef s a -> GHC.ST.ST s a writeSTRef :: STRef s a -> a -> GHC.ST.ST s () Prelude Control.Monad.ST Data.Array.ST> :i MArray class (Monad m) => MArray a e m where getBounds :: (Ix i) => a i e -> m (i, i) Data.Array.Base.getNumElements :: (Ix i) => a i e -> m Int newArray :: (Ix i) => (i, i) -> e -> m (a i e) newArray_ :: (Ix i) => (i, i) -> m (a i e) Data.Array.Base.unsafeNewArray_ :: (Ix i) => (i, i) -> m (a i e) Data.Array.Base.unsafeRead :: (Ix i) => a i e -> Int -> m e Data.Array.Base.unsafeWrite :: (Ix i) => a i e -> Int -> e -> m () -- Defined in Data.Array.Base instance MArray (STArray s) e (ST s) -- Defined in Data.Array.Base instance MArray (STUArray s) Bool (ST s) -- Defined in Data.Array.Base instance MArray (STUArray s) Char (ST s) -- Defined in Data.Array.Base instance MArray (STUArray s) Int (ST s) -- Defined in Data.Array.Base instance MArray (STUArray s) Float (ST s) -- Defined in Data.Array.Base instance MArray (STUArray s) Double (ST s) -- Defined in Data.Array.Base
つまり,これらのデータ型を返すSTアクションは,必ず「ST s (ST** s a ... )」という型を持つことになります。
では,これらのデータ型を返すSTアクションをrunSTに渡すと,どうなるでしょうか?
runSTの型「(forall s. ST s a) -> a」に暗黙のforallを追加すると,「forall a. ((forall s. ST s a) -> a)」になります。これを型「ST s (ST** s a ... )」に対して適用すると,「forall a. ((forall s. ST s (ST** s a ... )) -> ST** s a ...)」になります。この場合,(ST** s a ... )の型変数aに対して多相性を与えることはできますが,型変数sに対して多相性を与えることはできません。(ST** s a ... )のsはforall sの範囲外にあるためです。この結果,このような型を作り出す式は,型検査の段階で不正とみなされます。
これが「STRefやSTArrayなどのような更新可能なデータ型をSTモナドの外に持ち出す」式を型エラーとする仕組みです。第7回や前回で出てきたエラー・メッセージをもう一度読み返すと,今回の説明の意味がわかると思います。
Prelude Control.Monad.ST Data.STRef> runST $ newSTRef 23 <interactive>:1:0: Inferred type is less polymorphic than expected Quantified type variable `s' escapes In the second argument of `($)', namely `newSTRef 23' In the expression: runST $ newSTRef 23 In the definition of `it': it = runST $ newSTRef 23 Prelude Data.Array.ST Control.Monad.ST> :m Control.Monad.ST Data.Array.ST Prelude Data.Array.ST Control.Monad.ST> :t newArray (2,33) 11:: ST s (STArray s Int Int) newArray (2,33) 11:: ST s (STArray s Int Int) :: ST s (STArray s Int Int) Prelude Data.Array.ST Control.Monad.ST> :t runST (newArray (2,33) 11:: ST s (STArray s Int Int)) <interactive>:1:0: Inferred type is less polymorphic than expected Quantified type variable `s' escapes In the first argument of `runST', namely `(newArray (2, 33) 11 :: ST s (STArray s Int Int))'
なお,第19回で紹介したrunSTArrayやrunSTUArrayは,「ST s (ST*Array s i e)」に対して定義されているので,「変更可能なMArrayから変更不可能なIArrayを生成する」関数として問題なく働きます。
Prelude Data.Array.ST> :t runSTArray runSTArray :: (Ix i) => (forall s. GHC.ST.ST s (STArray s i e)) -> GHC.Arr.Array i e Prelude Data.Array.ST> :t runSTUArray runSTUArray :: (Ix i) => (forall s. GHC.ST.ST s (STUArray s i e)) -> Data.Array.Base.UArray i e Prelude Data.Array.ST> :t runSTArray (newArray (2,33) 11) runSTArray (newArray (2,33) 11) :: (Num t, Num t1, Ix t) => GHC.Arr.Array t t1 Prelude Data.Array.ST> :m +Control.Monad.ST Prelude Data.Array.ST Control.Monad.ST> :t runSTUArray (newArray (2,33) 11:: STs (STUArray s Int Int)) runSTUArray (newArray (2,33) 11:: ST s (STUArray s Int Int)) :: Data.Array.Base.UArray Int Int
runSTを実際に使用する場合には,もう少し考えなくてはならないこともあります。例えば,twice''を以下のように関数合成の形で記述することはできません。
module ST where import Control.Monad.ST import Data.STRef twiceST x = do r <- newSTRef x modifySTRef r (++x) y <- readSTRef r return y twice'' = runST . twiceST
2008年6月現在のGHCやHugsの型推論では,型変数sがforallの範囲を超えてしまうためです。
$ ghci ST.hs GHCi, version 6.8.3: http://www.haskell.org/ghc/ :? for help Loading package base ... linking ... done. [1 of 1] Compiling ST ( ST.hs, interpreted ) LazyST.hs:11:18: Inferred type is less polymorphic than expected Quantified type variable `s' escapes Expected type: [a] -> forall s1. ST s1 [a] Inferred type: [a] -> ST s [a] In the second argument of `(.)', namely `twiceST' In the expression: runST . twiceST Failed, modules loaded: none.
適切に機能させるには,runSTで使用する変数xを明示的に渡す必要があります。
twice'' x = runST (twiceST x)
$ ghci ST.hs GHCi, version 6.8.3: http://www.haskell.org/ghc/ :? for help Loading package base ... linking ... done. [1 of 1] Compiling ST ( ST.hs, interpreted ) Ok, modules loaded: ST. *ST> twice'' [3,6,5] [3,6,5,3,6,5]
また,現在のHugsの型推論では,runST関数と$演算子を組み合わせて使用することはできません。Hugsでは必ず括弧を使ってコードを記述する必要があります。
Control.Monad.ST> runST (return 12) 12 Control.Monad.ST> runST $ return 12 ERROR - Use of runST requires at least 1 argument
GHCではこのような制限に煩わされることはありません。しかし,GHCとHugsの両方で利用するコードを記述する場合には,こうした点に留意する必要があります。
Prelude Control.Monad.ST> runST $ return 12 12
考えなければならないのは,こうした処理系固有の制限だけではありません。runSTを使った関数を組み立てるとき,場合によっては多相的な構成要素やランク3以上の非叙述的多相性が必要になるかもしれません(参考リンク)。