STモナドと遅延評価
IOモナドを使ってI/Oアクションを組み立てる場合と同様に,STアクションも正格な状態の受け渡しの列として組み立てられます。結果として,STモナドはIOモナドと同じく一枚岩として動作するものになります。
モナド内で遅延評価が働くようにするにはどうすればよいでしょうか?
答えの一つは,第7回で紹介したunsafeInterleaveIOに類似した関数であるunsafeInterleaveSTを使うことです。
Prelude Control.Monad.ST> :t unsafeInterleaveST unsafeInterleaveST :: ST s a -> ST s a
関数定義の内部にunsafeInterleaveSTを挟み込むことで,必要なだけ実行する遅延STアクションを実現できます。unsafeInterleaveSTの使い方については,unsafeInterleaveIOについて紹介している第7回の<cite>遅延I/O</cite>の節を参考にしてください。
もう一つの答えは,>>=演算子や>>演算子で行われる状態の受け渡しを非正格にすることです。unsafeInterleaveは「あるアクションを必要に応じて必要なだけ実行する」ものですが,場合によっては「あるアクションが実行されるかどうか」を遅延評価したいこともあるでしょう。しかし,IOモナドやSTモナドは正格に組み立てられてしまうので,そのようなアクションを実行できません。
Prelude> undefined >> return ():: IO () *** Exception: Prelude.undefined Prelude Control.Monad.ST> runST (undefined >> return 2) *** Exception: Prelude.undefined Prelude Control.Monad.ST> :m +Data.STRef Prelude Control.Monad.ST Data.STRef> runST (readSTRef undefined >> return 2) *** Exception: Prelude.undefined Prelude Control.Monad.ST Data.STRef> runST (writeSTRef undefined () >> return 2) *** Exception: Prelude.undefined Prelude Control.Monad.ST Data.STRef> runST (writeSTRef undefined () >> readSTRef undefined >> return 2) *** Exception: Prelude.undefined
IOアクションやSTアクションが,アクションの最終結果に必要ないundefinedを評価しようとして失敗しているのがわかりますね。
このような無駄なアクションの実行を省くには,>>=演算子や>>演算子による状態の受け渡しを非正格におこなう「遅延モナド(lazy monad)」を使用する必要があります。状態の受け渡しを非正格に行えば,個々のアクションを必要に応じて評価するので無駄なアクションの実行が防げます。遅延STモナドはControl.Monad.ST.Lazyモジュールで定義されています。
Prelude Control.Monad.ST.Lazy> runST (undefined >> return 2) 2 Prelude Control.Monad.ST.Lazy> runST (undefined >>= return >> return 2) 2 Prelude Control.Monad.ST.Lazy> runST (undefined >>= fmap (+2) >> return 2) 2
今度は最後のreturn 2だけが評価されるため,問題なくSTアクションを実行できます。このように,遅延モナドでは>>=演算子や>>演算子が非正格に扱われます。
ただ,遅延STモナドで使用されているST型は,正格STモナドのST型とは別に定義されています。
Prelude Control.Monad.ST.Lazy> :i ST newtype ST s a = Control.Monad.ST.Lazy.ST (Control.Monad.ST.Lazy.State s -> (a, Control.Monad.ST.Lazy.State s)) -- Defined in Control.Monad.ST.Lazy instance Monad (ST s) -- Defined in Control.Monad.ST.Lazy instance Functor (ST s) -- Defined in Control.Monad.ST.Lazy
そのため,Data.STRefモジュールのSTRefとは一緒に使用できない点に気をつけてください。
module LazyST where import Control.Monad.ST.Lazy import Data.STRef twice x = runST $ do r <- newSTRef x writeSTRef r (x++x) y <- readSTRef r return y
$ ghci LazyST.hs GHCi, version 6.8.3: http://www.haskell.org/ghc/ :? for help Loading package base ... linking ... done. [1 of 1] Compiling LazyST ( LazyST.hs, interpreted ) LazyST.hs:6:9: Couldn't match expected type `ST s t' against inferred type `GHC.ST.ST s1 (STRef s1 a)' In a 'do' expression: r <- newSTRef x In the second argument of `($)', namely `do r <- newSTRef x writeSTRef r (x ++ x) y <- readSTRef r return y' In the expression: runST $ do r <- newSTRef x writeSTRef r (x ++ x) y <- readSTRef r return y Failed, modules loaded: none. Prelude>
遅延STモナド版のSTRefはData.STRef.Lazyモジュールで別途定義されているので,そちらを利用してください。
module LazyST where import Control.Monad.ST.Lazy import Data.STRef.Lazy twice x = runST $ do r <- newSTRef x writeSTRef r (x++x) y <- readSTRef r return y
$ ghci LazyST.hs GHCi, version 6.8.3: http://www.haskell.org/ghc/ :? for help Loading package base ... linking ... done. [1 of 1] Compiling LazyST ( LazyST.hs, interpreted ) Ok, modules loaded: LazyST. *LazyST> twice [3,6,5] [3,6,5,3,6,5] *LazyST> runST (writeSTRef undefined () >> return 2) 2 *LazyST> runST (writeSTRef undefined () >> readSTRef undefined >> return 2) 2
今度は型エラーにならずに済んでいるのがわかりますね。
残念ながら,STArrayやSTUArrayの遅延STモナド版は用意されていません。ですが,Control.Monad.ST.Lazyモジュールには,STモナドを使って作成したアクションと遅延STモナドで作成したアクションの相互運用を目的とした,strictToLazyST関数とlazyToStrictST関数が用意されています。したがって,これらの関数越しにSTArrayやSTUArrayを使うことができます(参考リンク)。
Prelude Control.Monad.ST.Lazy> :t strictToLazyST strictToLazyST :: GHC.ST.ST s a -> ST s a Prelude Control.Monad.ST.Lazy> :t lazyToStrictST lazyToStrictST :: ST s a -> GHC.ST.ST s a
なお,第6回で紹介したStateモナドにも正格モナド版と遅延モナド版が存在します。2008年6月現在,Stateモナドでは遅延モナドがデフォルトとなっているようです。
Prelude Control.Monad.State> runState (undefined >> put 12 >> return 23) 23 (23,12) Prelude Control.Monad.State> :m Control.Monad.State.Strict Prelude Control.Monad.State.Strict> runState (undefined >> put 12 >> return 23) 23 *** Exception: Prelude.undefined