可变数组是如何在Haskell中实现的？

Question

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

Answer 1

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

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

通过使用单体来线性化对可变状态的访问，确保了破坏性写入存储器的副作用动作的安全性。

查看Haskell数组的primitive包(在IO或ST中)，您可以看到实现是以GHC's 为单位的

-- | 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单数和原语。

Answer 2

顺便说一句，请记住，“使用monad实现”，就像可以对各种控制结构所做的那样，与“通过不透明类型上的一元操作隔离的副作用”并不是一回事，因为在IO或ST中，monad的属性只是确保纯代码保持不变。

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

Answer 3

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