注目の書籍好評発売中！
|
本物のプログラマはHaskellを使う
第20回 更新を高速化するためのSTモナド前回，MArrayクラスの配列を扱えるモナドの一つとして，STモナドを挙げました。他にも第6回や第7回で何度かSTモナドについて言及しています。ただ，これまでSTモナドについてまとまった説明はしてきませんでした。そこで今回から2回にわたってSTモナドの詳細を解説していくことにしました。 今回は，STモナドの基本的な特徴，およびSTモナドと関係のある拡張機能について説明します。
STモナドの特徴第6回で参照型をエミュレートするためのものとしてStateモナドを紹介しました。しかし，Stateモナドでは「状態」の更新を扱うためにその都度新しい「値」を作成するため，本物の参照型に比べて非効率です。極端な話，前回紹介したArray型などのように，データ構造を更新するためにすべての要素を複製しなければならない可能性があります。 新しい値を作らずに既存の値を使い回すにはどうすればよいでしょうか？ 解決法は大きく二つあります。一つは処理系の最適化により不要な値の作成をなくすことです。もう一つは値を使い回すようにプログラムを書き換えることです。もし，結果も外側から見た時の使い勝手も変わらないなら，どちらの方法を使ってもユーザーにとって差はないでしょう。後者の「値を使い回すようにプログラムを書き換える」ために用意されているのが，今回説明するSTモナドです。 STモナドを使った例を見てみましょう。STモナドはControl.Monad.STモジュールをインポートすることで利用できます。 module ST where
import Control.Monad.ST
import Data.STRef
twice x = runST $ do
r <- newSTRef x
writeSTRef r (x++x)
y <- readSTRef r
return y*ST> twice [3,6,5] [3,6,5,3,6,5] Control.Monad.STモジュールに加え，Data.STRefモジュールをインポートしています。これは，STモナドで使用可能なデータ型の一つであるSTRefを使用するためのものです。 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 () STRefは第6回で触れた参照型に相当します。つまり，STRefを使った操作では参照型の中身を直接書き換えられます。上の例では，参照型の作成にnewSTRef，参照にreadSTRef，更新にwriteSTRefを使っています。 writeSTRefを使って値を直接書き換える代わりに，modifySTRefを使って更新用の関数を渡し，間接的に値を書き換えることもできます。 twice' x = runST $ do
r <- newSTRef x
modifySTRef r (++x)
y <- readSTRef r
return y*ST> twice' [3,6,5] [3,6,5,3,6,5] STモナドはどのようにしてこのようなデータ型を扱っているのでしょうか？ GHCのST型を調べると，IO型とは外部インタフェースが違うだけで，似たような定義になっていることがわかります（わかりやすいよう余分な情報を削っています）。 newtype ST s a = ST (State# s -> (# State# s, a #)) newtype IO a
= IO (State# RealWorld
-> (# State# RealWorld, a #))IOモナド版であるIORefの型定義は，STモナドではなくIOモナドで利用するためのインタフェースになっています。 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.IORef
Prelude Data.IORef> :i IORef
newtype IORef a
= GHC.IOBase.IORef (GHC.STRef.STRef GHC.Prim.RealWorld a)
-- Defined in GHC.IOBase
instance Eq (IORef a) -- Defined in GHC.IOBasemodule IORef where
import Data.IORef
twiceIO x = do
r <- newIORef x
writeIORef r (x++x)
y <- readIORef r
return y
twiceIO' x = do
r <- newIORef x
modifyIORef r (++x)
y <- readIORef r
return y*IORef> twiceIO [3,6,5] [3,6,5,3,6,5] *IORef> :t twiceIO' twice' :: [a] -> IO [a] *IORef> twiceIO' [3,6,5] [3,6,5,3,6,5] このように，STモナドの実行やSTモナドによる値の更新には，IOモナドの実行と同じ仕組みが使われてます。IOモナドと同じ仕組みで実行するため，STモナドでも参照型のようなデータ型を使って直接値の中身を書き換えられるのです。 ただ，I/Oアクションは型構成子IOでくるまれた型になるのに対し，runST関数によるSTアクションの実行は，型構成子でくるまれない通常の関数呼び出しと同じ型となります。 Prelude Control.Monad.ST> :t runST runST :: (forall s. ST s a) -> a *IORef> :t twiceIO twiceIO :: [a] -> IO [a] *IORef> :l ST [1 of 1] Compiling ST ( ST.hs, interpreted ) Ok, modules loaded: ST. *ST> :t twice twice :: [a] -> [a] IOモナドによるI/Oアクションは，通常はプログラムの本体であるmain変数から実行されます。これに対し，STモナドを使ったアクションの実行は，関数呼び出しの中で駆動される非同期なアクション（state thread）として働きます。これがIOモナドとSTモナドの大きな違いです。 ただ，非同期なアクションの実行は「参照透過性の破壊」や「それに伴うプログラム動作の非決定性」などの問題を引き起こす可能性があります。STモナドは型を使ってこうした問題の発生を防いでいます。 一つ目の工夫は，STアクションを実行するための関数である「runST」の型にあります。runSTの型は，参照型や前回紹介したSTArray，STUArrayなどの書き換え可能なデータ型が関数の外側に出て行くことを阻止します。runSTを使ってこれらのデータ型を返す関数を書こうとすると，必ず型エラーが生じます。 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))'書き換え可能なデータ型が外部に出て行かなければ，複数個所で共有される懸念はなくなります。つまり，「状態」を使った計算がアクションの中だけで完結します。結果として，関数内でのアクションの実行に伴う非決定性の問題を回避できます。ただし，unsafeThawとunsafeFreeze（またはrunST*Array）を組み合わせて使う場合には，この保証がなくなるので注意してください。 もう一つの工夫は「STモナドはIOモナドとは異なるST s型を持つものとして定義されていること」です。ST s型を持つことで，STモナドのアクションはIOモナドのアクションとは明確に区別されます。STモナドで用意されている「値の更新以外」のI/O処理を行おうとすると，型検査の段階で静的なエラーとして検出できます。 Prelude Control.Monad.ST> runST $ readFile "sample.txt"
<interactive>:1:8:
Couldn't match expected type `ST s a'
against inferred type `IO String'
In the second argument of `($)', namely `readFile "sample.txt"'
In the expression: runST $ readFile "sample.txt"
In the definition of `it': it = runST $ readFile "sample.txt"
Prelude Control.Monad.ST> runST $ print "I/O print."
<interactive>:1:8:
Couldn't match expected type `ST s a' against inferred type `IO ()'
In the second argument of `($)', namely `print "I/O print."'
In the expression: runST $ print "I/O print."
In the definition of `it': it = runST $ print "I/O print."自由なI/O処理の実行を防ぐことで，参照透過性の問題も解決できます。書き換え可能なデータ型を使った状態が他の関数と共有できず，I/Oアクションで外部の状態に触れることもできなければ，関数の評価結果は外部の状態に左右されない純粋なものになります。この結果，STアクションを使って記述した関数は，必ず同じ値を返す純粋関数としてふるまうことが保証されるのです。 |
