ST.lhs 5.17 KB
 simonmar committed Jun 28, 2001 1 \begin{code}  dterei committed Oct 25, 2011 2 {-# LANGUAGE Unsafe #-}  Simon Peyton Jones committed Oct 31, 2012 3 {-# LANGUAGE NoImplicitPrelude, MagicHash, UnboxedTuples, RankNTypes #-}  Ross Paterson committed Jan 20, 2008 4 {-# OPTIONS_HADDOCK hide #-}  simonmar committed Apr 26, 2002 5 6 7 8 9 10 11 12 13 14 15 16 17 ----------------------------------------------------------------------------- -- | -- Module : GHC.ST -- Copyright : (c) The University of Glasgow, 1992-2002 -- License : see libraries/base/LICENSE -- -- Maintainer : cvs-ghc@haskell.org -- Stability : internal -- Portability : non-portable (GHC Extensions) -- -- The 'ST' Monad. -- -----------------------------------------------------------------------------  simonmar committed Jun 28, 2001 18   ross committed Feb 03, 2005 19 -- #hide  dterei committed Jun 18, 2011 20 21 22 23 24 25 26 module GHC.ST ( ST(..), STret(..), STRep, fixST, runST, runSTRep, -- * Unsafe functions liftST, unsafeInterleaveST ) where  simonmar committed Jun 28, 2001 27 28 29 30 31 32 33 34  import GHC.Base import GHC.Show default () \end{code} %*********************************************************  Don Stewart committed Mar 05, 2008 35 %* *  simonmar committed Jun 28, 2001 36 \subsection{The @ST@ monad}  Don Stewart committed Mar 05, 2008 37 %* *  simonmar committed Jun 28, 2001 38 39 40 41 42 43 %********************************************************* The state-transformer monad proper. By default the monad is strict; too many people got bitten by space leaks when it was lazy. \begin{code}  ross committed Sep 05, 2003 44 -- | The strict state-transformer monad.  ross committed Sep 08, 2003 45 46 47 48 -- A computation of type @'ST' s a@ transforms an internal state indexed -- by @s@, and returns a value of type @a@. -- The @s@ parameter is either --  dons committed Sep 18, 2005 49 -- * an uninstantiated type variable (inside invocations of 'runST'), or  ross committed Sep 08, 2003 50 51 52 53 54 55 -- -- * 'RealWorld' (inside invocations of 'Control.Monad.ST.stToIO'). -- -- It serves to keep the internal states of different invocations -- of 'runST' separate from each other and from invocations of -- 'Control.Monad.ST.stToIO'.  ross committed Oct 13, 2005 56 57 58 59 60 -- -- The '>>=' and '>>' operations are strict in the state (though not in -- values stored in the state). For example, -- -- @'runST' (writeSTRef _|_ v >>= f) = _|_@  simonmar committed Jun 28, 2001 61 62 63 64 65 66 67 68 69 70 71 72 newtype ST s a = ST (STRep s a) type STRep s a = State# s -> (# State# s, a #) instance Functor (ST s) where fmap f (ST m) = ST $\ s -> case (m s) of { (# new_s, r #) -> (# new_s, f r #) } instance Monad (ST s) where {-# INLINE return #-} {-# INLINE (>>) #-} {-# INLINE (>>=) #-}  simonpj committed Feb 17, 2003 73 74  return x = ST (\ s -> (# s, x #)) m >> k = m >>= \ _ -> k  simonmar committed Jun 28, 2001 75 76  (ST m) >>= k  simonpj committed Feb 17, 2003 77  = ST (\ s ->  Don Stewart committed Mar 05, 2008 78 79 80  case (m s) of { (# new_s, r #) -> case (k r) of { ST k2 -> (k2 new_s) }})  simonmar committed Jun 28, 2001 81 82 83 84 85 86 87 88 89 90 91 92  data STret s a = STret (State# s) a -- liftST is useful when we want a lifted result from an ST computation. See -- fixST below. liftST :: ST s a -> State# s -> STret s a liftST (ST m) = \s -> case m s of (# s', r #) -> STret s' r {-# NOINLINE unsafeInterleaveST #-} unsafeInterleaveST :: ST s a -> ST s a unsafeInterleaveST (ST m) = ST ( \ s -> let  Don Stewart committed Mar 05, 2008 93  r = case m s of (# _, res #) -> res  simonmar committed Jun 28, 2001 94 95 96 97  in (# s, r #) )  ross committed Sep 05, 2003 98 99 -- | Allow the result of a state transformer computation to be used (lazily) -- inside the computation.  ross committed Sep 08, 2003 100 -- Note that if @f@ is strict, @'fixST' f = _|_@.  simonmar committed Jun 28, 2001 101 102 103 fixST :: (a -> ST s a) -> ST s a fixST k = ST$ \ s -> let ans = liftST (k r) s  Don Stewart committed Mar 05, 2008 104  STret _ r = ans  simonmar committed Jun 28, 2001 105 106 107 108 109  in case ans of STret s' x -> (# s', x #) instance Show (ST s a) where showsPrec _ _ = showString "<>"  Don Stewart committed Mar 05, 2008 110  showList = showList__ (showsPrec 0)  simonmar committed Jun 28, 2001 111 112 113 114 115 116 117 118 119 \end{code} Definition of runST ~~~~~~~~~~~~~~~~~~~ SLPJ 95/04: Why @runST@ must not have an unfolding; consider: \begin{verbatim} f x = runST ( \ s -> let  Don Stewart committed Mar 05, 2008 120 121 122 123  (a, s') = newArray# 100 [] s (_, s'') = fill_in_array_or_something a x s' in freezeArray# a s'' )  simonmar committed Jun 28, 2001 124 125 126 127 \end{verbatim} If we inline @runST@, we'll get: \begin{verbatim} f x = let  Don Stewart committed Mar 05, 2008 128 129  (a, s') = newArray# 100 [] realWorld#{-NB-} (_, s'') = fill_in_array_or_something a x s'  simonmar committed Jun 28, 2001 130 131 132 133 134 135 136 137 138 139  in freezeArray# a s'' \end{verbatim} And now the @newArray#@ binding can be floated to become a CAF, which is totally and utterly wrong: \begin{verbatim} f = let (a, s') = newArray# 100 [] realWorld#{-NB-} -- YIKES!!! in \ x ->  Don Stewart committed Mar 05, 2008 140 141  let (_, s'') = fill_in_array_or_something a x s' in freezeArray# a s''  simonmar committed Jun 28, 2001 142 143 144 145 146 147 148 149 \end{verbatim} All calls to @f@ will share a {\em single} array! End SLPJ 95/04. \begin{code} {-# INLINE runST #-} -- The INLINE prevents runSTRep getting inlined in *this* module -- so that it is still visible when runST is inlined in an importing -- module. Regrettably delicate. runST is behaving like a wrapper.  ross committed Sep 05, 2003 150 151  -- | Return the value computed by a state transformer computation.  ross committed Sep 08, 2003 152 153 -- The @forall@ ensures that the internal state used by the 'ST' -- computation is inaccessible to the rest of the program.  simonmar committed Jun 28, 2001 154 155 156 157 runST :: (forall s. ST s a) -> a runST st = runSTRep (case st of { ST st_rep -> st_rep }) -- I'm only letting runSTRep be inlined right at the end, in particular *after* full laziness  simonmar committed Dec 21, 2001 158 -- That's what the "INLINE [0]" says.  Don Stewart committed Mar 05, 2008 159 -- SLPJ Apr 99  simonmar committed May 04, 2005 160 161 162 163 164 165 166 167 -- {-# INLINE [0] runSTRep #-} -- SDM: further to the above, inline phase 0 is run *before* -- full-laziness at the moment, which means that the above comment is -- invalid. Inlining runSTRep doesn't make a huge amount of -- difference, anyway. Hence: {-# NOINLINE runSTRep #-}  simonmar committed Jun 28, 2001 168 169 runSTRep :: (forall s. STRep s a) -> a runSTRep st_rep = case st_rep realWorld# of  Don Stewart committed Mar 05, 2008 170  (# _, r #) -> r  simonmar committed Jun 28, 2001 171 \end{code}