Haskell 中如何实现可变数组? [英] How are mutable arrays implemented in Haskell?

问题描述

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

I've read many research papers on this topic, and they usually argue that arrays are implemented using Monads. But none of these papers gave a clear definition of how the "type" Array itself should be defined, they only gave definitions for the functions using monads to access or modify this type. How are arrays, having O(1) time to access or modify an indexed element, implemented in Haskell ?! (such as STUArray and MArray)

推荐答案

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

How are arrays, having O(1) time to access or modify an indexed element, implemented in Haskell

它们是通过运行时系统中的原始操作实现的，用于内存读取和写入.

They are implemented via primitive operations in the runtime system for memory reads and writes.

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

The safety of the side effecting action of destructively writing to memory is ensured via the use of monads to linearize access to the mutable state.

查看用于 Haskell 数组的 primitive 包(在 IO 或 ST)，你可以看到实现是根据 GHC 的primops:

Looking at the primitive package for Haskell arrays (in IO or ST), you can see that the implementations is in terms of GHC's 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#
• 读取数组#
• writeArray#

它们是用于操作语言运行时提供的内存的原始(硬件加速；)服务.

which are primitive (hardware accelerated ;) services for operating on memory provided by the language runtime.

为破坏性记忆效应提供类型安全的机制是由 Launchbury 和 Peyton-Jones 的论文 Lazy Functional State Threads，它引入了 ST monad 和可变数组的原语.

Mechanisms for giving type safety to destructive memory effects were introduced to Haskell by the Launchbury and Peyton-Jones paper, Lazy Functional State Threads, which introduces the ST monad and primitives for mutable arrays.

这篇关于Haskell 中如何实现可变数组?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！