arrays - 使用 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 函数的主体中使用它，这意味着您所做的一切 都必须具有 IO 类型。 ST 不是IO，所以类型不能匹配。

您应该首先将 newArray 移动到您有权访问 ST monad 的上下文中。这个上下文当然在 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 用于创建并行纯 计算，不能用于单子(monad)操作； monads 通常根本不能并行化。特别是，ST monad 甚至没有为并行计算提供任何替代方案；因为对数组的并行写入会导致竞争条件(如果覆盖同一个单元格会发生什么？哪个写入有效，哪个无效？)，因此在此处允许并行是不安全的。您必须按顺序更改数组:

    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在需要并行对称数组计算的情况下。