How to use Unboxed Mutable vector

Question

import           Control.Monad.ST
import           Data.STRef

import qualified Data.Vector.Unboxed         as V
import qualified Data.Vector.Unboxed.Mutable as MV

-- what the heck is that s?
new0 :: (MV.Unbox a, Num a) => ST s (MV.STVector s a)
new0 = do
  v <- MV.new 10
  MV.write v 1 10
  MV.write v 2 10
  return v

new1 :: (MV.Unbox a) => IO (MV.IOVector a)
new1 = MV.new 10

new2 :: (MV.Unbox a, Num a) => IO (MV.STVector RealWorld a)
new2 = do
  v <- MV.new 10
  MV.write v 1 10
  return v

I'm implementing the QuickSort algorithm and I choose Data.Vector.Unboxed.Mutable

I'm completely lost regarding two issues:

• How to choose the right Monad: IO or ST
• How to get the value out of ST. Could anyone show me how to print new0 ?

Solutions:

I got some inspirations from this example code

For a good understanding of ST monad, check the original paper: Lazy Functional State Threads

Here's a code snippet showing how to use mutable vectors for quicksort:

import           Control.Monad.Primitive
import           Control.Monad.ST            (runST)
import           Prelude                     hiding (read)

import           Data.List                   (partition)
import qualified Data.Vector.Unboxed         as V
import qualified Data.Vector.Unboxed.Mutable as M

partitionV :: (PrimMonad m, Ord a, V.Unbox a) 
           => M.MVector (PrimState m) a -> Int -> Int -> m Int
partitionV v p r = do
  let i = p
  x <- M.unsafeRead v r
  go i p x
  where
    go i j x | j < r = do
               jv <- M.unsafeRead v j
               if jv < x
                 then M.unsafeSwap v i j >> go (i+1) (j+1) x
                 else go i (j+1) x
    go i _ _ = do
      M.unsafeSwap v i r
      return i

quickSortV :: (PrimMonad m, Ord a, V.Unbox a) 
           => M.MVector (PrimState m) a -> m ()
quickSortV v | M.length v < 2 = return ()
quickSortV v = do
  i <- partitionV v 0 (M.length v - 1)
  quickSortV (M.unsafeSlice 0 i v)
  quickSortV (M.unsafeSlice (i + 1) (M.length v - 1 - i) v)
    -- note the difference between for loop and recursive call

test l = runST $ do
  mv <- V.thaw l
  quickSortV mv
  V.freeze mv

quickSort :: (Ord a) => [a] -> [a]
quickSort []       = []
quickSort (x : xs) =
    let (lt, gt) = partition (<= x) xs
    in  quickSort lt ++ [x] ++ quickSort gt

Answer 1

The ST monad is for when you want to take some immutable data, make it temporarily mutable, do something with it, and make it immutable again. In particular, there is no way to return a mutable result from the ST monad (by design).

In particular, STVector is mutable, so it can never leave the ST monad. So there is no way to "print out" new0. You would have to convert it to something immutable to return it out of the ST monad.

If you're wanting to mutate something, print it out, mutate it a bit more, print it out, etc., you probably want the IO monad. The ST monad is for making something temporarily mutable, to eventually produce an ordinary immeduate result.

Regarding the s type variable: It's a slight hack that enforces the property that mutable data cannot leave ST. The runST function requires an action that works for every possible choice of s. This means it's impossible to return anything that contains s. Since all the mutable stuff has s in its type signature, this enforces our guarantee.