使用STArray的Haskell并行计算

Question

我正在尝试并行执行计算,并将结果写入STArray.我认为这段代码显示了我正在尝试做的事情.但是,我收到了编译错误.

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

我该怎么做？

Answer 1

你使用newArray,有类型ST s (STArray s (Int, Int) Int).但是,您在main函数体中使用它,这意味着您do必须具有IO类型的所有内容.ST不是IO,所以类型不匹配.

您应该首先newArray进入您可以访问STmonad 的上下文.这个背景当然可以在身体中使用runSTArray,所以将身体改为:

    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

然后,您需要重新思考par行为方式.par用于创建并行纯计算,不能用于monadic动作; monad一般不能并行化.特别是,STmonad甚至没有为并行计算提供任何替代方案; 因为并行写入数组会导致竞争条件(如果你覆盖同一个单元会发生什么？哪个写入会计数,哪个不会？),这里允许并行是不安全的.您必须按顺序更改数组:

    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

但是,写入并不昂贵; 这是可能很昂贵的价值计算.假设你要计算17和23对飞; 然后你可以做以下事情:

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

最后,你必须意识到runSTArray返回结果数组,所以你必须像这样存储它:

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

我不认为这STArray是正确的解决方案.您应该使用更强大的数组库,例如repa需要并行对称数组计算的情况.