注目の書籍好評発売中！
|
本物のプログラマはHaskellを使う
第21回 更新操作を一般化するためのSTモナド前回は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 IntrunSTを実際に使用する場合には，もう少し考えなくてはならないこともあります。例えば，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 . twiceST2008年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以上の非叙述的多相性が必要になるかもしれません（参考リンク）。 |
