Haskell 中如何实现可变数组？

Question

我读过很多关于这个主题的研究论文，他们通常认为数组是使用 Monad 实现的。但这些论文都没有给出“类型”数组本身应该如何定义的明确定义，它们只给出了使用 monad 访问或修改此类型的函数的定义。 在 Haskell 中如何实现具有 O(1) 时间来访问或修改索引元素的数组？！ （例如 STUArray 和 MArray）

Answer 1

在 Haskell 中如何实现具有 O(1) 时间访问或修改索引元素的数组

它们是通过运行时系统中用于内存读写的原始操作来实现的。

通过使用 monad 线性化对可变状态的访问，可以确保破坏性写入内存的副作用操作的安全性。

查看 Haskell 数组的 primitive 包（在 IO 或 ST），您可以看到实现是根据 GHC 的 primops：

-- | Create a new mutable array of the specified size and initialise all
-- elements with the given value.
newArray :: PrimMonad m => Int -> a -> m (MutableArray (PrimState m) a)
newArray (I# n#) x = primitive
   (\s# -> case newArray# n# x s# of
             (# s'#, arr# #) -> (# s'#, MutableArray arr# #))

-- | Read a value from the array at the given index.
readArray :: PrimMonad m => MutableArray (PrimState m) a -> Int -> m a
readArray (MutableArray arr#) (I# i#) = primitive (readArray# arr# i#)

-- | Write a value to the array at the given index.
writeArray :: PrimMonad m => MutableArray (PrimState m) a -> Int -> a -> m ()
writeArray (MutableArray arr#) (I# i#) x = primitive_ (writeArray# arr# i# x)

也就是说，

• newArray#
• readArray#
• writeArray#

是用于在语言提供的内存上进行操作的原始（硬件加速；）服务运行时。

Launchbury 和 Peyton-Jones 的论文 惰性功能状态线程，它引入了 ST monad 和可变数组的原语。

Answer 2

顺便说一句，请记住，“使用 monad 实现”（可以对各种控制结构执行）与“通过不透明类型上的一元操作隔离的副作用”实际上并不相同，如 IO 或 ST，其中 monad 的属性仅确保纯代码保持不变。

正如 Don Stewart 所解释的那样，可变数据作为运行时原语提供；这里唯一“用 monad 实现”的是类型安全。

Answer 3

它们的实现方式与命令式语言相同；即就地更新。类型系统将保证你不能用它们做任何“坏”的事情。