How do I make a new data type, based on a vector, within the ST monad

Question

Closely related to my most recent question on handling large data blocks, I have reached the point in which I need to take a large immutable data block, make it mutable for some operations, and then make it immutable again when I am done.

Since I want to retain at least the appearance of purity, the mutable data will be a mutable copy of the original immutable data. For reference, I'm looking at the Bloom Filter example in Real World Haskell, but finding that I cannot actually make my code run in runST.

My data structures, first the pure one, then the impure:

import Data.Vector.Unboxed (Vector)
import Data.Vector.Unboxed.Mutable (MVector)

data PixelMap = Bitmap Int Int (Vector Bool)
data MPixelMap s = MBitmap Int Int (MVector s Bool)

And then I create just a basic newBitmapM function:

newBitmapM :: (Int, Int) -> ST s (MPixelMap s)
newBitmapM (width, height) = MBitmap width height `liftM` MV.replicate (width * height) False

This loads into GHCI just fine, but then I try to run it:

> runST $ newBitmapM (15, 15)

<interactive>:78:9:
    Couldn't match type `a' with `PixelMapMutable s'
      `a' is a rigid type variable bound by
          the inferred type of it :: a at <interactive>:78:1
    Expected type: ST s a
      Actual type: ST s (PixelMapMutable s)
    In the return type of a call of `newBitmapM'
    In the second argument of `($)', namely `newBitmapM (15, 15)'
    In the expression: runST $ newBitmapM (15, 15)

This error message makes no sense to me at all. a, defined in the type for runST should be polymorphic, and thus not at all "fixed". Can anyone decode this enough to tell me what is really wrong with the code?

Answer 1

The full type signature of runST is forall a. (forall s. ST s a) -> a. In forall s. ST s a all occurrences of the s parameter are quantified by forall s, including the s in your MPixelMap s, in the specific example you provided. In fact, all Haskell type parameters must be introduced somewhere by quantification, it's just that most of the time it's left implicit, like the a in the type of runST. The scope of the s param here in restricted to only ST s a. It doesn't make sense for the a param returned by runST to contain an s parameter, because there is no such s parameter in scope anymore!

In practice, this means that you cannot extract anything with runST that depends on the inner state parameter. This is the actually a core safety feature of the ST monad. A function is pure if it's independent from some state. The type quantification trick ensures that runST appears pure to the outside world.

You can make your example code work if you eliminate the s from the returned type. In the case of mutable vectors freeze and unsafeFreeze does exactly that. You can freeze your bitmaps by freezing their state-dependent fields:

freezeMPixelMap :: MPixelMap s -> ST s PixelMap
freezeMPixelMap (MBitmap width height vec) = 
    Bitmap width height `liftM` V.freeze vec

Then you can extract a PixelMap any time using runST.

Of course, you can use the unsafe versions of freeze and thaw to convert between immutable/mutable vectors without copying. It is usually quite easy to ascertain that unsafeFreeze does nothing nasty; you just have to make sure you don't use the mutable vector anymore in the ST action. unsafeThaw can be trickier, since you have to make sure that your whole program has no reference to your immutable vector, so it makes sense to only unsafeThaw vectors that live in a small local scope.