[Haskell-cafe] Fun with the ST monad

Andrew Coppin andrewcoppin at btinternet.com
Thu Feb 24 21:45:59 CET 2011


OK, so I had a function that looks like

   transform :: [Word8] -> [Word16]

It works nicely, but I'd like to use mutable state inside. No problem! 
Use the ST monad. Something like

   transform :: [Word8] -> [Word16]
   transform xs = runST (work xs)
     where
       work :: [Word8] -> ST s [Word16]

Ah, yes, well there is one *small* problem... If you do that, the 
function becomes too strict.

The input list is being read from disk by lazy I/O. With the original 
implementation, the input file gets read at the same time as the output 
file is written. But runST returns nothing until the *entire* input has 
been compressed. So writing to disk doesn't start until the entire file 
has been slurped up into memory.

Anybody have any hints on how to get around this?

My first thought was to break the ST computation into several seperate 
pieces. But, /by design/, you cannot do this. And here's why:

   main = do
     let r = runST $ newSTRef 0
     let x = runST $ n <- readSTRef r; writeSTRef r (n+1); return n
     let y = runST $ n <- readSTRef r; writeSTRef r (n*2); return n
     print x
     print y

Now what the hell does this print out? Because it appears, logically, 
that it ought to vary depending on the order in which x and y are 
accessed - a clear violation of referential integrity.

Fortunately of course, by a clever dodge, this code doesn't actually 
type-check. That's great, because it has undefined semantics. But it's 
also a problem, since it's exactly the sort of thing I'd like to do.

Come to think of it, how the heck does lazy I/O manage this trick? How 
come accessing the elements of the list in the wrong order doesn't cause 
the wrong data to end up in each cell, if each cell is just using 
unsafePerformIO to read the next byte from a normal file handle?



More information about the Haskell-Cafe mailing list