haskell - 可变性 : directly or via ST Monad

Question

我正在关注斯坦福算法 MOOC 并尝试使用 Haskell 解决问题。许多算法需要大量的数据处理，纯解决方案的运行速度比人们为命令式语言引用的基准要慢得多。所以我觉得我需要使用可变数据结构。

大多数 Haskell 数据结构似乎都有可变的等价物，但有很多关于使用它们的警告。通过 IO Monad 实现这些似乎很容易，但我的印象是“更纯粹”的方法是使用 ST Monad，但在后一种情况下，我只看到提到的数组，其中 runSTArray可用(见下面的代码)。我错过了什么吗？

main = do
    let
        inputData = [1,10,4,3,2]
    print $ elems $ runSTArray $ do
        --newListArray :: (MArray a e m, Ix i) => (i, i) -> [e] -> m (a i e)
        state <- newListArray (1, length inputData) inputData
        qsort state 1 (length inputData)
        return state

qsort :: (STArray s Int Int) -> Int -> Int -> ST s ()
qsort arr min mx =
    if mx - min < 1 then
        return ()

    else do
        p <- readArray arr min
        final_i <- foldM (partitioner p) (min+1) [(min+1)..mx]
        swap min $ final_i - 1
        qsort arr min     (final_i-2)
        qsort arr final_i mx     

    where
        swap i j = do
            arr_i <- readArray arr i
            arr_j <- readArray arr j
            writeArray arr i arr_j
            writeArray arr j arr_i

        partitioner p i idx = do
            arr_idx <- readArray arr idx
            if arr_idx > p then
                return i
            else do
                swap i idx
                return $ i+1

具体来说，上述和以下之间的有效区别是什么:

main = do
    [snip]
    arr <- newListArray (0, length inputData - 1) inputData :: IO (IOArray Int Int)
    qsort arr 0 (length inputData - 1)
    printArray arr

qsort :: (IOArray Int Int) -> Int -> Int -> IO ()
[As above]

再想一想:这个问题不就是 ST 和 IO Monad 之间的区别吗，外行的答案是 ST 更“安全”？

Answer 1

是的，您缺少模块 Data.STRef .您可以使用 newSTRef 创建可变变量, 使用 writeSTRef 存储变量并使用 readSTRef 获取.