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

Question

我已经阅读了很多关于这个主题的研究论文,他们通常认为数组是使用Monads实现的.但是这些论文都没有明确定义如何定义"类型"数组本身,它们只给出了使用monads访问或修改此类型的函数的定义.在Haskell中实现的数组如何有O(1)时间来访问或修改索引元素？(例如STUArray和MArray)

Answer 1

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

它们通过运行时系统中的原始操作实现,用于存储器读写.

通过使用monad来线性化对可变状态的访问,确保了破坏性地写入存储器的副作用的安全性.

primitive查看Haskell数组的包(在IO或中ST),您可以看到实现是根据GHC的初衷:

-- | 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向Haskell介绍了为破坏性记忆效应提供类型安全的机制,该论文介绍了ST可变阵列的monad和primitives.

Answer 2

它们的实现方式与命令式语言相同; 即就地更新.类型系统将保证您不能对它们做任何"坏事".

Answer 3

作为一个例外,请记住,"可以对各种控制结构进行"使用monads实现"与"对opaque类型的monadic操作隔离的副作用"不同,与IOor一样ST, monad的属性只是确保纯代码保持不变.

Don Stewart解释说,可变数据作为运行时原语提供; 这里唯一"用monads实现"的是类型安全.