第5章 单词与图（Words and graphs）

本章涵盖

• 在 Haskell 中建模图结构
• 通过隐藏数据类型的构造和修改来确保其不变量
• 以最小开销重用实现
• 为字符串构建简单变换

上一个项目是一个流行 UNIX 工具的最小克隆，非常正经！但生活不只有为终端行号需求编写工业级工具。让我们找点乐子。人们通常如何娱乐？当然是玩游戏！

单词接龙是一个有趣的小游戏，玩家需要从词汇库中挖掘单词链，通过逐字母变换构建链条。游戏有许多变体，我们将聚焦一个相当复杂的版本。但与其亲自玩，何不让计算机代劳？

即使是为儿童游戏编写人工智能也并非易事。这个项目将促使我们思考如何巧妙运用数据结构来解决搜索问题。虽然表面简单，但我们会发现即使是儿戏也可能暗藏陷阱。

本章首先讨论如何用 Haskell 类型建模图，以及如何创建自定义模块。接着探索类型类的基础知识，讨论其定义、功能及用法。然后，我们使用关联列表和模块导出列表创建特殊的地图数据类型，以确保数据类型的不变性。通过使用地图，我们为图创建数据类型，并为单词列表的排列构建查找表。

5.1 构建图 （Building a graph）

接龙游戏是个有趣的练习，要求玩家（人数不限）深挖词汇知识。游戏有多种规则变体；我们将从最简单的变体入手，再讨论如何为游戏开发人工智能。

玩家从两个相同长度的单词开始。一个视为起点，另一个视为终点。任务是找到连接起点和终点的单词链，其中每对相邻单词仅差一个字母。这意味着玩家从起始词开始，每次改变一个字母得到新词，持续变换直到形成完整链条。若多人游戏，链条最短者胜。示例：cat → sat → sag → dag → dog。

这游戏虽有趣，但对计算机而言不过是小菜一碟（我们很快会验证）。实际上，这是搜索问题的经典案例。要找到解决方案，我们需要在领域（一堆单词）中搜索从起点到终点的路径。这类问题常见于众多应用：

• 导航系统
• 数据库
• 网络路由器
• 数独求解器

通过解决单词接龙游戏，我们习得的技能可迁移至其他领域。对计算机而言，无论搜索对象是什么，搜索本质相同。区别仅在于解决方案的建模方式。在我们的游戏中，单词因特定规则而连接，但在导航系统中，路径由地图数据提供。一旦剥离这层抽象，问题就变得一致。

为了让问题更有挑战性，我们将增加复杂度：不仅允许改变单个字母，还允许增删字母，甚至任意重排字母顺序。这一修改使游戏趣味大增，因为现在可以在不同长度的单词间寻找路径。例如，在 find 和 solution 之间可找到解决方案（如 find → fins → ions → loins → tonsil → lotions → solution）。图 5.1 展示了逐步解决方案。

图 5.1 改进版接龙游戏中 find 与 solution 的解决方案

这一修改不仅让我们找到更具创造性的解决方案，也增加了计算求解的难度。解决此问题时，我们需要考虑性能优化，并巧妙减少不必要的计算。

5.1.1 多态类型（Polymorphic types）

现在，我们可以开始思考如何为这类游戏构建人工智能了。我们假设我们的智能体以某种方式拥有一个包含所有英语单词的完整列表。如果它想找到一个有效的链条，就需要找到一条从一个单词到另一个单词的路径，并且每一步转换都是有效的。为此，我们可以设想所有单词排列在一个图中，当且仅当可以在一步内从一个单词到达另一个单词时，这两个单词（作为图中的节点）之间就存在一条边。图5.2展示了几个单词构成的这种图。可以看到，通过在这个图中找到一条路径，就可以发现从"cat"到"dog"的一个链条。

图5.2 一个由部分英语单词构成的阶梯图

我们立刻就能看到，从"cat"到"dog"存在多条路径。一个解可能是：cat → hat → heat → heal → held → dole → does → dogs → dog。然而，这并不是最短的解！例如，一个更短的解是：cat → cats → tags → goat → got → dog。我们的人工智能必须能够在这种阶梯图中找到最短的解，我们姑且这么称呼它。

我们可以快速勾勒出程序应该做的事情：

1. 从用户那里读取起始单词和结束单词。
2. 根据词典构建一个阶梯图。
3. 在阶梯图中搜索从一个单词到另一个单词的最短路径。

幸运的是，寻找这种最短路径的问题在计算机科学中已被广泛研究，所以这应该不成问题。真正的问题在于，我们首先需要计算出这样一个阶梯图才能找到解。这让我们思考：如何在 Haskell 中表示一个图呢？

让我们回顾一下图是什么。图由节点和边组成，边连接着这些节点。边可以是有向的（因此只能从一个节点构建到另一个节点的路径，反过来不行），也可以是无向的。此外，边可以有成本，但在我们的问题中可以忽略这些。我们视路径中的每条边都是相同的：一条边代表阶梯游戏中的一步。这就给了我们许多用 Haskell 类型来表示这个概念的可能性。首先，我们想在图中存储什么类型的元素？这些元素将是什么类型？我们可以选择一个固定的类型，但没有必要这样做。一般来说，图中元素的类型是不确定的，因此我们将使用一个多态类型：

type Graph a = ...

这将使我们在图中可以使用的类型更加灵活，但图本身要如何建模呢？因为我们处理的是无向图且边没有成本，我们只关心存储两个节点相连的信息。使用邻接表可以实现这一点。这种表包含了所有相连的节点对。在上一章中，我们已经遇到过一种可以表示这种数据结构的类型：关联列表！

type Graph a = [(a, a)]

当且仅当列表中存在包含两个节点的元组时，表示这两个节点之间存在一条边。虽然这种类型非常简单，但在性能方面有一些缺点。在最坏的情况下，检查一条边是否存在以及收集一个给定节点的所有邻接点，都需要我们扫描整个列表。向列表中插入一条新边也是如此，因为我们必须检查重复项。对于较大的图，这是不可接受的，而由于我们希望能够处理整个词典，这种方法是行不通的。为了高效遍历，我们需要一种允许快速索引的数据结构。根据底层实现的不同，邻接映射可能是一个更好的解决方案：

type DiGraph a = [(a, [a])]

这种类型将一个节点映射到一个节点列表，因此隐含了多条边，但仅限于一个方向！因此，这种类型被命名为 DiGraph，以表明它是有向的。图5.3展示了这个映射如何对应一个图结构。

图5.3 基于邻接映射构建的图示例

遗憾的是，如果我们想表示无向图，这种类型有一个缺点。添加一条无向边需要我们在映射中添加两个元素。对于一个包含两个相连节点的简单无向图，对于节点 1 和 2，其值看起来像 [(1, [2]), (2, [1])]。

目前，让我们先从这个类型开始，因为有向图对于我们的搜索问题来说已经足够（我们稍后会看到）。我们不仅要创建这个类型，还要创建一组函数来操作这个类型。为此，我们希望将所有功能打包到它自己的模块中！让我们开始创建一个新项目！我们将它命名为 ladder。

5.1.2 引入新模块（Introducing a new module）

使用 stack new ladder 创建新项目后，现在我们将在 src 目录中创建一个新文件，这将是我们用于图类型的新模块。我们将文件命名为 Graph.hs。这将是我们所有与图相关的定义的模块：

module Graph where

请记住，模块名与文件名保持一致很重要。

注意 此外，模块可以打包在源目录的子目录中。如果模块位于类似 Foo/Bar/Module.hs 的路径中，则模块名称需要相应地反映出来，例如 Foo.Bar.Module。子目录名称通常大写。

现在，我们可以开始思考想要实现的函数了。首先，让我们专注于构建图。如何向图中添加单个节点？仅仅是向列表中添加一个关联元组那么简单吗？不完全是，因为我们必须确保同一个键不会在列表中出现两次。请记住，关联列表的作用类似于映射（map）。在我们的例子中，我们将节点映射到与它们相连的其他节点。因此，首先我们需要实现一个在映射中查找键的函数，然后在插入函数中使用它。该函数如下代码清单所示。

代码清单 5.1 检查键是否存在于关联列表中的函数

member _ [] = False                    -- #1
member x ((x', _) : xs)                -- #2
  | x' == x   = True                    -- #3
  | otherwise = member x xs             -- #4

• #1 返回 False，因为空关联列表没有键
• #2 匹配输入列表及其第一个元素作为一个元组，并将该元组的第一个元素命名为 x'
• #3 如果列表头部的第一个元素等于参数，则返回 True
• #4 如果之前的守卫不匹配，则在列表的剩余部分上递归调用函数

在这个函数的第二个模式中，我们可以看到在列表中匹配元组的例子。元组的第一个元素（它本身也是列表的第一个元素）被命名为 x'，而第二个元素被忽略。

这个函数的类型表达式被有意省略，是为了让我们思考这个类型应该是什么样的。我们想为一个通用的关联列表定义一个函数（以便稍后用于我们的图类型定义）。这让我们得出结论：关联列表和搜索元素的类型需要是多态的：

member :: a -> [(a, b)] -> Bool

这个表达式似乎有道理。键和搜索的元素需要是相同的类型，而元组中的第二个元素可以是任何其他类型。但是，如果我们尝试将此类型赋给函数并编译代码（例如，使用 stack repl），就会得到一个错误！

...
    • No instance for (Eq a) arising from a use of ‘==’
      Possible fix:
        add (Eq a) to the context of
          the type signature for:
            member :: forall a b. a -> [(a, b)] -> Bool
...

这是怎么回事？错误源于使用了 (==) 函数。我们假定键的类型是自由多态的，但我们如何确保使用该函数的类型具有可比较的值呢？我们通常如何知道哪些类型具有可比较的值？

注意 Haskell 中的运算符如 == 或 && 都是函数，我们可以像使用其他函数一样使用它们！编译器以中缀表示法解释它们，但可以通过将运算符括在括号中来像其他函数一样引用它们，例如 (==)。这使得它们可以在高阶函数中使用（例如，zipWith (==) [1,2,3] [1,1,3] 求值为 [True,False,True]）。

要理解这个难题，我们必须快速进入类型类（type classes）的主题。它们是什么？

5.1.3 Eq 类型类和类型约束（The Eq type class and type constraints）

让我们从一个简单的问题开始讨论：类型具有什么属性？类型本身只是值集合的名称（在极少数情况下甚至可能没有值）。但是，一个值属于某种类型并不意味着我们必然知道可以对它执行哪些操作。在大多数语言中，某些操作是针对特定类型隐含的，比如 C 或 Java 中的相等运算符 ==，它为基本数据类型定义。然而，在 Haskell 中，我们更明确地定义类型的操作。这是通过类型类完成的；类型类包含需要为类的实例定义的函数（或值，因为函数本身也是值）的签名。我们可以通过 GHCi 检查这一点，如下所示：

ghci> :info Eq
type Eq :: * -> Constraint
class Eq a where
  (==) :: a -> a -> Bool
  (/=) :: a -> a -> Bool
  {-# MINIMAL (==) | (/=) #-}

这个输出告诉我们，Eq 类型类定义了两个方法：一个用于相等（==），一个用于不等（/=）。从相等运算符的类型签名（a -> a -> Bool）中，我们还可以立即推断出，我们只能比较存在此类型类实例的相同类型的值。因此，例如，我们不能比较 Int 和 Float！

此类的类型实例只需要提供其中一个方法的实现，如 MINIMAL 编译指示所示。缺失的方法只需通过对给定方法的结果取反来推断。因此，当我们为某个类型定义相等（或不等）时，我们会自动获得相反的功能！

在我们作用域内现有的实例也列在与该签名相同的输出中。以下是一些实例：

instance Eq Bool
instance Eq Char
instance Eq Integer
instance Eq Int
instance Eq Float

这些是我们熟悉的类型，我们已经使用过它们。这些实例中的每一个都定义了如何检查其各自类型值的相等性。此外，我们看到：

instance Eq a => Eq (Maybe a)
instance Eq a => Eq [a]

某些实例将类型约束作为先决条件。这两个例子告诉我们，如果任意类型 a 具有 Eq 类型类的实例，那么对于该类型，Maybe a 和 [a] 也具有 Eq 的实例。这意味着 Maybe Float 和 [Int] 也可以进行比较！

警告 类型类的词汇与面向对象编程有一些重叠。但是，绝不应混淆这些概念！类型类不能被实例化为对象，并且方法的行为也不像类方法，因为它们的实现可能因类型而异。类型类在面向对象的上下文中与接口更相关，而不是与类相关。

还有更多类型类，我们将在适当的时候看到其中的一些，但现在，让我们专注于为我们的 member 函数找到一个类型表达式。当我们想要指定要搜索的元素类型需要具有可比较的相等性时，它需要具有 Eq 类型类的实例。我们可以通过在类型表达式中添加类型约束来实现这一点：

member :: Eq a => a -> [(a, b)] -> Bool

该约束指定了我们使用的多态类型必须具有哪些属性。请注意，当显式指定类型时（例如，使用 Int），我们不需要添加约束，因为已经知道该类型具有哪些实例。另外，请注意类型类的方法如何隐式地带有自己的类型约束：

ghci> :type (==)
(==) :: Eq a => a -> a -> Bool

如果我们想使用 (==)，那么多态类型需要具有 Eq 类型类的实例。这就是为什么否则我们会得到编译错误！

注意 在前面的章节中，我们有时有意省略类型表达式，以使我们的某些函数可以编译。我们这样做是为了让 Haskell 自己推断出约束。类型推断足够强大，至少在大多数情况下可以做到这一点。

5.1.4 flip 函数（The flip function）

现在我们已经完成了这个插曲，终于可以实现向图中添加新节点的函数了。为了使命名更清晰，我们定义一个新函数 hasNode，它只是 member 的一个别名，但参数顺序颠倒了。用于向图中添加新节点的函数现在只需检查节点是否已存在，如果不存在，则将其添加，并且没有出边。实现此功能的代码如下所示。

代码清单 5.2 检查键是否存在于关联列表中的函数

member :: Eq a => a -> [(a, b)] -> Bool   -- #1
member _ [] = False
member x ((x', _) : xs)
  | x' == x = True
  | otherwise = member x xs

hasNode :: Eq a => DiGraph a -> a -> Bool    -- #2
hasNode = flip member   -- #3

addNode :: Eq a => DiGraph a -> a -> DiGraph a
addNode graph node
  | graph `hasNode` node = graph        -- #4
  | otherwise = (node, []) : graph     -- #5

• #1 定义一个函数，用于检查键是否存在于关联列表中
• #2 定义一个函数，用于检查节点是否存在于有向图中
• #3 翻转 member 的参数以产生 hasNode 的定义
• #4 如果图已包含要添加的节点，则返回未更改的图
• #5 如果节点尚不存在于图中，则返回添加了该节点的图

请注意我们函数的参数顺序。hasNode 有意将图作为第一个参数，以便它可以以中缀表示法书写。为了翻转这些参数，我们使用了一个名为 flip 的函数：

flip :: (a -> b -> c) -> b -> a -> c

这个函数接受一个二元函数，并产生一个参数顺序颠倒的函数！注意 a 和 b 是函数的参数，通过部分函数应用，将 flip 应用于单个二元函数将产生一个类型为 b -> a -> c 的新函数。

练习：lookup 函数 Data.List 模块（以及总是被导入的 Prelude）已经提供了一个在关联列表中查找键的函数，称为 lookup。尝试使用它重写 member 函数。

查看类型表达式，我们看到必须在每个函数的约束中添加 Eq。这是因为我们想在它们的定义内部使用其他具有相同约束的函数（如 (==)）。我们需要确保函数参数的类型满足其相应定义的所有约束。如果我们不添加 Eq 约束，我们将指定可以在一个检查相等性的函数内部使用任意类型，即使是那些无法检查相等性的类型，这是不可能的。

提示 有时，你会遇到一些函数，在其类型约束中带有你从未见过的类型类。我发现快速了解该类（它具有哪些方法和实例）的方法是使用 GHCi 检查该类。你可以通过 :i <类名> 来做到这一点。

现在我们知道如何使用类型类，我们可以解决构建图的更大问题。我们应该考虑可以在模块中添加哪些函数来帮助我们处理关联列表。

5.2 封装实现（Encapsulating implementations）

在构建图时，我们希望添加一个名为 addEdge 的新函数，用于在图的两个节点之间添加一条边。为此，我们需要检查起始节点是否已经存在于图中。如果它不存在，就必须把这个节点连同一个只包含终点节点的新边列表一起加入图中；如果它已经存在，就必须修改现有的边列表。换句话说，我们需要以某种方式“改变”这个映射。

为了让事情更简单，我们想创建一个新函数，对映射执行任意修改。理想情况下，它应该能够添加新元素、删除元素，以及修改某个键对应的值。一个好办法是使用高阶函数，让它接收一个函数参数，由这个参数决定数据结构应该发生什么变化。

这个函数需要把给定键是否已经存在的信息传给参数函数，然后再根据该参数函数返回的信息判断这个值应当被修改、移除，还是保持缺失。两个步骤都可以用 Maybe 类型完成。下面的代码清单给出了实现。

代码清单 5.3 修改关联列表的函数

alter :: Eq k => (Maybe v -> Maybe v) -> k -> [(k, v)] -> [(k, v)]
alter f key [] =                         -- #1
  case f Nothing of                       -- #2
    Nothing -> []                         -- #3
    Just value -> [(key, value)]          -- #4
alter f key ((key', value') : xs)         -- #5
  | key == key' =                         -- #6
    case f (Just value') of               -- #7
      Nothing -> xs                       -- #8
      Just value -> (key, value) : xs     -- #9
  | otherwise =
    (key', value') : alter f key xs       -- #10

• #1 匹配空关联列表
• #2 因为给定键没有关联值，所以用 Nothing 调用转换函数
• #3 如果函数没有返回值，则返回空列表
• #4 如果转换函数返回了值，则返回包含这个键值对的关联列表
• #5 匹配至少包含一个元素的列表
• #6 如果列表头部的键等于函数给定的键，则匹配成功
• #7 用给定键当前关联的值调用转换函数
• #8 如果转换函数返回 Nothing，则移除给定键的映射
• #9 如果转换函数返回 Just value，则使用返回的新值更新映射
• #10 递归地继续查找键，并把当前匹配到的映射重新加到递归结果中

函数 f 控制实际行为。如果给定键不存在，它会收到 Nothing；如果键存在，它会收到一个包含当前值的 Just。然后这个函数可以返回 Nothing，表示如果该键有值就应当删除；也可以返回 Just，其中包含应当作为映射中更新值的内容。

在空列表的情况下，给定键显然缺失，因此没有值与它关联。此时我们把 Nothing 传给函数 f，然后要么保持列表为空，要么向列表添加一个新的映射。在非空列表的情况下，我们递归查找正确的映射；一旦找到，就检查函数的结果。Nothing 表示删除该映射，而包在 Just 构造器中的值会让我们把更新后的映射加入映射中。为了让类型和值更清楚，我们把自由类型变量命名为 k 和 v，分别表示键（key）和值（value）。

注意 我们可以观察到，在 alter 函数中其实从未真正“修改”关联列表。函数本身会构建一个全新的列表，其中包含我们想要的修改。列表自身是不可变的。这就是 Haskell 的纯函数式特征，也是我们通常处理状态问题的方式。

5.2.1 添加与删除条目（Adding and removing entries）

让我们快速看一下如何用这个函数删除、更新和添加列表中的映射。可以用下面这个简单的关联列表测试它：

ghci> myAssocList = [(1,1), (2,2), (3,3)] :: [(Int, Int)]

删除操作通过让作为参数传入的函数返回 Nothing 来完成。当我们始终返回 Nothing（使用 \x -> Nothing 或 const Nothing）时，就可以用这个函数删除给定键对应的任何映射：

ghci> alter (const Nothing) 1 myAssocList
[(2,2),(3,3)]

如果想添加一个新值，则返回包含该值的 Just 构造器即可：

ghci> alter (const (Just 4)) 4 myAssocList
[(1,1),(2,2),(3,3),(4,4)]

我们也可以只在映射已经存在时更新值。为此可以使用 maybe 函数：如果函数参数是 Nothing，就继续返回 Nothing；如果已经有值，则用 Just 包装更新后的值：

ghci> alter (maybe Nothing (const (Just 0))) 1 myAssocList
[(1,0),(2,2),(3,3)]
ghci> alter (maybe Nothing (const (Just 0))) 4 myAssocList
[(1,1),(2,2),(3,3)]

如果我们不显式检查关联列表中是否已经存在这个值，那么当它不存在时就会自动添加。这个函数很强大，我们可以基于它为关联列表构建许多不同的辅助工具。

练习：另一种 alter 实现

在 3.3.2 节中，我们学习了用于处理 Maybe 值的 maybe 函数。然而，在当前的 alter 实现中，我们使用了手动模式匹配。请尝试重写这个函数，让它改用 maybe。

在把所有这些函数封装成辅助函数之前，我们还想让代码结构更清晰。显然，我们现在定义的不是图函数，而是通用关联列表函数。因此，让我们为这些代码定义一个新模块。

5.2.2 使用导出列表隐藏构造器（Using export lists to hide constructors）

为了更清晰地组织这些功能，我们在 src 目录中新增一个名为 AssocMap 的模块，并移动 member 和 alter 函数。我们会把这个模块放在 src 下的一个子目录 Data 中。这样做是为了表明我们创建的模块用于定义某种数据类型及其相关函数。完成后，项目结构大致如下：

ladder
├── CHANGELOG.md
├── LICENSE
├── README.md
├── Setup.hs
├── app
│   └── Main.hs
├── package.yaml
├── src
│   ├── Data
│   │   └── AssocMap.hs
│   ├── Graph.hs
│   └── Lib.hs
├── stack.yaml
├── stack.yaml.lock
├── test
│   └── Spec.hs
└── test.cabal

这种新结构的目的不只是分离图和关联列表的代码，还要确保代码中的不变量。对我们的映射来说，需要确保每个键只出现一次。理想情况下，我们只希望在映射自己的模块中修改它。否则，我们无法确保其他使用该类型的开发者也遵守这个不变量。他们可能会构造出这样的值：

badAssocMap = [(1,1), (1,2)] :: [(Int, Int)]

这样一来，alter 和 member 就不再正常工作了。因此，我们想以某种方式隐藏这个类型只是一个列表的事实。为此，我们给它一个新类型和自己的构造器：

data AssocMap k v = AssocMap [(k, v)]

这个类型有些特殊，因为它只有一个构造器，而这个构造器又只有一个字段。在这种情况下，我们可以使用另一个关键字来定义类型：newtype。

newtype AssocMap k v = AssocMap [(k, v)]

我们应当使用 newtype 而不是 data，背后有一些技术原因。关于这两个关键字的差异和细节，可以查看附录 B。

注意 在 newtype 定义中，让构造器与类型本身同名是可行的，而且通常也是标准做法。这不是强制要求；如果你愿意，也可以给构造器选择不同的名字。但在较大的项目中，同名会让哪个值对应哪个类型更加清晰。

那么，如何从外部隐藏这个类型的构造器呢？答案是使用模块的导出列表。通过导出列表，我们可以控制模块向外暴露什么，以及隐藏什么。如果想导出某个类型但不导出它的构造器，只需要写下类型名即可。它看起来像这样：

module Data.AssocMap
  ( AssocMap,
    member,
    alter,
  )
where

这里我们导出了 AssocMap 类型以及 member 和 alter 函数。不过，我们没有导出 AssocMap 类型的构造器。如果想同时导出构造器，可以写成 AssocMap(..)，表示导出这个类型的所有构造器。

现在有一个问题：我们的函数是为元组列表写的，而不是为新的 AssocMap 类型写的。我们必须重写它们。这里有两种选择：

1. 在所有处理关联列表的表达式中添加新的构造器。
2. 为每个函数构造一个新类型包装器，在内部继续使用旧的元组列表函数。

第一种选项可以说更标准，因为我们确实想为这个类型定义函数。然而，第二种选项让我们可以从任意作用于元组列表的函数构造出这个类型上的函数。因此，我们选择第二种方式，因为它也让代码更容易阅读。

这也是一个熟悉 Haskell 另一个小巧语法的好机会：where 关键字。我们可以像使用 let 一样，在函数内部用 where 定义局部定义，不同之处在于定义会出现在使用位置之后。图 5.4 展示了这种结构。

图 5.4 where 子句

导出列表、新类型以及对函数的改写如下所示。

代码清单 5.4 AssocMap 的模块结构

module Data.AssocMap
  ( AssocMap,          -- #1
    member,            -- #2
    alter,             -- #2
  )
where

newtype AssocMap k v = AssocMap [(k, v)]    -- #3

member :: Eq k => k -> AssocMap k v -> Bool
member key (AssocMap xs) = member' key xs   -- #4
  where                                     -- #5
    member' :: Eq k => k -> [(k, v)] -> Bool
    member' _ [] = False
    member' x ((x', _) : xs)
      | x' == x = True
      | otherwise = member' x xs

alter :: Eq k => (Maybe v -> Maybe v) -> k -> AssocMap k v -> AssocMap k v
alter f key (AssocMap xs) = AssocMap (alter' f key xs) -- #4
  where                                                -- #6
    alter' :: Eq k => (Maybe v -> Maybe v) -> k -> [(k, v)] -> [(k, v)]
    alter' f key [] =
      case f Nothing of
        Nothing -> []
        Just value -> [(key, value)]
    alter' f key ((key', value') : xs)
      | key == key' =
        case f (Just value') of
          Nothing -> xs
          Just value -> (key, value) : xs
      | otherwise =
        (key', value') : alter' f key xs

• #1 导出 AssocMap 类型，但不导出它的构造器
• #2 导出模块中声明的函数
• #3 基于关联列表定义一个新的映射类型
• #4 解开并重新包装关联列表，在内部使用我们原先定义的函数
• #5 创建可在 where 上方表达式中使用的局部定义
• #6 创建可在 where 上方表达式中使用的局部定义

现在，我们已经把自己的类型和函数从外部世界正确封装起来了。遗憾的是，我们也让这个类型暂时变得不可用。为什么？想想这个问题：如何创建一个新列表？请记住，我们没有用于构建这个类型的构造器，也就是说，我们无法构造任何 AssocMap k v 类型的值。如何绕过这个问题？

我们可以提供一个函数，把关联列表转换成 AssocMap；但更简单的方案是提供一个空映射值，以及用于添加和删除新映射的函数。幸运的是，有了 alter 函数，这些实现会非常轻松。新函数如下所示。

代码清单 5.5 空映射、删除函数和插入函数的定义

empty :: AssocMap k v
empty = AssocMap []                         -- #1

delete :: Eq k => k -> AssocMap k v -> AssocMap k v
delete = alter (const Nothing)              -- #2

insert :: Eq k => k -> v -> AssocMap k v -> AssocMap k v
insert key value = alter (const (Just value)) key -- #3

• #1 定义一个空映射
• #2 定义一个从映射中移除某个键及其值的函数
• #3 定义一个向映射插入或更新某个键对应值的函数

不要忘记把这些新定义加入导出列表：

module Data.AssocMap
  ( AssocMap,
    empty,
    member,
    alter,
    delete,
    insert,
  )
where

现在可以试一下了。把项目加载到 GHCi 中并执行：

ghci> insert 'a' "Hello" (insert 'b' "World" empty)

<interactive>:70:1: error:
    • No instance for (Show (AssocMap Char String))
        arising from a use of 'print'
    • In a stmt of an interactive GHCi command: print it

糟糕！看起来我们又缺少一个类型类。

5.2.3 Show 类型类（The Show type class）

Show 类型类用于提供 show 函数，它可以把 Haskell 类型转换为 String。GHCi 正是使用这个函数来显示它求值出的结果，但我们的类型还没有这个类型类的实例。

警告 show 函数并不是为了提供适合人类阅读的 Haskell 值表示！Show 类型类与 Read 类型类成对出现，后者提供自动生成的 Haskell 值解析器。对大多数类型来说，Show 可以直接自动派生。

幸运的是，我们可以自动推导它。某些类型类（Eq 和 Show 就是其中两个）可以被自动派生，并表现出合理的行为。要为某个类型派生类型类，可以使用 deriving 关键字：

newtype AssocMap k v = AssocMap [(k, v)]
  deriving (Show)

为 Show 派生出的实例会生成看起来很像代码中写出来的值的 String。注意，这只有在映射内部使用的类型本身也有 Show 实例时才有效。

对类型做出这个小改动之后，就可以测试我们的函数了：

ghci> insert 'a' "World" (insert 'b' "Hello" empty)
AssocMap [('b',"World"),('a',"Hello")]
ghci> delete 'a' (insert 'a' "Delete me!" empty)
AssocMap []

顺便说一句，我们也可以为 Eq 派生实例。在这种情况下，相等性（==）由结构等价定义。如果两个值的构造器以及它们的字段都相等，那么这两个值相等。下面是一些例子：

ghci> data X = A | B Int | C Int Int deriving Eq
ghci> A == A
True
ghci> B 1 == B 2
False
ghci> B 1 == B 1
True
ghci> B 1 == C 1 2
False
ghci> C 1 2 == C 2 2
False
ghci> C 1 2 == C 1 2
True

现在，我们定义用于按键查找关联值的函数。毕竟，这就是映射存在的目的。对 lookup 函数，我们使用前面相同的方法：把一个作用于列表的函数包装到新类型上。此外，我们还定义一个在键不存在时提供默认值的函数。稍后这会帮我们省掉一些麻烦。代码见清单 5.6。

我们创建的函数名叫 lookup，它可能与 Prelude 自动导入的 lookup 函数冲突。为了绕过这个问题，可以用下面的导入语句隐藏 lookup：

import Prelude hiding (lookup)

注意 如果我们不想从导入中隐藏某个函数（因为确实想使用它），就必须用模块名作为前缀来引用这些函数。在我们的例子中，那会写成 Prelude.lookup 和 Data.AssocMap.lookup。

代码清单 5.6 基于关联列表的映射查找函数定义

lookup :: (Eq k) => k -> AssocMap k v -> Maybe v
lookup key (AssocMap xs) = lookup' key xs    -- #1
  where
    lookup' _ [] = Nothing                   -- #2
    lookup' key ((key', value) : xs)         -- #3
      | key == key' = Just value             -- #3
      | otherwise = lookup' key xs           -- #3

findWithDefault :: (Eq k) => v -> k -> AssocMap k v -> v
findWithDefault defaultValue key map =
  case lookup key map of
    Nothing -> defaultValue                  -- #4
    Just value -> value                      -- #5

• #1 匹配一个 AssocMap 值，并在其中包含的列表上执行查找
• #2 如果列表为空，则返回 Nothing
• #3 在关联列表中递归查找键，如果找到则返回 Just 值
• #4 如果查找失败，则返回默认值
• #5 返回查找到的值

太好了！我们已经完成了一个基于关联列表的映射模块。通过仔细检查，我们确保模块内部的函数不会破坏“每个键只能出现一次”这个不变量；同时，因为构造器没有从模块导出，映射也不能从模块外部被“弄坏”。因此，外部既不能对这个类型进行构造，也不能对它进行模式匹配。现在，我们可以基于这个新的映射定义来实现图。

5.3 使用与复用代码（Using and reusing code）

在 Graph 模块中，我们可以导入新的映射数据类型。但请记住，它导出了一个名为 lookup 的函数，会与 Prelude 中的 lookup 冲突。对我们来说这是个问题；而在更大的项目中，某个模块可能会导入数百个其他模块，这类问题只会更加明显。

5.3.1 限定导入（Qualified imports）

解决 lookup 问题的一种优雅方式是使用限定导入。这样的导入看起来如下：

import qualified Data.AssocMap as M

这会导入 Data.AssocMap，并把它命名为 M，因为我们不想每次都写完整模块名。qualified 关键字要求我们在引用这个模块中的函数和定义时，必须给名称加上模块前缀。这意味着我们不能直接使用 alter 这样的定义，而必须写成 M.alter。由于每个导入都有唯一名称，我们就避免了命名冲突，也让某些定义来自哪个上下文更加清楚。

现在，让我们使用这些导入来编写有向图的定义。首先定义类型和空图：

type DiGraph a = M.AssocMap a [a]

empty :: DiGraph a
empty = M.empty

接下来，需要提供以下功能：

• 向图中添加一条边
• 向图中添加多条边
• 获取某个节点连接到的所有节点

添加边可以通过修改映射完成。如果条目尚不存在，就添加这个节点，并让它的连接节点列表只包含新的子节点。否则，就把子节点添加到原有的连接节点列表中。唯一需要注意的是确保连接节点列表中没有重复值。我们可以通过删除所有重复值来做到这一点；幸运的是，Data.List 模块中已经存在一个执行此操作的函数，叫作 nub。

ghci> import qualified Data.List as L
ghci> L.nub [1,1,1,2,3,4,1,1,1,2,3,4] :: [Int]
[1,2,3,4]

现在可以构造添加边的函数。如果节点不存在于图中，它会被加入图中。否则，连接节点列表会扩展为包含新的连接节点，并删除重复项。添加多条边也并不复杂，只需要对每条应当添加的边调用添加单条边的函数即可。此外，我们还想定义一个函数，把节点及其节点列表组成的关联列表转换成图，其实现与添加多条边类似。从某个节点获取所有连接节点就是在映射中做一次简单查找。如果找不到该节点，就返回空列表，因为缺失节点没有连接节点。下面的代码给出了这些函数。

代码清单 5.7 向有向图添加边并获取连接节点的函数

import qualified Data.List as L       -- #1

...

addEdge :: (Eq a) => (a, a) -> DiGraph a -> DiGraph a
addEdge (node, child) = M.alter insertEdge node -- #2
  where
    insertEdge Nothing = Just [child]           -- #3
    insertEdge (Just nodes) =
      Just (L.nub (child : nodes))              -- #4

addEdges :: (Eq a) => [(a, a)] -> DiGraph a -> DiGraph a
addEdges [] graph = graph                       -- #5
addEdges (edge : edges) graph = addEdge edge (addEdges edges graph) -- #6

buildDiGraph :: (Eq a) => [(a, [a])] -> DiGraph a
buildDiGraph nodes = go nodes M.empty
  where
    go [] graph = graph
    go ((key, value) : xs) graph = M.insert key value (go xs graph) -- #7

children :: (Eq a) => a -> DiGraph a -> [a]
children = M.findWithDefault []                 -- #8

• #1 导入 Data.List 模块
• #2 修改构成图的映射
• #3 如果节点不存在于图中，新子节点会构成连接节点列表，并且该节点会被添加到图中
• #4 将节点加入其他连接节点，并移除所有重复项
• #5 如果没有要添加的内容，则返回未改变的图
• #6 递归地向图中添加所有边
• #7 递归地向图中添加所有“节点到连接节点列表”的映射
• #8 返回某个节点的连接节点；如果该节点不存在，则返回空列表

现在，我们已经有了一些可用于处理有向图的函数。来看几个例子：

ghci> import Graph
ghci> g = addEdges [(1,1), (1,2), (3,2), (3,1)] Graph.empty
ghci> children 3 g :: [Int]
[2,1]
ghci> children 2 g :: [Int]
[]
ghci> children 2 (addEdge (2,1) g) :: [Int]
[1]

这个实现的一个优点是，它完全独立于底层映射实现。只要另一个类型拥有兼容的相关函数，我们就可以用它替换 AssocMap 类型。

练习：泛化函数

仔细观察图函数时，可以看到 addEdges 和 buildDiGraph 的实现非常相似。请尝试泛化这两个函数，提供一个具有类似列表处理结构的高阶函数，并把这个函数应用到两个定义中。此外，我们还没有提供从图中删除节点和边的函数。请自行实现这些函数。

现在，我们可以自信地说，已经学会如何构建图了。带着这些知识，让我们终于开始组装单词阶梯图。

5.3.2 为排列构建映射（Building maps for permutations）

回顾一下，单词阶梯图包含给定词典中的所有单词，并在所有能够通过单词阶梯游戏一步到达的单词之间建立边。一步可以是以下任意转换的组合：

• 向单词添加一个字母
• 从单词中删除一个字母
• 任意重新排列单词中的所有字母

转换结果必须仍然是一个单词，并且存在于单词阶梯游戏所基于的词典中。这带来了计算挑战！对每一个可能的单词，我们都必须搜索整个词典。由于可以任意重新排列单词，从给定单词出发需要检查的单词数量具有阶乘级时间复杂度。对于较长的单词来说，这是个问题。

如果有某种缓存或过滤器，可以快速告诉我们哪些排列有效、哪些无效，那就很有帮助。理想情况下，我们根本不想计算某个单词的所有排列。但该怎么做到呢？假设我们想扫描一次词典，目标是存储每个单词的排列。这些排列有什么共同属性？它们都由相同字母组成！因此，把它们排序之后，它们就是相同的。我们可以扫描词典，通过对每个单词排序来创建一个键，然后把这个单词存储到该键关联的列表中。对每个单词都这样做，就能创建一个映射，把单词与词典中有效的排列关联起来。

我们可以在一个新模块中实现这种排列映射（permutation map），模块名为 PermutationMap。这个类型是从字符串（排列的排序表示）到其有效排列的映射：

type PermutationMap = M.AssocMap String [String]

这个映射上的操作与 AssocMap 相同，但我们需要确保每当操作键时，都先对键排序。可以使用 Data.List 模块中的 sort 函数来完成。这里我们再次对 Data.AssocMap 和 Data.List 使用限定导入；此外，还导入 Data.Maybe 模块。不过，对于 Data.Maybe，我们只想导入单个函数，这可以通过导入列表完成。这种列表类似于导出列表，用于限制被导入的定义。该模块代码如下。

代码清单 5.8 排列映射模块

module PermutationMap
  ( PermutationMap,
    empty,
    member,
    alter,
    delete,
    insert,
    lookup,
    findWithDefault,
    createPermutationMap,
  )
where

import qualified Data.AssocMap as M      -- #1
import qualified Data.List as L
import Data.Maybe (fromMaybe)
import Prelude hiding (lookup)           -- #2

type PermutationMap = M.AssocMap String [String] -- #3

empty :: PermutationMap
empty = M.empty                           -- #4

member :: String -> PermutationMap -> Bool
member key = M.member (L.sort key)        -- #5

alter ::
  ( Maybe [String] ->
    Maybe [String]
  ) ->
  String ->
  PermutationMap ->
  PermutationMap
alter f key = M.alter f (L.sort key)      -- #5

delete :: String -> PermutationMap -> PermutationMap
delete key = M.delete (L.sort key)        -- #5

insert :: String -> [String] -> PermutationMap -> PermutationMap
insert key = M.insert (L.sort key)        -- #5

lookup :: String -> PermutationMap -> Maybe [String]
lookup key = M.lookup (L.sort key)        -- #5

findWithDefault :: [String] -> String -> PermutationMap -> [String]
findWithDefault defaultValue key map =
  fromMaybe defaultValue (PermutationMap.lookup key map) -- #6

• #1 以限定方式导入模块，并从 Data.Maybe 模块导入单个函数
• #2 导入不包含 lookup 函数的 Prelude，避免命名冲突
• #3 将 PermutationMap 类型定义为 AssocMap 类型的别名
• #4 定义空排列映射
• #5 包装来自 AssocMap 的通用函数，在访问映射前先对键排序，从而用于排列映射
• #6 提供带默认值的查找

本质上，PermutationMap 类型只是 AssocMap 的一个特化版本。多亏我们的多态实现，我们可以自由使用具体类型。而且，就像 Graph 一样，PermutationMap 类型也完全独立于映射的具体实现。

练习：字符串排序

查看 sort 函数的类型表达式。为什么我们可以把这个函数用于 String 值？为什么可以在新模块中使用来自 AssocMap 的多态函数？请尝试用 GHCi 检查类型（:type 和 :info），弄清楚这些类型为什么兼容。

接下来，我们想构造一个函数，接收单词列表并从中构建排列映射。为此，可以假设所有单词都是小写。每个单词都需要被添加到映射中。我们预期会有多个单词共享同一个键（因为这正是我们查找某个单词所有排列的方式），所以添加单词时，必须把它们加入该键指向的列表中。实现代码如下。

代码清单 5.9 从字符串列表构造排列映射的函数

createPermutationMap :: [String] -> PermutationMap
createPermutationMap = go empty           -- #1
  where
    go permMap [] = permMap               -- #2
    go permMap (x : xs) = go (insertPermutation x permMap) xs

    insertPermutation word = alter (insertList word) word -- #3

    insertList word Nothing = Just [word] -- #4
    insertList word (Just words) = Just (word : words)

• #1 使用空映射调用辅助函数 go
• #2 定义一个辅助函数，用于把每个单词添加到映射中
• #3 修改映射，使用单词作为键，并用一个函数把单词加入可能已经存在的值中
• #4 定义一个函数：如果映射中缺少该键，则创建包含单个单词的列表；否则把单词加入已有列表

这个实现与清单 5.7 中的 addEdges 函数非常相似，但这次我们没有把函数拆开，而是用 where 把所有必要定义保留为局部定义。我们还可以观察到，go 函数的机制似乎很熟悉。事实上，已经有一个函数具有完全相同的行为，不过我们会等到第 8 章再介绍它。

5.3.3 从字典创建排列映射（Creating a permutation map from a dictionary）

现在可以测试这个新函数了：

ghci> words = ["traces", "reacts", "crates", "caster", "tool", "loot", "cat"]
ghci> pm = createPermutationMap words
ghci> pm
AssocMap [("acerst",["caster","crates","reacts","traces"]),("loot",["loot","tool"]),("act",["cat"])]
ghci> PermutationMap.lookup "tool" pm
Just ["loot","tool"]
ghci> PermutationMap.lookup "reacts" pm
Just ["caster","crates","reacts","traces"]

可以看到，每个单词都会和它排序后的形式关联起来。构建映射后，我们就能快速取回原始单词列表中存在的所有排列。与其计算某个单词的全部排列并逐个检查，不如在映射中做一次简单查找。

5.4 转换参数化（Parameterizing transformations）

现在，我们已经有了一个在计算上可管理的方案，可以开始构建单词阶梯图了。为此，我们再创建一个模块，名为 Ladder，其中包含专属于这个用例的函数。首先，我们为单词列表定义一个类型：

type Dictionary = [String]

这样做是为了区分词典和普通字符串列表的用法。我们假设词典中包含的单词只使用小写字母。现在，可以编写一个 IO 动作，读取包含单词的文件，并把它解析为词典。我们已经知道如何把文件按行拆分，但还需要过滤词典条目，使其只包含小写字母。可以使用 Data.List 模块中的 filter 函数做到这一点。这个函数接收一个类型为 a -> Bool 的函数，这个函数作为列表元素上的布尔谓词。只有让该谓词返回 True 的元素会出现在结果中。下面是例子：

ghci> filter (\x -> x <= 5) [1..10]
[1,2,3,4,5]
ghci> filter even [1..10]
[2,4,6,8,10]

使用这个函数，可以通过检查每个字符是否属于小写拉丁字母，把字符串过滤成只包含小写字母：

ghci> filter (\x -> x `elem` ['a'..'z']) "hello world."
"helloworld"

这可以帮助我们过滤掉其他字符。此外，我们还需要移除重复项，这可以用 nub 函数完成。实现这些功能的代码如下。我们还为 Data.List、Graph 和 PermutationMap 模块创建限定导入。

代码清单 5.10 从文件路径读取词典的 IO 动作

module Ladder
  ( Dictionary,
    readDictionary,
  )
where

import qualified Data.List as L
import qualified Graph as G
import qualified PermutationMap as PM

type Dictionary = [String]

readDictionary :: FilePath -> IO Dictionary
readDictionary filepath = do
  dictionaryContent <- readFile filepath  -- #1
  let
    lines = L.lines dictionaryContent     -- #2
    words = L.map (L.filter (`L.elem` ['a' .. 'z'])) lines -- #3
  return (L.nub words)                    -- #4

• #1 读取文件内容
• #2 把文件内容拆分成表示各行的字符串列表
• #3 过滤每一行，使其只包含小写字母
• #4 返回去重后的过滤单词

这里我们也看到，如何对函数（这里是 L.elem）使用中缀表示法，并通过 η 化简去掉 lambda 抽象。

现在，我们想使用词典中的单词生成单词阶梯图。为此，需要计算某个单词所有可能的变化（添加字母、删除字母和修改一个字母），并使用由词典自身构建的排列映射来计算新形成单词的所有有效重排。我们可以用 buildDiGraph 函数，通过为词典中的每个单词计算所有有效的新单词，构建出节点及其对应边的列表。假设已经有一个函数 computeCandidates，它能为给定单词返回所有可能候选项，那么完整函数如下。

代码清单 5.11 从词典构建单词阶梯图的函数

mkLadderGraph :: Dictionary -> G.DiGraph String
mkLadderGraph dict = G.buildDiGraph nodes -- #1
  where
    map = PM.createPermutationMap dict     -- #2
    nodes =
      L.map (\w -> (w, computeCandidates map w)) dict -- #3

• #1 根据词典中的单词以及它们在单词阶梯游戏中的相关单词构建有向图
• #2 从词典构建排列映射
• #3 把每个单词映射为它自身以及它在单词阶梯游戏中的相关单词

不过，我们还没有 computeCandidates 函数，需要处理它。给定一个单词，我们首先需要向它添加任意字母，然后使用排列映射获取所有有效排列。这让工作稍微简单一些，因为我们不关心新字母具体添加到哪里。如何向字符串添加新字母？一种可能是使用 map 函数：

ghci> map (\x -> x : "word") ['a' .. 'z']
["aword","bword","cword","dword","eword","fword","gword","hword","iword","jword","kword","lword","mword","nword","oword","pword","qword","rword","sword","tword","uword","vword","wword","xword","yword","zword"]

删除一个字母同样可以通过 map 完成，因为可以遍历单词本身，并用 Data.List 模块中的 delete 函数从单词中删除每个字母。注意，这个函数只会删除第一个出现的待删除元素：

ghci> map (\x -> delete x "word") "word"
["ord","wrd","wod","wor"]

同样，我们不关心具体删除了哪个字母，因为排列映射在查找时无论如何都会对单词排序。为了计算把单个字母替换成另一个字母得到的单词，现在需要把两个操作结合起来。这是因为我们不想把刚刚删除的同一个字母再添加回单词。不过，直接写出来可能稍显繁琐，所以我们会使用另一种列表语法：列表推导。

5.4.1 列表推导（List comprehensions）

列表推导让我们能够以非常简单的方式写出列表定义。一个列表推导有两部分：左侧指定如何构建列表元素，右侧包含所谓的生成器和守卫。

下面是几个例子：

ghci> [ x + 1 | x <- [1..10] ] :: [Int]
[2,3,4,5,6,7,8,9,10,11]
ghci> [ x + 1 | x <- [1..10], x <= 5 ] :: [Int]
[2,3,4,5,6]

可以看到，左侧表达式会针对生成器中满足守卫的每个元素求值。使用多个生成器时，左侧表达式会针对这些生成器元素的笛卡尔积求值：

ghci> [ (x, y) | x <- [1,2], y <- ['a', 'b', 'c']] :: [(Int, Char)]
[(1,'a'),(1,'b'),(1,'c'),(2,'a'),(2,'b'),(2,'c')]

我们可以使用这些推导式构造单词的修改形式。对给定的 word，可以这样计算可能的新单词：

added = [x : word | x <- ['a' .. 'z']]
removed = [delete x word | x <- word]
modified =
  [x : delete y word | x <- ['a' .. 'z'], y <- word, x /= y]

这里可以看到，列表推导可以结合 map 和 filter 的功能。此外，它还提供了一种通过笛卡尔积组合列表的方式。由于可以使用任意数量的生成器，这种写法可以扩展到任意维度。用这种方式编写列表定义，通常能让定义更短，也可以说更容易阅读。不过，这很大程度上是个人偏好。

注意 列表推导也可以用于模式匹配。生成器中的失败模式匹配会被视为跳过该值。这样，你可以像这样定义 catMaybes 函数：catMaybes xs = [ x | Just x <- xs ]。任何不匹配 Just x 的值都会被丢弃。

现在，我们可以使用刚刚得到的定义完成函数。此外，可以删除排序后单词中的所有重复项，从而减少映射查找次数。最后，在最终结果中还应当移除原单词，因为单词阶梯游戏中的一步应该改变单词。完整源代码如下。

代码清单 5.12 计算游戏下一步有效候选项的函数

computeCandidates :: PM.PermutationMap -> String -> [String]
computeCandidates map word =
  let candidates = modified ++ removed ++ added ++ [word]
      uniques = L.nub [L.sort w | w <- candidates]      -- #1
      perms = L.concatMap (\x -> PM.findWithDefault [] x map) uniques -- #2
   in L.delete word perms                                -- #3
  where
    added = [x : word | x <- ['a' .. 'z']]               -- #4
    removed = [L.delete x word | x <- word]              -- #5
    modified =
      [x : L.delete y word | x <- ['a' .. 'z'], y <- word, x /= y] -- #6

• #1 对所有可能候选项排序，并从中移除重复项
• #2 为每个可能候选项计算有效排列
• #3 从有效候选项中移除原单词
• #4 计算向原单词添加单个字母得到的字符串
• #5 计算从原单词删除单个字母得到的字符串
• #6 计算把某个字母替换为另一个字母得到的字符串

这里有一个尚未见过的函数：concatMap。它做什么？这个函数与 concat 紧密相关。concat 只是接收一个列表的列表并将其展平，通过连接内部列表创建一个包含所有元素的单个列表。concatMap 则是先执行 map，再执行 concat 的组合。当 map 函数的结果本身是列表，而你想把所有这些列表中的元素组合成一个列表时，它非常有用。由于这种情况相当常见，该函数已经预定义好了：

ghci> concat [[1,2,3], [4,5,6]] :: [Int]
[1,2,3,4,5,6]
ghci> concat ["Hello", " ", "World"] :: String
"Hello World"
ghci> concatMap (\x -> [1..x]) [1..5] :: [Int]
[1,1,2,1,2,3,1,2,3,4,1,2,3,4,5]

现在，我们可以为给定词典构造单词阶梯图了。来看一个小例子：

ghci> mkLadderGraph ["cat", "cats", "act", "dog"]
AssocMap [("dog",[]),("act",["cat","cats"]),("cats",["act","cat"]),("cat",["act","cats"])]

这里，我们为函数提供了包含四个单词的词典。可以看到，cat、cats 和 act 这几个单词都可以在一步之内互相到达，而 dog 无法从任何节点到达，并且在图中没有邻居。现在，我们已经能够构造用于搜索解的结构，可以继续处理人工智能核心中的挑战：搜索问题。

总结

• 代数数据类型可以包含自由类型变量，这可以让数据结构容纳任意类型。
• 模块名必须与项目中文件的路径保持一致。
• Eq 类型类用于提供比较值是否相等的函数（(==) 和 (/=)）。
• flip 函数用于翻转二元函数的参数。
• 高阶函数可以根据接收到的函数参数完全改变自身行为。
• 我们可以在模块导出列表中排除某个类型的构造器，使模块外部无法创建该类型的值。
• Show 类型类提供 show 函数，用于把 Haskell 值转换为字符串。
• 限定导入会强制我们在使用某个模块中的定义时带上模块名（或别名）。
• 列表推导提供了一种特殊语法，用于过滤、映射和组合列表。