1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
|
{-# LANGUAGE Unsafe #-}
{-# LANGUAGE NoImplicitPrelude, MagicHash, UnboxedTuples, RankNTypes #-}
{-# OPTIONS_HADDOCK hide #-}
-----------------------------------------------------------------------------
-- |
-- 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.
--
-----------------------------------------------------------------------------
module GHC.ST (
ST(..), STret(..), STRep,
fixST, runST, runSTRep,
-- * Unsafe functions
liftST, unsafeInterleaveST
) where
import GHC.Base
import GHC.Show
default ()
-- The state-transformer monad proper. By default the monad is strict;
-- too many people got bitten by space leaks when it was lazy.
-- | The strict state-transformer monad.
-- 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
--
-- * an uninstantiated type variable (inside invocations of 'runST'), or
--
-- * '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'.
--
-- The '>>=' and '>>' operations are strict in the state (though not in
-- values stored in the state). For example,
--
-- @'runST' (writeSTRef _|_ v >>= f) = _|_@
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 Applicative (ST s) where
{-# INLINE pure #-}
{-# INLINE (*>) #-}
pure x = ST (\ s -> (# s, x #))
m *> k = m >>= \ _ -> k
(<*>) = ap
instance Monad (ST s) where
{-# INLINE (>>=) #-}
(>>) = (*>)
(ST m) >>= k
= ST (\ s ->
case (m s) of { (# new_s, r #) ->
case (k r) of { ST k2 ->
(k2 new_s) }})
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
r = case m s of (# _, res #) -> res
in
(# s, r #)
)
-- | Allow the result of a state transformer computation to be used (lazily)
-- inside the computation.
-- Note that if @f@ is strict, @'fixST' f = _|_@.
fixST :: (a -> ST s a) -> ST s a
fixST k = ST $ \ s ->
let ans = liftST (k r) s
STret _ r = ans
in
case ans of STret s' x -> (# s', x #)
instance Show (ST s a) where
showsPrec _ _ = showString "<<ST action>>"
showList = showList__ (showsPrec 0)
{-
Definition of runST
~~~~~~~~~~~~~~~~~~~
SLPJ 95/04: Why @runST@ must not have an unfolding; consider:
\begin{verbatim}
f x =
runST ( \ s -> let
(a, s') = newArray# 100 [] s
(_, s'') = fill_in_array_or_something a x s'
in
freezeArray# a s'' )
\end{verbatim}
If we inline @runST@, we'll get:
\begin{verbatim}
f x = let
(a, s') = newArray# 100 [] realWorld#{-NB-}
(_, s'') = fill_in_array_or_something a x s'
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 ->
let (_, s'') = fill_in_array_or_something a x s' in
freezeArray# a s''
\end{verbatim}
All calls to @f@ will share a {\em single} array! End SLPJ 95/04.
-}
{-# 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.
-- | Return the value computed by a state transformer computation.
-- The @forall@ ensures that the internal state used by the 'ST'
-- computation is inaccessible to the rest of the program.
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
-- That's what the "INLINE [0]" says.
-- SLPJ Apr 99
-- {-# 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 #-}
runSTRep :: (forall s. STRep s a) -> a
runSTRep st_rep = case st_rep realWorld# of
(# _, r #) -> r
|
