如何可变数组在Haskell实施？ [英] How are mutable arrays implemented in Haskell?

问题描述

我读过关于这一主题的许多研究论文，他们通常认为的阵列是利用单子执行。但是这些论文给了如何类型阵列本身应该被定义，他们只给了使用单子访问或修改这种类型的功能定义一个明确的定义。
如何是数组，有O（1）时间访问或修改索引的元素，在Haskell实现的？！ （如STUArray和MARRAY）

解决方案

  

如何是数组，有O（1）时间访问或修改索引的元素，在Haskell实施

它们通过基本操作来实现在运行系统内存的读取和写入。

侧面破坏性影响写入存储器的动作的安全性是通过使用单子的保证，以线性访问可变状态。

在

看原始 包哈斯克尔阵列（在 IO 或 ST ），你可以看到，实现在的GHC's的 primops 的：

   -  |创建指定大小的新的可变数组并初始化所有
 - 元素与给定值。
newArray :: PrimMonad M =＆GT; INT  - ＆GT;一个 - ＆GT; M（MutableArray（PrimState米））
newArray（I＃N＃）X =原始
   （\\ S＃ - ＆GT;的情况下newArray＃N＃个S的＃
             （＃S'＃，编曲##） -  GT; （＃S'＃，MutableArray ARR ##）） -  |阅读从给定索引处的数组值。
readArray :: PrimMonad M =＆GT; MutableArray（PrimState米） - ＆GT; INT  - ＆GT;嘛
readArray（ARR MutableArray＃）（I＃I＃）=原语（readArray＃＃改编I＃） -  |写一个值给定索引处的数组。
writeArray :: PrimMonad M =＆GT; MutableArray（PrimState米） - ＆GT; INT  - ＆GT;一个 - ＆GT; M（）
writeArray（ARR MutableArray＃）（I＃I＃）X = primitive_（writeArray＃＃改编I＃X）
 

即，在以下方面：

• newArray＃


• readArray＃


• writeArray＃

这是原始的（硬件加速）。服务由语言运行时提供的内存操作

给类型安全破坏性记忆效应的机制被引入哈斯克尔由Launchbury和佩顿 - 琼斯纸的 懒惰的功能状态的线程的，其中介绍了 ST 单子和可变数组元。

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)

解决方案

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.

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.

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)

That is, in terms of:

• newArray#
• readArray#
• writeArray#

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

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屋！