第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 的解决方案

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