Haskell/库/数据结构入门

本章介绍了库中提供的一些数据结构。我们将重点关注一些常见且特别有用的示例，每个 Haskell 程序员都应该了解这些示例。

权衡

本章不断强调列表的缺点，但这并不意味着你应该停止使用它们！列表是 Haskell 中默认的数据结构，原因有很多：除了简单性之外，列表在懒惰的纯函数式环境中具有相当高的功率重量比。惰性使得列表能够用作 *流*，我们按需顺序处理生成的元素。该过程允许诸如 map、filter、foldr、takeWhile 和 zipWith 等函数作为许多常见迭代控制结构使用的有效替代品。

尽管列表可能很强大，但它们更适合流式传输和迭代控制等模式，而不是简单的数据存储和检索。当然，切换到不同的数据结构会涉及权衡。任何数据结构都有优点和缺点，正确的选择取决于手头的任务。

查找：Data.Map 及其相关

首先，我们将考虑一个常见的问题：对数据结构执行查找。给定一个键和值之间关联的集合，我们可能希望检索与某个键对应的值（如果有的话）。我们可以简单地将关联存储为一对列表，[(k, v)]。事实上，Prelude 包含 lookup :: Eq k => k -> [(k, v)] -> Maybe v，但是要从列表中找到一个值，我们必须遍历列表中的所有对，测试键是否相等，直到我们找到我们要找的键（或者遍历完列表）。在普通关联列表中的查找是 *O(n)* 操作，因为执行它所需的预期步骤数与列表长度成正比。不难看出，当关联很多时，这将成为一个问题。

我们可以通过切换到更合适的数据结构来实现更好的查找。由 containers 包中的 Data.Map 提供的 Map 类型是一个不错的通用选择。请注意，Data.Map 通常被导入限定，以避免与 Prelude 函数发生名称冲突。

GHCi> import qualified Data.Map as M
GHCi> :t M.empty
M.empty :: M.Map k a

在 Map 中，键和值被排列在一个（大小平衡的二叉）树中。这种树形结构使得查找一个键只需简单地沿着树的特定分支向下遍历即可。然而，树的操作完全在幕后进行。Map 与库中的许多其他数据结构一样，通过一个不涉及树实现的接口用作 *抽象* 类型。特别是，构造函数不被导出：一个新的 Map 是通过以下方式构建的，例如，将关联插入到一个 empty 映射中，或者通过使用实用函数 fromList

GHCi> let foo = M.fromList [(1, "Robert"), (5, "Ian"), (6, "Bruce")]
GHCi> :t foo
foo :: M.Map Integer [Char]

Data.Map 接口提供了 *O(log n)* 查找...

GHCi> :t M.lookup
M.lookup :: Ord k => k -> M.Map k a -> Maybe a
GHCi> M.lookup 5 foo
Just "Ian"
GHCi> M.lookup 7 foo
Nothing

...以及许多其他有用的操作 - 并集、交集、删除等等。一些重要类型类的实例（例如 Functor）也可用。

GHCi> M.size $ M.union foo $ M.fromList [(11, "Andrew"), (17, "Mike")]
5
GHCi> fmap reverse foo
fromList [(1,"treboR"),(5,"naI"),(6,"ecurB")]

变体

其他提供映射和类似映射的数据结构的模块值得了解，包括

• containers 中的 Data.IntMap 提供了一个更有效的映射实现，它仅限于 Int 键。
• containers 中的 Data.Set 提供了一个 *集合* 实现。集合适合于当有趣的操作只是查找一个值是否在一个集合中，而不是检索给定键的值。它们很像一个映射，其中只有键很重要，因此关于性能和实现的许多考虑因素都适用于集合和映射。
• unordered-containers 包提供了 *哈希* 映射和集合。它们在不限制键类型为 Int 的情况下提供了效率提升（例如，几乎恒定的查找时间），代价是相对有限的接口和损失了 container 基于树的映射的排序保证。

用 Data.Sequence 窥视两端

列表的一个特点是它们是不对称的。鉴于我们使用 `(:)` 通过头部构建和解构列表，头部操作比尾部操作效率更高。例如，虽然用 `(:)` 添加元素需要恒定的时间，但天真地用 \xs x -> xs ++ [x] 添加单个元素需要与 xs 长度成正比的时间。这意味着通过重复添加来构建列表将花费 *二次* 时间，这在元素数量上非常糟糕。

当必须对中间或尾部执行大量操作时，一个非常棒的列表类替代品是 *序列*，如 Data.Sequence 模块提供的，它也是 containers 的一部分。序列和列表在很多方面都不同，尽管许多熟悉的列表函数以某种形式出现在 Data.Sequence 中。虽然列表是懒惰的并且可以是无限的，但序列是有限的并且是严格的。使得序列有用的权衡是，以牺牲列表的一些开销为代价，许多在列表中很麻烦的操作执行得更好。值得注意的是，我们可以得到在恒定时间内添加和添加、在恒定时间内获得长度，以及在对数时间内进行连接和随机访问。所有这些都可通过一个令人愉快的纯函数式接口获得。

GHCi> import qualified Data.Sequence as S
GHCi> import Data.Sequence((<|), (|>), (><), ViewL(..), ViewR(..))
GHCi> let foo = S.fromList [1, 3, 5, 2, 9]
GHCi> :t foo
foo :: S.Seq Integer

(<|) 添加到头部，(|>) 添加到尾部，(><) 连接。

GHCi> 0 <| foo
fromList [0,1,3,5,2,9]
GHCi> foo |> 18
fromList [1,3,5,2,9,18]
GHCi> foo >< foo
fromList [1,3,5,2,9,1,3,5,2,9]

你也可以在两端进行模式匹配。为此，你可以使用 viewl 或 viewr 来获取序列的所需视图，然后分别使用 EmptyL 和 (:<) 以及 EmptyR 和 (:>) 进行匹配。

GHCi> S.viewl foo
1 :< fromList [3,5,2,9]
GHCi> S.viewr foo
fromList [1,3,5,2] :> 9
GHCi> let xs :> x = S.viewr foo
GHCi> xs
fromList [1,3,5,2]
GHCi> x
9

使用数组进行原始性能

处理大量数据时的性能要求可能非常严格。对于需要快速处理大量数据的场景，惰性和流式传输不是相关问题，Haskell 提供了与 C 等语言中发现的类似的真数组。数组在内存方面是紧凑的，提供恒定的时间随机访问和许多极快的操作（主要例外是那些需要复制数组的操作，例如不可变数组连接），代价是由于数组与我们通常处理的纯函数式数据结构的行为之间的深刻差异而造成的一定程度的笨拙。有几个数组库可用；它们通常提供多种类型的数组 - 从那些使用起来与其他数据结构库（如 containers）中的接口感觉不太不同的数组到 C 风格的原始原始值的可变数组。^[1] 在这里，我们将提到三个最流行的数组库。

• vector 是一个不错的默认选择，如果你刚刚开始使用数组，或者如果你没有其他库涵盖的专门需求。它提供了一维数组，其接口与其他数据结构库（如 containers）中的接口相当类似。

• array 相反，它的接口更加令人望而生畏。至于功能，它支持多维数组和自定义索引。重要的是，它也是语言标准的一部分，并且与 GHC 捆绑在一起，这对那些不想产生额外依赖关系的库编写者很有用。我们在 单独的章节 中提供了标准数组的概述，可以用作数组相关术语的介绍。

• repa 是一个提供最先进的多维可并行数组的复杂库。它非常适合诸如图像处理之类的任务。

text、bytestring 和 String 的问题

快速浏览一下 base 库，我们可能会留下这样的印象：String 是将数据输入和输出 Haskell 程序的首选方式。但是，String 有几个问题，使其不适合这样的角色。

• 最明显的问题是性能。String 只是一个 Char 列表。在需要处理中等甚至相当大文本或二进制数据的应用程序中，通用链表的优势被相对于专用实现可能实现的效率的巨大损失所掩盖。

• 对于二进制数据，更深层的问题是基于 Char 的表示没有意义，因为我们实际上正在处理原始字节。

• 最后，虽然 Haskell Char 是 Unicode 字符，但总体而言，base 库对不同编码和国际化的支持有些不足。

text 和 bytestring 库解决了 String 的这些缺点。这两个库都是 *事实上的* 标准；几乎所有现代库，其功能涉及任何大量数据输入或输出，都使用它们。它们有明显不同的用例。

• text 用于高效处理 Unicode 文本。它支持编码之间的转换，并且通过配套的 text-icu 库，支持各种 Unicode 服务。

• bytestring 用于高效处理二进制数据，无论其形式如何——案例包括网络数据包、原始图像数据、序列化（通过 binary 和 cereal 等库）；任你选择。

这两个库的核心类型 Text 和 ByteString 分别用作 Char 和 Word8（即原始字节）的专门的单态容器。内部表示是基于数组的，非常紧凑。在接口方面，这两个库都非常简单明了。需要注意的主要细微之处是，在这两种情况下，类型都有 *严格的* 和 *惰性的* 变体。严格版本非常适合处理大量小数据块，而惰性版本则以块的形式进行处理，因此允许流式处理和处理大型单片数据，而不会出现内存消耗问题。

在处理 String 替换时，值得注意的一个便利功能是 OverloadedStrings GHC 扩展允许将字符串字面量自动、类型引导地转换为 Text 或 ByteString。这非常有用，尤其是在使用 Text 时。