Personal tools

Merging ST threads

From HaskellWiki

(Difference between revisions)
Jump to: navigation, search
m (edit formatting of signature)
Current revision (21:14, 18 May 2007) (edit) (undo)
m (typo)
 
(3 intermediate revisions not shown.)
Line 49: Line 49:
</haskell>
</haskell>
-
Of course, we won't be able to run values of type <hask>ST (s,t) a</hask>, since they violate the <hask>forall}}} restriction on <hask>runST</hask>. So we need some way to get rid of the tuple:
+
Of course, we won't be able to run values of type <hask>ST (s,t) a</hask>, since they violate the <hask>forall</hask> restriction on <hask>runST</hask>. So we need some way to get rid of the tuple:
<haskell>
<haskell>
Line 58: Line 58:
Does this make sense? Is it safe? I doubt it's very useful, but I think it's probably implementable with a bit of hacking inside the implementation of ST.
Does this make sense? Is it safe? I doubt it's very useful, but I think it's probably implementable with a bit of hacking inside the implementation of ST.
-- GaneshSittampalam
-- GaneshSittampalam
 +
 +
[[Category:Code]]

Current revision

In the thread starting at http://www.haskell.org//pipermail/haskell/2004-January/013330.html there is a discussion about temporarily combining two independent monadic state threads. The problem is this: we have a computation that works with one bit of state, say a
Bool
, and another that works with another bit of state, say an
Int
, and we want to make one that works with both the
Bool
and the
Int
simultaneously for a while, and then go back to computations working on them individually. So what we want is, given
start1
and
start2
computations that work with the
Bool
and the
Int
respectively, an
intermediate
computation that works with the pair
(Bool,Int)
, and then computations
end1
and
end2
that work with the individual states, to construct the combined computation that does
start1
and
start2
, then
intermediate
, then
end1
and
end2
.

One solution is to define the individual computations using the StateT monad transformer, and then stack the two monad transformers on top of each other to make the combined one. This is a bit nasty and asymmetric, requiring one computation to be "lifted": 

whole
    = do
        start1
        lift start2
        intermediate
        end1
        lift end2

Another option is to work with the normal State monad, and to define operations on this monad that "lifts" the state into a tuple: 

embedState1 :: State s a -> State (s,t) a
embedState2 :: State t a -> State (s,t) a
 
embedState1 (State f) = State (\(s,t) -> let (s',a)=f s in ((s',t),a))
embedState2 (State f) = State (\(s,t) -> let (t',a)=f s in ((s,t'),a))
 
whole
    = do
         embedState1 start1
         embedState2 start2
         intermediate
         embedState1 end1
         embedState2 end2
This removes the asymmetry, but isn't really any nicer otherwise. However, what would be neat is if we could do this with ST threads too. ST is the extension present in at least GHC and Hugs that has an imperative implementation, and makes clever use of a
forall
in a type to guarantee purity.

The key point is the operation 

runST :: (forall s . ST s a) -> a
Which guarantees that state variables (
STRef
etc) cannot "escape" from one state thread to another.

If we want to do the above with then ST, then we probably want operations like this: 

embedST1 :: ST s a -> ST (s,t) a
embedST2 :: ST t a -> ST (s,t) a
Of course, we won't be able to run values of type
ST (s,t) a
, since they violate the
forall
restriction on
runST
. So we need some way to get rid of the tuple: 
finishST1 :: (forall s . ST (s,t) a) -> ST t a
finishST2 :: (forall t . ST (s,t) a) -> ST s a

Does this make sense? Is it safe? I doubt it's very useful, but I think it's probably implementable with a bit of hacking inside the implementation of ST. 

 -- GaneshSittampalam
Retrieved from "http://www.haskell.org/haskellwiki/Merging_ST_threads"

Category: Code