CODEWITHSUNDEEP
haskellgenericsvector
MaiaVictor
MaiaVictor

Reputation: 53077

How to create a type that wraps around mutable vectors?

I'm trying to create a type, a 2D Matrix, that wraps around mutable vectors. I want a few operations such as set, get. The problem is that I have absolutely no idea on how to get the types for it to work. I've tried several things, but I'm really just shooting on the dark because there is absolutely no explanation nowhere on how to do this. See:

data Matrix v s a = Matrix { size :: (Int,Int), buffer :: v s a } -- ?? Wrong
newMatrix = ??
set (x,y) mat = ??
get (x,y) val mat = ??

Take, for example, the official documentation. Where is the constructor? What does v and a in class MVector v a where mean? What the heck is m (v (PrimState m) a)? Is that the "type" of a generic mutable vector? What is m and v? What even is PrimState?

Upvotes: 2

Views: 220

Answers (1)

Cactus
Cactus

Reputation: 27636

As @user2407038 noted, it is easier to restrict yourself at first to a concrete MVector type like IOVector. If you specialize the type of new, read and write to IOVector, you get the following, distinctively non-intimidating types:

new   :: Int -> IO (IOVector a)
read  :: IOVector a -> Int -> IO a
write :: IOVector a -> Int -> a -> IO ()

So for the first version, the implementation of your Matrix operations are straightforward:

import Data.Vector.Mutable as V
import Control.Monad (liftM)

data Matrix a = Matrix { size :: (Int, Int), buffer :: IOVector a }

newMatrix :: (Int, Int) -> IO (Matrix a)
newMatrix (w, h) = liftM (Matrix (w, h)) $ V.new (w * h)

set :: (Int, Int) -> a -> Matrix a -> IO ()
set pos e mtx = V.write (buffer mtx) (offset mtx pos) e

get :: (Int, Int) -> Matrix a -> IO a
get pos mtx = V.read (buffer mtx) (offset mtx pos)

offset :: Matrix a -> (Int, Int) -> Int
offset (Matrix (w, _h) _) (x, y) = w * y + x

So then, how do we generalize over the choice of s in MVector s? Matrix itself needs to be generalized over the choice of s:

data Matrix s a = Matrix { size :: (Int, Int), buffer :: MVector s a }

And we also need to thread this generalization through to all the functions. Let's look at newMatrix in detail; the rest can be left as an exercise for the reader.

If we just abstract on s, newMatrix becomes

newMatrix :: (Int, Int) -> IO (Matrix s a)
newMatrix (w, h) = liftM (Matrix (w, h)) $ V.new (w * h) -- Same implementation as above

However, surely this can't be right -- we can't create MVector s a in IO for any choice of s, only RealWorld! Expectedly, the typechecker catches this:

Couldn't match type `s' with `RealWorld'
  `s' is a rigid type variable bound by
      the type signature for newMatrix :: (Int, Int) -> IO (Matrix s a)
Expected type: s
  Actual type: PrimState IO
Expected type: IO (MVector s a)
  Actual type: IO (MVector (PrimState IO) a)
In the return type of a call of `new'
In the second argument of `($)', namely `new (w * h)'

But suppose we wrote

newMatrix :: (Monad m) => (Int, Int) -> m (Matrix s a)

This is, in some sense, even worse: now we are saying that for any choice of m and s (independent of each other!), we can construct a Matrix s a in m. Clearly this is not the case.

This is where the PrimMonad typeclass is needed: it provides the linkage between PrimState m, the choice of s for the vector being manipulated, and the monad m where this manipulation is possible. newMatrix thus becomes

newMatrix :: (PrimMonad m) => (Int, Int) -> m (Matrix (PrimState m) a)
newMatrix (w, h) = liftM (Matrix (w, h)) $ V.new (w * h) -- implementation is still the same!

The other operations can be typed in an analogous way.

Upvotes: 3

Related Questions