跳转到内容

Haskell/Libraries/Arrays

Add links
来自维基教科书，开放书籍，共建共享世界
Arrays (Solutions)
库参考

介绍
Maybe
IO
Random
数据结构入门 75% developed
数组
映射

Haskell'98 只支持一个数组构造函数类型，即 Array，它提供不可变的盒子数组。 "不可变"意味着这些数组，就像任何其他纯函数式数据结构一样，其内容在构造时固定。 您不能修改它们，只能查询。 存在“修改”操作，但它们只是返回新数组，不修改原始数组。 这使得可以在纯函数式代码中将数组与列表一起使用。 "盒子"意味着数组元素只是普通的 Haskell（惰性）值，这些值在需要时进行评估，甚至可以包含底层（未定义）值。 您可以在 http://haskell.org/tutorial/arrays.html 中学习如何使用这些数组，我建议您在继续本页面的其余部分之前阅读它。

如今，主要的 Haskell 编译器 GHC 和 Hugs 附带相同的 分层库 集，这些库包含数组的新实现，该实现与 Haskell'98 的实现向后兼容，但功能更多。 不用说，这些库支持 9 种数组构造函数类型：Array、UArray、IOArray、IOUArray、STArray、STUArray、DiffArray、DiffUArray 和 StorableArray。 不难理解为什么数组库会让新来的 Haskellers 感到困惑。 但是，它们实际上非常简单 - 每个都只提供两种接口中的一种，而其中一种您已经知道。

快速参考

[编辑 | 编辑源代码]
不可变
instance IArray a e 		IO 单子
instance MArray a e IO 		ST 单子
instance MArray a e ST
标准 Array
DiffArray 		IOArray STArray
非盒子 UArray
DiffUArray 		IOUArray
StorableArray 		STUArray

不可变数组

[编辑 | 编辑源代码]

新数组库提供的第一个接口由类型类 IArray（代表“不可变数组”，在模块 Data.Array.IArray 中定义）定义，并定义了与 Haskell '98 中为 Array 定义的相同操作。 以下是一个简单示例，演示了它的用法，该示例打印 (37,64)

import Data.Array
buildPair :: (Int, Int)
buildPair = let arr  = listArray (1,10) (repeat 37) :: Array Int Int
                arr' = arr // [(1, 64)]
            in (arr ! 1, arr' ! 1)

main = print buildPair

最大的区别在于它现在是一个类型类，并且有 4 种数组类型构造函数，每种都实现了此接口：Array、UArray、DiffArray 和 DiffUArray。 我们稍后将描述它们之间的差异以及何时优先使用这些其他类型而不是传统的 Array。 还要注意，要将 Array 类型构造函数与其他新数组类型一起使用，您需要导入 Data.Array.IArray 模块而不是 Data.Array。

可变IO数组

[编辑 | 编辑源代码]

第二个接口由类型类 MArray（代表“可变数组”，在模块 Data.Array.MArray 中定义）定义，并包含在适当位置更新数组元素的操作。 可变数组与 IORefs 非常相似，只是它们包含多个值。 可变数组的类型构造函数是 IOArray 和 IOUArray（在 Data.Array.IO 中），创建、更新和查询这些数组的操作都属于 IO 单子

import Data.Array.IO
main = do arr <- newArray (1,10) 37 :: IO (IOArray Int Int)
          a <- readArray arr 1
          writeArray arr 1 64
          b <- readArray arr 1 
          print (a,b)

此程序创建了一个包含 10 个元素的数组，所有值最初都设置为 37。 然后它读取数组的第一个元素。 之后，该程序修改数组的第一个元素，然后再次读取它。 第二行中的类型声明是必要的，因为我们的小程序没有提供足够的上下文来允许编译器确定 arr 的具体类型。

ST单子中的可变数组

[编辑 | 编辑源代码]

与 IORef 具有更通用的兄弟 STRef 一样，IOArray 也具有更通用的版本 STArray（类似地，IOUArray 由 STUArray 模仿；两者都在 Data.Array.ST 中定义）。 这些数组类型允许人们在 ST 单子中使用可变数组

import Control.Monad.ST
import Data.Array.ST

buildPair = do arr <- newArray (1,10) 37 :: ST s (STArray s Int Int)
               a <- readArray arr 1
               writeArray arr 1 64
               b <- readArray arr 1
               return (a,b)

main = print $ runST buildPair

信不信由你，现在您已经知道了使用任何数组类型所需的所有知识。 除非您对速度问题感兴趣，否则只需在适当的地方使用 Array、IOArray 和 STArray。 以下主题几乎完全是关于选择合适的数组类型以使程序运行得更快。

冻结和解冻

[编辑 | 编辑源代码]

Haskell 允许使用 freeze 和 thaw 函数在不可变数组和可变数组之间进行转换

freeze :: (Ix i, MArray a e m, IArray b e) => a i e -> m (b i e)
thaw   :: (Ix i, IArray a e, MArray b e m) => a i e -> m (b i e)

例如，以下将 Array 转换为 STArray，修改它，然后转换回来

import Data.Array
import Control.Monad.ST
import Data.Array.ST

buildPair :: (Int, Int)
buildPair = let arr  = listArray (1,10) (repeat 37) :: Array Int Int
                arr' = modifyAsST arr
            in (arr ! 1, arr' ! 1)

modifyAsST :: Array Int Int -> Array Int Int
modifyAsST arr = runST $ do starr <- thaw arr
                            compute starr
                            newarr <- freeze starr
                            return newarr

compute :: STArray s Int Int -> ST s ()
compute arr = do writeArray arr 1 64

main = print buildPair

冻结和解冻都会复制整个数组。 如果你想在冻结或解冻之前和之后使用相同的内存位置，但可以允许一些访问限制，请参阅 不安全操作和遍历数组元素 部分。

DiffArray

[编辑 | 编辑源代码]

正如我们已经说过的那样，不可变数组 (IArray) 上的更新操作只是创建数组的新副本，这非常低效，但它是一个可以在纯函数中使用的纯操作。 另一方面，可变数组 (MArray) 上的更新很有效，但只能在单子代码中完成。 DiffArray（在 Data.Array.Diff 中定义）结合了两个世界的优点 - 它支持 IArray 接口，因此可以在纯函数式方式中使用，但它在内部使用 MArrays 的高效更新。

这个技巧是如何运作的？ DiffArray 具有纯外部接口，但在内部它表示为对 IOArray 的引用。

当 '//' 运算符应用于差异数组时，其内容会以适当位置的方式物理更新。 旧数组会悄无声息地改变其表示形式，而不会改变可见的行为：它将存储一个指向新当前数组的链接以及要应用的差异以获得旧内容。

因此，如果差异数组以单线程方式使用，即在 '//' 应用之后不再使用旧版本，那么 a ! i 需要 O(1) 时间，a // d 需要 O(n) 时间。 访问旧版本的元素会逐渐变慢。

更新一个不是当前版本的数组会进行物理复制。 生成的数组与旧的系列没有链接。 因此，您可以通过执行“标识更新”old // [] 来获得一个版本，该版本保证是当前版本，因此具有快速元素访问速度。

该库提供了两种“微分”数组构造函数 - DiffArray，在内部由 IOArray 构成，以及 DiffUArray，基于 IOUArray。 如果您确实需要，您可以从任何生活在 'IO' 单子中的 'MArray' 类型构建新的“微分”数组类型。 有关更多详细信息，请参阅 模块文档。

DiffArray 的用法与 Array 的用法没有区别，唯一的区别是内存消耗和速度

import Data.Array.Diff

main = do
       let arr = listArray (1,1000) [1..1000] :: DiffArray Int Int
           a = arr ! 1
           arr2 = arr // [(1,37)]
           b = arr2 ! 1
       print (a,b)

您可以使用 'seq' 来强制在更新数组之前评估数组元素

import Data.Array.Diff

main = do
       let arr = listArray (1,1000) [1..1000] :: DiffArray Int Int
           a = arr ! 1
           b = arr ! 2
           arr2 = a `seq` b `seq` (arr // [(1,37),(2,64)])
           c = arr2 ! 1
       print (a,b,c)

非盒子数组

[编辑 | 编辑源代码]

在大多数惰性评估实现中，值在运行时表示为指向其值或用于计算其值的代码的指针。 这种额外的间接级别，以及运行时可能需要的任何额外标签，被称为盒子。 默认的“盒子”数组包含许多这样的盒子，每个盒子都可以单独计算其值。 这允许许多巧妙的技巧，例如递归地根据彼此来定义数组的元素，或者仅计算永远需要的数组的特定元素。 但是，对于大型数组，它会在开销方面花费很多，如果始终需要整个数组，则可能是浪费。

无箱数组（在 Data.Array.Unboxed 中定义）更像是 C 语言中的数组 - 它们只包含纯值，没有额外的间接层，因此例如一个包含 1024 个 Int32 类型值的数组只会使用 4 kb 的内存。此外，对这类数组的索引速度可以显著提高。

当然，无箱数组也有自己的缺点。首先，无箱数组只能由具有固定大小的纯值组成 - Int、Word、Char、Bool、Ptr、Double 等（在 UArray 类定义 中列出）。你甚至可以自己为其他简单类型（包括枚举类型）实现无箱数组。但是 Integer、String 和任何其他使用可变大小定义的类型都不能成为无箱数组的元素。其次，如果没有额外的间接层，无箱数组中的所有元素都必须在数组被求值时求值，因此你将失去惰性求值的优势。索引数组以读取单个元素将构建整个数组。如果你最终需要整个数组，这并不算什么损失，但这确实阻止了用彼此递归定义数组元素，并且如果只使用特定值，它可能会过于昂贵。尽管如此，无箱数组是一个非常有用的优化工具，我建议尽可能地使用它们。

库中的所有主要数组类型都有无箱对应物

 Array - UArray          (module Data.Array.Unboxed)
 IOArray - IOUArray      (module Data.Array.IO)
 STArray - STUArray      (module Data.Array.ST)
 DiffArray - DiffUArray  (module Data.Array.Diff)

因此，基本上用无箱数组替换程序中的箱数组非常简单 - 只需在类型签名中添加 'U'，就完成了！当然，如果你将 Array 更改为 UArray，还需要在导入列表中添加 "Data.Array.Unboxed"。

StorableArray

[edit | edit source]

可存储数组 (Data.Array.Storable) 是一个 IO 可变数组，它将内容存储在 C 堆中的连续内存块中。元素根据 'Storable' 类存储。你可以获取指向数组内容的指针，以便从 C 等语言中操作元素。

它类似于 'IOUArray'（特别是，它实现了相同的 MArray 接口），但速度更慢。优点是它通过外部函数接口与 C 兼容。可存储数组的内存地址是固定的，因此你可以将它们传递给 C 例程。

指向数组内容的指针由 'withStorableArray' 获取。这个想法类似于 'ForeignPtr'（这里内部使用）。该指针只应该在 'withStorableArray' 函数作为参数传递的函数返回的 'IO' 操作执行期间使用。

{-# OPTIONS_GHC -fglasgow-exts #-}
import Data.Array.Storable
import Foreign.Ptr
import Foreign.C.Types

main = do arr <- newArray (1,10) 37 :: IO (StorableArray Int Int)
          a <- readArray arr 1
          withStorableArray arr 
              (\ptr -> memset ptr 0 40)
          b <- readArray arr 1
          print (a,b)

foreign import ccall unsafe "string.h" 
    memset  :: Ptr a -> CInt -> CSize -> IO ()

如果你想之后使用这个指针，请确保在最后一次使用指针之后调用 'touchStorableArray'，这样数组就不会过早释放。


其他说明：GHC 6.6 应该使访问 'StorableArray' 的速度与访问任何其他无箱数组一样快。'StorableArray' 和 'UArray' 之间的唯一区别是，UArray 位于 GHC 堆的可重定位部分，而 'StorableArray' 位于不可重定位部分，因此保持固定地址，这允许将该地址传递给 C 例程并在 C 数据结构中保存它。

GHC 6.6 还添加了 'unsafeForeignPtrToStorableArray' 操作，该操作允许使用任何 Ptr 作为 'StorableArray' 的地址，特别是在处理 C 例程返回的数组时。使用此操作的示例

import Data.Array.Storable
import Foreign.Marshal.Alloc
import Foreign.Marshal.Array
import Foreign.ForeignPtr

main = do ptr <- mallocArray 10
          fptr <- newForeignPtr_ ptr
          arr <- unsafeForeignPtrToStorableArray (1,10) fptr :: IO (StorableArray Int Int)
          writeArray arr 1 64
          a <- readArray arr 1
          print a
          free ptr

此示例为 10 个 Int 分配内存（模拟由某个 C 函数返回的数组），然后将返回的 'Ptr Int' 转换为 'ForeignPtr Int'，并将 'ForeignPtr Int' 转换为 'StorableArray Int Int'。然后它写入并读取数组的第一个元素。最后，通过 'free' 释放数组使用的内存，它再次模拟 C 例程的释放。我们还可以通过将 "newForeignPtr_ ptr" 替换为 "newForeignPtr finalizerFree ptr" 来启用自动释放已分配的块。在这种情况下，内存将在最后一次使用数组后自动释放，就像任何其他 Haskell 对象一样。

Haskell 数组预处理器 (STPP)

[edit | edit source]

在 Haskell 中使用可变数组（IO 和 ST 数组）并不是很方便。但有一个工具可以添加语法糖，使使用这种数组非常接近于在命令式语言中的使用。它由 Hal Daume III 编写，你可以将其作为 http://hal3.name/STPP/stpp.tar.gz 获取。

使用此工具，你可以在任意复杂的表达式中索引数组元素，只需使用 "arr[|i|]" 表示法，此预处理器将自动将这种语法形式转换为对 'readArray' 和 'writeArray' 的适当调用。也支持多维数组，索引形式为 "arr[|i|][|j|]”。请参阅 http://hal3.name/STPP/ 中的进一步说明。


ArrayRef 库

[edit | edit source]

The ArrayRef 库 重新实现了数组库，并具有以下扩展

  • 动态（可调整大小）数组
  • 多态无箱数组

它还添加了 语法糖，简化了数组使用。虽然不像 STPP 那样优雅，但另一方面，它完全在 Haskell 语言内部实现，没有任何预处理器。


不安全操作和遍历数组元素

[edit | edit source]

如上所述，存在将可变数组和不可变数组转换为相同类型的操作，即 'freeze'（可变 → 不可变）和 'thaw'（不可变 → 可变）。这些操作会复制整个数组。如果你确定可变数组不会被修改，或者不可变数组在转换后不会被使用，那么你可以使用 unsafeFreeze/unsafeThaw 代替 - 这些操作会就地转换数组，如果输入和结果数组具有相同的内存表示（即相同的类型和装箱）。请注意，"unsafe*" 操作会修改内存 - 它们会在数组头中设置/清除标志，以指示数组的可变性。因此，这些操作不能与多线程访问数组一起使用（使用线程或某种形式的协程）。

还存在将无箱数组转换为其他元素类型的操作，即 castIOUArray 和 castSTUArray。这些操作依赖于内存中实际的类型表示，因此没有关于其结果的任何保证。特别是，这些操作可以用于将任何可无箱化的值转换为字节序列，反之亦然，例如，它在 AltBinary 库中用于序列化浮点数。请注意，这些操作不会根据元素大小的更改重新计算数组边界。你应该使用 'sizeOf' 操作自己执行此操作！

虽然数组可以具有任何类型的索引，但在内部，任何在边界检查之后的索引都会被转换为普通的 Int 值（位置），然后使用低级操作之一，即 unsafeAt、unsafeRead、unsafeWrite。你可以在自己需要跳过边界检查并使程序更快的情况下，自己使用这些操作。这些操作在需要遍历整个数组时特别有用

-- | Returns a list of all the elements of an array, in the same order
-- as their indices.
elems arr = [ unsafeAt arr i | i <- [0 .. rangeSize (bounds arr)-1] ]

在这样的循环中使用 "unsafe*" 操作实际上是安全的，因为 'i' 只遍历现有数组元素的位置。

GHC 特定主题

[edit | edit source]

并行数组（模块 GHC.PArr）

[edit | edit source]

正如我们已经提到的，数组库支持两种数组变体 - 惰性箱数组和严格无箱数组。并行数组实现了一些介于两者之间的东西 - 它是一个严格的箱不可变数组。这保留了使用任何数据类型作为数组元素的灵活性，同时使创建和访问这类数组的速度更快。数组创建实现为一个命令式循环，它填充所有数组元素，而访问数组元素不需要检查“箱”。应该很明显，在数组元素的计算相当复杂，并且不会使用大部分数组元素的情况下，并行数组效率不高。实际使用的另一个缺点是，并行数组不支持 IArray 接口，这意味着你无法编写同时适用于 Array 和并行数组构造函数的通用算法。

像许多 GHC 扩展一样，这在论文中进行了描述：Haskell 中快速数组的一种方法，作者是 Manuel M. T. Chakravarty 和 Gabriele Keller。

你也可以查看 GHC.PArr 模块的源代码，其中包含许多注释。

并行数组的特殊语法由 "ghc -fparr" 或 "ghci -fparr" 启用，这在 GHC 6.4.1 的用户手册中没有记录。


欢迎来到机器

[edit | edit source]

Array#、MutableArray#、ByteArray#、MutableByteArray#、固定和可移动字节数组

GHC 堆包含两种类型的对象 - 一些只是字节序列，另一些包含指向其他对象的指针（称为“箱”）。这种隔离允许在执行垃圾回收时找到引用链，并在压缩堆使用的内存时更新这些指针，并将对象移动到新位置。内部 (raw) GHC 的类型 Array# 表示一个对象指针序列（箱）。在 ST 单元中有一个低级操作，它在堆中分配指定大小的数组，它的类型类似于 (Int -> ST s Array#) 。Array# 类型在 Array 类型中使用，Array 类型表示箱不可变数组。

对于可变箱数组（IOArray/STArray），存在一种不同的类型，即 MutableArray#。可变数组的单独类型是由于两阶段垃圾回收机制。Array# 和 MutableArray# 的内部表示相同，除了头部中的一些标志，这使得可以就地转换 MutableArray# 为 Array#，反之亦然（这就是 unsafeFreeze 和 unsafeThaw 操作所做的）。

未装箱数组由 ByteArray# 类型表示。它只是一个堆上的普通内存区域，就像 C 语言的数组一样。有两个基本操作可以创建指定大小的 ByteArray# - 一个在普通堆上分配内存，因此这个字节数组每次发生垃圾回收时都会被移动。这会阻止将 ByteArray# 转换为可以在 C 程序中使用的普通内存指针（尽管仍然可以将当前 ByteArray# 指针传递给“不安全外部”程序，如果它不尝试将该指针存储在任何地方）。第二个基本操作在“固定”堆区域分配指定大小的 ByteArray#，该区域包含固定位置的对象。这种字节数组永远不会被 GC 移动，因此它的地址可以用作普通 Ptr 并与 C 世界共享。创建 ByteArray# 的第一种方式用于所有 UArray 类型的实现内部，第二种方式用于 StorableArray（尽管 StorableArray 也可以指向由 C malloc 分配的数据）。

还有 MutableByteArray# 类型，它与 ByteArray# 几乎没有区别，但 GHC 的基本操作仅支持 MutableByteArray# 的单子读/写操作，仅支持 ByteArray# 的纯读取操作，以及用于更改这些数组头部的相应字段的 unsafeFreeze/unsafeThaw 操作。这种差异除了额外的安全检查外没有太大意义。

所以，固定的 MutableByteArray# 或 StorableArray 内部使用的 C malloc 的内存，I OUArray 和 STUArray 内部使用的未固定的 MutableByteArray#，以及 UArray 内部使用的未固定的 ByteArray#。

装箱和未装箱数组的 API 几乎相同

 marr <- alloc n            - allocates mutable array with given size
 arr  <- unsafeFreeze marr  - converts mutable array to immutable one
 marr <- unsafeThaw arr     - converts immutable array to mutable one
 x    <- unsafeRead marr i  - monadic reading of value with given index from mutable array
 unsafeWrite marr i x       - monadic writing of value with given index from mutable array
 let x = unsafeAt arr i     - pure reading of value with given index from immutable array
 (all indexes are counted from 0)

基于这些基本操作，数组库实现了对任何类型和任何下界的索引，边界检查以及所有其他高级操作。创建/更新不可变数组的操作只是在 ST 单子中将它们创建为可变数组，对该数组进行所有必需的更新，然后在从 runST 返回数组之前使用 unsafeFreeze。IO 数组上的操作是通过使用 stToIO 操作对 ST 数组上的操作实现的。

可变数组和 GC

[edit | edit source]

GHC 实现了一个两阶段的 GC，它非常快 - 小 GC 在每分配 256 kb 后发生，并且在搜索“活动”数据时只扫描该区域（以及最近的堆栈帧）。这个解决方案利用了普通 Haskell 数据是不可变的事实，因此在上次小 GC 之前创建的任何数据结构都不能指向该 GC 之后创建的数据结构（由于不可变性，数据只能包含“向后”引用）。

但是，当我们在语言中添加可变装箱引用 (IORef/STRef) 和数组 (IOArray/STArray) 时，这种简单性就会被打破。在每次 GC（包括小 GC）上，可变数据结构中的每个元素都应该被扫描，因为它们可能自上次 GC 以来被更新，现在指向上次 GC 以来分配的数据。

对于包含大量可变装箱数组/引用数据的程序，GC 时间可能会很容易地超过有用的计算时间。具有讽刺意味的是，其中一个这样的程序是 GHC 本身。解决此类程序的方案是在命令行选项中添加类似 "+RTS -A10m" 的选项，该选项将小 GC 块的大小从 256 kb 增加到 10 mb，即使小 GC 的频率降低 40 倍。您可以使用 "+RTS -sstderr" 选项看到此更改的效果 - "%GC 时间" 应该显着下降。

有一种方法可以将此选项包含到您的可执行文件中，这样它将在每次执行时自动使用 - 您只需将包含以下行的 C 源文件添加到您的项目中

char *ghc_rts_opts = "-A10m";

当然，您可以根据需要增加或减少此值。

增加 "-A" 值并非没有代价 - 除了显而易见的内存使用量增加外，执行时间（有效代码的执行时间）也会增加。默认的 "-A" 值经过调整，使其接近现代 CPU 缓存的大小，这意味着大多数内存引用都落在缓存内。当在进行 GC 之前分配了 10 mb 的内存时，这种数据局部性就不再成立了。因此，增加 "-A" 可能会增加或减少程序速度，具体取决于程序的性质。尝试在运行程序时使用“典型”参数尝试 64 kb 到 16 mb 之间的各种设置，并尝试为您的具体程序和 CPU 组合选择最佳设置。

还有一种方法可以避免增加 GC 时间 - 使用未装箱或不可变数组。还要注意，不可变数组是作为可变数组构建的，然后被“冻结”，因此在构建期间 GC 也会扫描它们的内容。

希望 GHC 6.6 修复了这个问题 - 它会记住自上次 GC 以来哪些引用/数组被更新，并只扫描它们。只有在使用非常大的数组时才会遇到旧问题。

更多信息


检索自 "https://wikibooks.cn/w/index.php?title=Haskell/Libraries/Arrays&oldid=3676129"
华夏公益教科书