Haskell parallel computation using an STArray

Question

I'm trying to do computation in parallel, and write the results to an STArray. I think this code shows what I'm trying to do. However, I'm getting compile errors.

import Control.Monad
import Control.Monad.ST
import Control.Parallel
import Data.Array.ST

main = do
    arr <- newArray ((0,0), (5,5)) 0 :: ST s (STArray s (Int, Int) Int)
    runSTArray $ do
        par (writeArray arr (1,1) 17) (writeArray arr (2,2) 23)
        return arr
    print arr

How should I do this?

Answer 1

You use newArray, which has the type ST s (STArray s (Int, Int) Int). However, you use it in the body of the main function, which means that everything you do must have an IO type. ST is not IO, so the types cannot match.

You should first move the newArray into a context where you have access to the ST monad. This context is of course available in the body of runSTArray, so change the body to:

    runSTArray $ do
        arr <- newArray ((0,0), (5,5)) 0 :: ST s (STArray s (Int, Int) Int)
        par (writeArray arr (1,1) 17) (writeArray arr (2,2) 23)
        return arr

Then, you need to rethink how par behaves. par is for creating parallel pure computations, and cannot be used for monadic actions; monads cannot generally be parallelized at all. In particular, the ST monad doesn't even offer any alternatives for parallel computations; since parallel writes to an array can lead to race conditions (what happens if you overwrite the same cell? Which write will count, and which one won't?), it is unsafe to allow parallelism here. You must change the array in sequence:

    runSTArray $ do
        arr <- newArray ((0,0), (5,5)) 0 :: ST s (STArray s (Int, Int) Int)
        writeArray arr (1,1) 17
        writeArray arr (2,2) 23
        return arr

However, the writes aren't expensive; it's the calculations of the values that might be expensive. Suppose that you want to calculate 17 and 23 on the fly; you can then do the following:

let a = someLongCalculation 12534
    b = a `par` (someLongCalculation 24889)
writeArray arr (1, 1) a
writeArray arr (2, 2) b

Finally, you must realize that runSTArray returns the result array, so you must store it like this:

import Control.Monad
import Control.Monad.ST
import Control.Parallel
import Data.Array.ST

main =
  let pureArr =
        runSTArray $ do
          arr <- newArray ((0,0), (5,5)) 0 :: ST s (STArray s (Int, Int) Int)
          writeArray arr (1,1) 17
          writeArray arr (2,2) 23
          return arr
  in print pureArr

I don't think that STArrays are the correct solution here. You should use a more powerful array library like repa in situations where you need parallel symmetrical array computations.