What's going on in this type signature? (Vector.Mutable modifiers in Haskell)

Question

Mutable vectors in Haskell have three element-level mutators:

read :: PrimMonad m => MVector (PrimState m) a -> Int -> m a
write :: PrimMonad m => MVector (PrimState m) a -> Int -> a -> m ()
swap :: PrimMonad m => MVector (PrimState m) a -> Int -> Int -> m ()

Now I can use these fine --

import Data.Vector
import Data.Vector.Mutable 
import Control.Monad.ST
import Control.Monad.Primitive 

incrAt :: Vector Double -> Int -> Vector Double
incrAt vec i = runST $ do
  mvec <- thaw vec
  oldval <- read mvec i
  write mvec i (oldval + 1)
  freeze mvec

But what is going on here? What is a PrimMonad? And is PrimState a constructor?

I understand there is some binding going on here, on a PrimMonad class monad. thaw returns m (MVector (PrimState m) a), where m is a PrimMonad... but the monad contains itself? Why is m inside the context of another m?

I see that everything is basically binding on this PrimState or PrimMonad, but I don't see how this has to do with mutable/storable vectors. Is there something special about those typeclasses that allow them to store state?

Thank you for your time!

Answer 1

I think you are using the vector package, as in

import Data.Vector.Mutable

Following the PrimMonad type class leads to low level details; the thing to notice is the two instances:

instance PrimMonad IO where ...
instance PrimMonad (ST s) where ...

So (PrimMonad m) is just a way of saying m is either IO or (ST s). These are the two basic monads in which Haskell is setup to let you mutate memory. To be clear, m is a type constructor and applying m to a type like Int gives a type: m Int.

To emphasize: IO and (ST s) are special because they allow you to "store state" using this ability to mutate the actual memory. They expose this capability in a raw form that the rest of Haskell hides.

Now PrimState is a newish thing: an associated data type. In the PrimMonad type class there is a declaration:

-- | Class of primitive state-transformer monads
class Monad m => PrimMonad m where
  -- | State token type
  type PrimState m

The type that (PrimState m) will be in your code depends on what the instance for (PrimMonad m) assigned to it.

instance PrimMonad IO where
  type PrimState IO = RealWorld

instance PrimMonad (ST s) where
  type PrimState (ST s) = s

The RealWorld type is an low level internal implementation detail of IO in GHC. The s type attached to (ST s) is the existential type trick that lets runST prove that nothing mutable has escaped the (ST s) monad.

To make the same code work in IO and (ST s) the PrimMonad type-class (with associated PrimState) are used to provide ad-hoc overloading.