PR

 前回は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以上の非叙述的多相性が必要になるかもしれません(参考リンク)。