第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。我们的人工智能必须能够在这种阶梯图中找到最短的解，我们姑且这么称呼它。
我们可以快速勾勒出程序应该做的事情：
- 从用户那里读取起始单词和结束单词。
- 根据词典构建一个阶梯图。
- 在阶梯图中搜索从一个单词到另一个单词的最短路径。
幸运的是，寻找这种最短路径的问题在计算机科学中已被广泛研究，所以这应该不成问题。真正的问题在于，我们首先需要计算出这样一个阶梯图才能找到解。这让我们思考：如何在 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 <类名>来做到这一点。
现在我们知道如何使用类型类，我们可以解决构建图的更大问题。我们应该考虑可以在模块中添加哪些函数来帮助我们处理关联列表。