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

Question

我已经阅读了许多关于这个主题的研究论文，它们通常认为数组是使用单子实现的。但是这些论文中没有一个清晰地定义了“类型”数组本身应该如何定义，他们只给出了使用单子来访问或修改此类型的函数的定义。

在Haskell中，具有O(1)时间访问或修改索引元素的数组是如何实现的？（例如STUArray和MArray）

- is7s

---

通常它们是通过调用外部库或运行时支持来实现的。 - luqui

我想知道“数组是使用Monad实现的”可能意味着什么...听起来就像“面包是用表格烤出来的”。 - Alexey

@Alexey，“implemented”在英语中的意思是“实施”。因此，说Haskell中数组的可变性是使用单子（Monads）实现（“实施”或“实现”）并没有错。使用无限流也可以达到相同的结果，但这要不太直观。 - is7s

Answer 1

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

它们是通过运行时系统中的原始操作来实现内存读写的。使用单子来线性化对可变状态的访问，以确保破坏性写入内存的副作用操作的安全性。

查看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的论文Lazy Functional State Threads引入了赋值式内存效果的类型安全机制，该论文介绍了ST单子和可变数组的原语。

- Don Stewart

Answer 2

作为一个旁注，请记住，“使用单子实现”，对于各种控制结构来说，并不真正意味着“通过单子操作在不透明类型上隔离副作用”，比如IO或ST，其中单子的属性仅确保纯代码仍然保持纯净。可变数据作为运行时原语提供，就像Don Stewart所解释的那样；这里唯一“使用单子实现”的是类型安全性。

- C. A. McCann

---

类型安全的封装和排序（自动线程化的s参数，给出了效果的依赖顺序）。 - Don Stewart

@Don：啊，是的，我想我认为那部分显而易见，但你说得对，我应该更明确一些。 - C. A. McCann

Answer 3

它们的实现方式与命令式语言相同，即就地更新。类型系统将保证您不会对它们做任何“坏事”。

- augustss