Haskell中的数组

与普遍存在的链表类型 [a] 不同。在Haskell中，没有任何内置语法支持，或者任何其他特殊的编译器支持数组,除了一些内置的原语，可以在 ghc-prim中找到

newArray# :: Int# -> a -> State# s -> (# State# s, MutableArray# s a #)
readArray# :: MutableArray# s a -> Int# -> State# s -> (# State# s, a #)
writeArray# :: MutableArray# s a -> Int# -> a -> State# s -> State# s
newByteArray# :: Int# -> State# s -> (# State# s, MutableByteArray# s #)
indexInt8Array# :: ByteArray# -> Int# -> Int#
indexInt16Array# :: ByteArray# -> Int# -> Int#
...

我们很难直接使用这些函数，因为它们直接操作 State# 令牌，并且它们区分不同的数组类型：如盒装的(Boxed) Array#， ByteArray# 等。这些类型后的#表示它们是特殊的原始类型，我们将稍后将进行讨论。

在Z-Data中，我们为统一数组操作提供了类型包装器和类型类：

class Arr (arr :: * -> * ) a where
    -- | 可变版本的数组类型.
    type MArr arr = (mar :: * -> * -> *) | mar -> arr
    -- | 创建指定大小的数组.
    newArr :: (PrimMonad m, PrimState m ~ s) => Int -> m (marr s a)
    -- | 创建数组并为其中的元素填补指定值.
    newArrWith :: (PrimMonad m, PrimState m ~ s) => Int -> a -> m (marr s a)
    -- | 访问在原生monad中的数组.
    readArr :: (PrimMonad m, PrimState m ~ s) => marr s a -> Int -> m a
    -- | 写入原生monad中的数组.
    writeArr :: (PrimMonad m, PrimState m ~ s) => marr s a -> Int -> a -> m ()
    -- | 用指定值填充可变数组值.
    setArr :: (PrimMonad m, PrimState m ~ s) => marr s a -> Int -> Int -> a -> m ()
    -- | 访问不可变数组 这是一个纯函数
    indexArr :: arr a -> Int -> a
    -- | 访问原生monad中的不可变数组,当你想要访问你的索引元素不是一个引用整个数组的thunk时很有用。
    indexArrM :: (Monad m) => arr a -> Int -> m a
    -- | 通过创建一个可变数组切片的不可变数组拷贝，以安全地冻结可变数组.
    freezeArr :: (PrimMonad m, PrimState m ~ s) => marr s a -> Int -> Int -> m (arr a)
    -- | 通过创建一个不可变数组切片的可变数组拷贝，以安全地解冻不可变数组.
    thawArr :: (PrimMonad m, PrimState m ~ s) => arr a -> Int -> Int -> m (marr s a)
    -- | 原地冻结数组，原来的可变数组将无法继续使用.
    unsafeFreezeArr :: (PrimMonad m, PrimState m ~ s) => marr s a -> m (arr a)
    -- | 原地解冻数组，原来的不可变数组将无法继续使用.
    unsafeThawArr :: (PrimMonad m, PrimState m ~ s) => arr a -> m (marr s a)
    -- | 拷贝一个不可变数组的切片到一个可变数组的指定偏移位置.
    copyArr ::  (PrimMonad m, PrimState m ~ s) => marr s a -> Int -> arr a -> Int -> Int -> m ()
    -- | 拷贝一个可变数组的切片到一个可变数组的指定偏移位置.
    -- 这两个数组不能是同一个.
    copyMutableArr :: (PrimMonad m, PrimState m ~ s) => marr s a -> Int -> marr s a -> Int -> Int -> m ()
    -- | | 拷贝一个可变数组的切片到一个可变数组的指定偏移位置.
    -- 这两个数组可以是同一个.
    moveArr :: (PrimMonad m, PrimState m ~ s) => marr s a -> Int -> marr s a -> Int -> Int -> m ()
    -- | 创建一个不可变拷贝.
    cloneArr :: arr a -> Int -> Int -> arr a
    -- | 创建一个可变拷贝.
    cloneMutableArr :: (PrimMonad m, PrimState m ~ s) => marr s a -> Int -> Int -> m (marr s a)
    -- | Resize mutable array to given size.
    resizeMutableArr :: (PrimMonad m, PrimState m ~ s) => marr s a -> Int -> m (marr s a)
    -- | 收缩数组的大小至指定值. 该操作只能对原生数组生效.
    -- 对于盒装的数组, 这个操作是一个无用操作, 即 'sizeOfMutableArr' 不会改变.
    shrinkMutableArr :: (PrimMonad m, PrimState m ~ s) => marr s a -> Int -> m ()
    -- | 两个可变数组是否指向同一个引用.
    sameMutableArr :: marr s a -> marr s a -> Bool
    -- | 不可变数组的长度.
    sizeofArr :: arr a -> Int
    -- | 可变数组的长度.
    sizeofMutableArr :: (PrimMonad m, PrimState m ~ s) => marr s a -> m Int
    -- | 判断两个不可变数组是否指向同一个引用.
    sameArr :: arr a -> arr a -> Bool

我们有以下的实例：

-- | 盒装的数组类型, 持有Haskell抽象数据类型.
instance Arr Array a where
    type MArr Array = MutableArray
    ...
-- | 盒装的数组类型, 持有Haskell抽象数据类型, 但没有卡片表.
instance Arr SmallArray a where
    type MArr SmallArray = SmallMutableArray
    ...
-- | 非盒装的数组类型, 持有原生数据类型如Int, Word8等.
instance Prim a => Arr PrimArray a where
    type MArr PrimArray = MutablePrimArray
    ...
-- | 盒装的数组类型, 持有盒装非提升的类型, 详见后续章节.
instance PrimUnlifted a => Arr UnliftedArray a where
    type MArr UnliftedArray = MutableUnliftedArray
    ...

如果你知道 IO 在Haskell中是如何工作的，可以将PrimMonad简单地等同于ST或IO。如果你对PrimMonad约束感到困惑，请在更多详细信息中获取。

盒装的，非盒装的

对于许多Haskell的使用者而言，使用数组可能是你第一次知道boxed和unboxed类型之间的区别是什么。花一些时间了解这些术语的意思是很重要的。

在其他语言中，你通常必须区分引用和值。例如，在C中，指针是对其他对象的引用。从硬件的角度来看，指针是一个内存地址：你可以使用机器码来找到它所指向的内存引用。而其他非指针类型的值就不是一个内存地址了，它们的1-0排列表示了该类型的某个值。

在 Haskell 中，从C语言的角度来看几乎每个你所见到的的值都是一个指针，即指向堆对象的内存位置，例如，像这样的数据类型：

data Foo = Foo Int Char
foo = Foo 3 'a'

上述代码内存布局表现为:

    foo(由寄存器或者其他盒子指向的)
     |
     V
+----+--------+---+---+    +-------------+------+
| info-table* | * | * +--->+ info-table* | 'a'# |
+-------------+-+-+---+    +-------------+------+
  Foo           |           C# (Char构造器)
                V
            +---+---------+----+
            | info-table* | 3# |
            +-------------+----+
             I# (Int构造器)

在运行时，值foo是引用，且所有的操作，例如模式匹配，都需要进行引用求值(Dereferencing)。这样的值称为盒装的(Boxed)，因为它是对盒子的引用，即持有info-table的堆上对象。信息表(Info-table)包含有关该盒子的许多有用信息，例如，盒子所占用的字节数，盒子所对应的构造函数等。

上面用到的 3# 和 'a'# 是Haskell的非指针值，我们称这些值为 非盒装的((Unboxed) 值。非盒装的值没有信息表，因此我们不能将它们直接放在堆上：否则，GC在扫描它们时会感到困惑：如果没有来自信息表的信息，则无法确定要复制多少字节。这些值通常属于寄存器或其他盒子：我们生成机器码以直接对其进行操作。

盒装的（Boxed）数组

现在让我们考虑GHC的数组，它们是RTS提供的特殊堆对象。我们有装箱的数组 MutableArray# 和 Array#，他们存储着对盒子的引用：

+-------------+--------------+---------------------------+---+-...-+---+---+------------+
| info-table* | payload size | payload + card-table size | * | ... | * | * | card table |
+-------------+--------------+---------------------------+-+-+-...-+---+---+------------+
 MutableArray#                                             |
 Array#                                                    V
                                                    +------+------+-----+
                                                    | info-table* | ... |
                                                    +-------------+-----+
                                                      盒子, 可能是一个 thunk
                                                      盒装的数组大部分操作作用于数组元素时都是惰性的

它看起来非常复杂，尤其是卡片表（card-table）的部分，该部分用于数组GC优化。在分代式GC中，一旦将 MutableArray# 提升到一个世代后，它们始终会保留在该世代的可变列表中，因此，卡片表的优化很重要，如果你将大型可变数组长时间保留在堆。对于小数组其实没有必要使用卡片表，GHC为此提供了 MutableSmallArray#/SmallArray#。

+-------------+--------------+---+-...-+---+---+
| info-table* | payload size | * | ... | * | * | 
+-------------+--------------+---+-...-+---+---+
 MutableSmallArray#
 SmallArray#

为了可以更轻松地使用这些类型，我们提供了ADT包装器：

data MutableArray s a = MutableArray (MutableArray# s a)
data Array a = Array (Array# a)

data SmallMutableArray s a = SmallMutableArray (SmallMutableArray# s a)
data SmallArray a = SmallArray (SmallArray# a)

Haskell中的一种常见模式是在完成创建后通过冻结(Freeze)操作将 MutableArray 转换为 Array，为了方便我们再次解冻(Thaw)数组，card-table的空间仍然会被保留。一般来说，在创建冻结模式下，更建议使用MutableSmallArray 和 SmallArray，因为可变数组往往不会在堆上保留太长时间。

非盒装的数组

MutableByteArray#, ByteArray# 是GHC的非盒装的数组(Unboxed array)。它们不包含指针，并且在GC期间无需关注他们的负载(payload)：

+-------------+--------------+-------------+---+-...-+---+---+
| info-table* | payload size | 0xXXXXXXXX# | # | ... | # | # |
+-------------+--------------+-------------+---+-...-+---+---+
 MutableByteArray#
 ByteArray#   

ByteArray# 可以用来编码不同大小的非指针数据，例如Int和Word8，ghc-prim 提供了独立的函数来处理不同的数据类型：如 indexIntArray#，indexWord8Array# 等，因此我们提供了 Prim 类型类和 PrimArray 类型，这让使用不同的类型更加容易：

-- 可以存储在 ByteArray# 中的类型
class Prim a where
    indexByteArray# :: ByteArray# -> Int# -> a
    ...

-- | 被 ByteArray# 索引的类型
data PrimArray a = PrimArray ByteArray#

indexPrimArray :: Prim a => PrimArray a -> Int -> a
...

提升的，非提升的

类型之间的另一个区别是：非提升的和提升的，这是因为在Haskell中，我们具有 non-strict evaluation 机制，例如值 1 + 2 可能具有以下表示形式：

+-------------+----------+---+    +-------------+----+
| info-table* | reserved | * +--->+ info-table* | 2# |
+------+------+----------+---+    +-------------+----+
       |                           This is I#
       V
 info-table 指向 (+1) 代码.

在Haskell中，1 + 2 和 3 都是引用，它们可以互换使用：这两个指针都可以被以 Int 为参数的函数接受。这是通过 entering 堆对象来完成的。即执行 info-table 重的 entry code。构造函数的 entry code 仅仅只做返回一件事。对于 thunk ，代码将进行求值，并且通过写入前向指针(Forward pointer)并将 thunk box 修改为 indirection box ，上面的 reserved 字段正是用来保存求值结果的。

求值过程可能会失败（发散递归，堆栈溢出等），因此指针可能指向未定义的值，这种情况在 Haskell 中称为 bottom，写为 _|_ 。之所以被称为 bottom ，是因为所有其他被求值的值都具有确定的语义，但 bottom 却没有，它在确定性，具体性，有用性等方面会比其他类型的值来说更差一些…… 因此，产生了 lifted 类型的概念，即包含 bottom 的值。

如您所料，大多数盒装类型都包含了 _|_ ，thunk 可能会因异常并终止您的程序，或者在代码中调用 error 或 undefined 。而且大多数非盒装的类型都是非提升类型。一个 Int# 代表一个未定义的值是不可能的，因为所有的1-0排列都是用来表示一个 Int# 。或者换个说法：我们不可能从 Int# 中得到 bottom ，因为它没有 info-table ，我们也无法“进入”其中。

但是确实存在一些盒装的非提升的类型，例如 MutableArray#/Array# 就是这样的类型，它们在堆上的表示里有一个 info-table 的指针，但是从来没有“进入”过。所有操纵他们的原语都不会“进入”他们的 entry code ，创建它们的唯一方法是通过 newArray#, cloneArray# 等。

为了有效地存储盒装的非提升类型，引入了 Unlifted 类和 UnliftedArray 类型，类似于 Prim 和 PrimArray ，UnliftedArray 存储非提升的引用而不是常规的 Haskell ADT。与 Array Array 相比, UnliftedArray Array 可以去掉一层重定向，即移除 Array 盒子并直接存储 Array# 类型。

有关数组的更多信息

Haskell数组有更多相关的内容，例如 pinned 和 unpinned 的 ByteArray 等。有兴趣的读者可以在GHC wiki，中找到相关的信息，尤其是在RTS部分。要正确使用数组，你需要做的就是选择适当的存储类型并导入 Z.Data.Array。在下一节中，我们将介绍 vector ，它只是数组的切片。

目录