Haskell入门教程：4 寻找梯子

• 将图形结构建模为地图
• 应用类型约束以确保有关类型的属性
• 将数据类型和函数正确封装在模块中
• 使用列表推导式更轻松地转换列表
• 设计正在处理复杂状态的算法
• 分析和改进计划绩效

我们的上一个项目是一个流行的UNIX工具的最小克隆。严肃的生意！但生活不仅仅是为我们所有的终端线路编号需求编写工业级实用程序。让我们玩得开心吧！人们通常如何玩得开心？当然是通过玩游戏！

一个有趣的小游戏是单词梯子游戏，它使玩家构建单词链，可以通过转换其中的单个字母来找到这些单词链。游戏有很多变体，我们将专注于一个非常复杂的变体！但是，当我们可能有点懒惰时，为什么要玩游戏呢？电脑可以为我们播放！

编写人工智能，即使是儿童游戏，也并不总是小菜一碟。这个项目将让我们思考如何巧妙地使用数据结构，以便实现搜索问题的解决方案。虽然表面上看起来很简单，但我们会发现可能存在陷阱，即使在儿童游戏中也是如此！

本章首先讨论使用 Haskell 类型建模图以及如何创建我们自己的模块。然后，我们将探讨类型类的基础知识，它们是什么，它们做什么以及如何使用它们。然后，我们使用关联列表为映射创建一个特殊的数据类型，并使用模块导出列表来正确确保数据类型的不变量。通过使用地图，我们为图形创建数据类型，并为列表中的单词排列创建查找表。然后，我们对有向图实现广度优先搜索，并在将所有内容放在一起后，将通过分析我们的程序并提高其性能来结束本章

天梯游戏是一项有趣的练习，需要玩家真正深入挖掘他们的词汇知识。这个游戏的一轮可以由任意数量的玩家玩，并且规则明智地存在它的许多变体。让我们先看一下最简单的变体，然后讨论如何为游戏开发人工智能。

玩家以两个相同长度的单词开头。其中一个可以被认为是开始，另一个可以被认为是结束。要解决的任务是找到将起始词链接到结束词的其他单词链，其中每对相邻的单词相差一个字母。这意味着玩家从一个单词开始，更改单个字母以到达一个新单词，并继续这些转换，直到找到从头到尾的完整链。如果有多个玩家在玩游戏，则链条最短的玩家获胜。

这是一个例子：猫→坐在下垂→→达格→狗

这是一个有趣的游戏，但对于计算机来说，这是一个相当微不足道的练习，我们很快就会看到。事实上，这是一个经典的搜索问题。为了找到解决方案，我们需要搜索一个域（一堆单词）以查找从一个元素到另一个元素的路径。这种问题在很多方面蔓延：

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

通过解决单词梯子游戏，我们学习了一种可以转移到任何其他学科的技能。对于计算机来说，无论我们搜索什么，搜索都是一样的！区别在于解决方案的建模方式。对我们来说，单词由于游戏中的某些规则而相互连接，但在导航系统中，路径是由地图数据给出的。一旦这个抽象层被移除，问题就会变得相同！

为了使这个问题不那么简单，我们会让事情变得更加复杂：我们不仅允许玩家更改单个字母，还允许添加一个全新的字母，删除一个字母，并任意重新排序字母。对游戏的这种修改使其更加有趣，因为现在可以在不同长度的单词之间找到路径！因此，现在可以为“查找”和“解决方案”这两个词找到解决方案（例如，找到→鳍→离子→腰部→扁桃体→乳液→溶液）。分步解决方案如图4.1所示。

这种修改不仅使我们能够找到更具创造性的解决方案，而且使问题更难在计算上解决。在解决这个问题时，我们需要开始考虑性能和一种聪明的方法来最大限度地减少我们不必做的工作。

现在，我们可以开始思考如何为这种游戏构建人工智能了。我们假设我们的智力以某种方式拥有所有英语单词的完整列表。如果它想找到一个有效的链，它需要找到一个单词到另一个单词的路径，并具有有效的转换。为此，我们可以假设所有单词都排列在图中，其中两个单词之间存在边缘，当且仅当我们可以在一个步骤中从一个单词到达另一个单词时，单个单词是图形中的一个节点。图4.2显示了几个三个字母的单词的图表。正如我们所看到的，找到从“猫”到“狗”的链可以通过在这个图中找到一条路径来完成。

我们立即看到从“猫”到“狗”的路径有多条。一种解决方案可能是用猫→帽子→加热→治愈→拿着→救济金→→狗→狗。但是，这不是最短的解决方案！较短的可能是猫→猫→标签→山羊→→狗。我们的人工智能必须能够在我们称之为梯形图的梯形图中找到最短的解决方案。

我们可以快速规划出我们的程序应该做什么：

1. 从用户那里读取开头和结尾单词
2. 从字典构建梯形图
3. 在梯形图中搜索从一个单词到另一个单词的最短路径

幸运的是，寻找这种最短路径的主题已经在计算机科学中得到了广泛的研究，所以这应该不是问题。问题是，我们首先需要计算这样一个梯形图来找到解决方案。这应该让我们思考：我们如何在 Haskell 中表示图形？

让我们回顾一下什么是图表。图形由节点和边组成，而节点和边又连接这些节点。边可以是定向的（因此路径只能从一个节点构造到另一个节点，而不能构造相反）或无向。此外，边缘可能有成本，但对于我们的问题，我们可以忽略这些成本。我们一视同仁地对待路径中的每个边缘，一条边缘代表阶梯游戏中的一步。这为我们提供了许多可能性，可以将这个概念表示为 Haskell 类型。首先，我们想在图表中存储什么样的元素？元素将具有什么类型？我们可以选择一个固定类型，但真的没有必要这样做。通常，图中元素的类型是不明确的，因此我们将它保留为多态类型：

type Graph a = ...

这将使我们能够更灵活地使用可以在图形中使用的类型，但是图形是如何建模的呢？由于我们正在处理无向图并且边没有成本，因此我们只对存储两个节点连接的信息感兴趣。这可以通过使用邻接列表来实现。这样的列表包含所有连接的节点对。在上一章中，我们已经遇到了一种可以表示这种数据结构的类型：关联列表！

type Graph a = [(a,a)]

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

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

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

可悲的是，如果我们想表示无向图，这种类型有一个缺点。添加单个无向边，需要我们在地图中添加两个元素！在具有两个相互连接的节点的简单无向图的情况下，节点 1 和 2 的值看起来像 [（2， [1]）、（1， [2]）]。

现在让我们从这种类型开始，因为有向图适合我们的搜索问题（我们将在后面看到）。我们要创建的不仅仅是此类型，还包括可用于处理此类型的函数集合。为此，我们希望将所有这些功能捆绑在自己的模块中！让我们从创建一个新项目开始。我们称这个梯子！

使用堆栈新梯创建新项目后，我们现在将在 src 目录中创建一个新文件，该文件将成为我们图形类型的新模块。让我们称该文件为 Graph.hs 。这将是我们所有图相关定义的模块。每个模块都以一个小序言开头，如下所示：

module Graph where

模块名称必须与文件名保持一致，这一点很重要。

此外，模块可以捆绑在源目录的子目录中。如果模块包含在类似 Foo/Bar/Module.hs 的路径中。名称需要像这样反映这一点：Foo.Bar.Module 。子目录名称通常大写。

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

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

故意省略了此函数的类型表达式，以让我们思考此类型应该是什么样子。我们想为一般关联列表定义一个函数（稍后使用图类型的定义）。这让我们得出结论，关联列表和搜索元素的类型必须是多态的：

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

这个表达似乎很有道理。键和搜索的元素需要是相同的类型，而元组中的第二个元素可以是任何其他类型。但是，如果我们尝试将此类型分配给函数并编译我们的代码（例如，使用堆栈 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] ）

为了理解这个难题，我们需要快速进入类型类的主题。一直以来，我们一直在与他们合作，而我们却不知道！但它们是什么？

让我们通过提出一个简单的问题来开始讨论：类型具有哪些属性？类型本身只是值集合的名称（在极少数情况下甚至没有值）。但是，仅仅因为一个值是某种类型的，我们不一定知道我们可以对它执行什么样的操作。在大多数语言中，某些类型隐含了一些操作，例如 C 或 Java 中的相等运算符 ==，它是为原始数据类型定义的。但是，在Haskell中，我们更明确地定义了类型的操作。这是通过类型类完成的。它们包含需要为此类的实例定义的值的签名。我们可以像这样用GHCi检查这一点：

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

这个输出告诉我们 Eq 类型类定义了两个方法，一个用于相等 （ == ），一个用于不等式 （ /= ）。但是，此类类型的实例只需要提供其中一个的实现，由 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 类型类的实例，则 May a 和 [a] 也是如此。这意味着也许 Float 和 [Int] 也可以进行比较！

类型类的词汇与面向对象编程有一些重叠。但是，这些概念永远不应该混淆！类型类不能实例化为对象，并且方法的行为与类方法不同，因为它们的实现可能因类型而异！类型类与面向对象上下文中的接口的关系比类更多。

从相等运算符的类型签名（→ → Bool），我们也可以立即推测我们只允许比较相同类型的值。因此，例如，我们无法将 Int 与浮点数进行比较！

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

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

约束指定对于我们使用的多态类型必须保留哪些属性。请注意，在显式命名类型时（例如使用 Int ），我们不需要添加约束，因为已经知道此类型具有哪些实例。另请注意类型类的方法如何隐式附带自己的类型约束：

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

如果要使用 （==），多态类型需要有一个 Eq 类型类的实例！这就是为什么我们会收到编译错误的原因！

有时，我们故意省略了类型表达式，以便编译我们的一些函数。我们这样做了，所以Haskell会自己找出约束。类型推断足够强大，至少在大多数情况下是这样。

现在我们已经完成了偏移，我们终于可以实现向图形添加新节点的函数了！为了使命名更清晰，我们定义了一个新函数hasNode，它只是成员的别名，其参数翻转。用于向图形添加新节点的功能现在只需检查节点是否已存在，如果没有，则添加没有传出边的节点。示例 4.2 中给出了此代码。

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

请注意函数的参数顺序。hasNode 有目的地将图形作为其第一个参数，以便可以用中缀符号编写。为了翻转这些参数，我们使用一个名为flip的函数：

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

这个函数接受一个二进制函数，并生成一个参数翻转的函数！请注意 a 和 b 是如何作为函数的参数的，通过使用部分函数应用程序，使用单个二进制函数的翻转将导致 b 类型的新函数→ a → c ！

Data.List 模块（以及始终导入的 Prelude）已经提供了一个在称为 lookup 的关联列表中查找键的功能！使用它重写成员函数！

另外，请查看类型表达式。我们必须在我们定义的每个函数中添加 Eq 的类型约束。如果我们想对类型变量（在我们的例子中为 a）使用具有类型约束的函数，我们还必须将所述约束添加到我们的函数类型中，因为我们不能对函数内部的类型应用约束（通过使用具有类型约束的函数），但也不能对暴露在外部的类型表达式上施加此约束。

到目前为止，我们的讨论只围绕着 Eq 类型类。当然，还有更多像 Ord 类型类，它为我们提供了排序的定义（例如 （<） 和 （>） ） 和 Num，它是数字类型的类型类并定义了某些算术运算（例如 （ ） ， （-） ， 否定）。虽然我们可以花费大量时间来探索 Haskell 开箱即用提供的所有课程，但我们只会在它们出现后讨论这些课程！

有时，您会遇到函数，这些函数在其类型约束中具有以前从未见过的某些类型类。为了了解这个类，它有哪些方法和实例，我发现最快的方法是使用 GHCi 来检查这个类。您可以使用 ghci> ：i <类的名称> 来执行此操作。

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

为了构建我们的图，我们要添加一个名为 addEdge ，它将节点之间的单个边添加到我们的图。为此，我们需要检查起始节点是否已经存在于图中。要么我们必须将此节点添加到图形中，其中包含仅包含结束节点的新边列表，要么该节点已经存在，我们必须修改边列表。无论如何，我们需要以某种方式改变地图。为了方便起见，我们希望创建一个新函数来对地图执行任意更改。理想情况下，它应该能够添加新元素，删除它们并修改某个键的值。在这种情况下，一个好主意是使用高阶函数，因为这个函数可以为我们的值提供修改，但是我们需要一种方法来告诉函数缺少一个值，并且该函数需要一种告诉我们的方式，它想要删除一个值。幸运的是，两者都可以通过我们已经知道的类型来实现：也许！类型函数（也许是→也许 a）通过将 Nothing 解释为缺失值或希望删除该值来实现此目的！

我们可以递归地实现 alter 函数，如清单 4.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 #4 | otherwise = (key', value') : alter f key xs #9

为了使类型和值更清晰一些，我们将自由类型变量 k 和 v 称为键和值。虽然一开始有点令人生畏，但这个功能非常简单。在空列表的情况下，给定的键丢失，因此没有与之关联的值。在这种情况下，我们提供函数 f a Nothing，要么将列表保留为空，要么向列表中添加新映射。这样，该函数可以添加新的映射！在非空列表的情况下，我们递归搜索正确的映射，一旦我们再次找到它，就会检查函数的结果。没有任何意义，我们删除映射，而包装在 Just 构造函数中的值意味着对现有映射的更新。

我们可以观察到，我们从未真正“修改”过 alter 函数中的关联列表。该函数本身构建了一个全新的列表，其中包含我们想要的修改。列表本身是不可变的。这是Haskell的纯粹方面，也是我们处理国家问题的一般方式！

让我们快速看一下如何使用此函数在我们的列表中删除、更新和添加映射。我们可以在清单 4.4 中看到我们的函数在起作用。

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

这是一个强大的函数，我们可以从中为我们的关联列表构建许多不同的有用实用程序！

在第 3.3.2 节中，我们了解了 may 函数，用于处理 可能值。但是，在 alter 的实现中，我们采用了手动模式匹配。重写函数以改用！

在添加所有这些函数之前，我们希望在代码中加入更好的结构！显然，我们不是在定义图的函数，而是在定义一般的关联列表。因此，让我们为我们的代码定义一个新模块！

为了更干净地捆绑我们的功能，我们在 src 目录中的代码中添加了一个名为 AssocMap 的新模块，并添加了成员和更改函数。我们将这个模块放在一个子目录中 src ，我们称之为 数据 .我们这样做是为了表示我们正在创建的模块用于定义数据类型的类型和函数。这样做的目的不仅仅是为我们的图形和关联列表提供单独的代码，而且还要确保代码的不变性。对于我们的地图，我们需要确保每个键只出现一次！理想情况下，我们只想在它自己的模块中对此映射执行修改。否则，我们无法确保使用我们类型的其他开发人员也确保此不变性保持为真！因此，我们想以某种方式隐藏此类型只是一个列表的事实。为了实现这一点，我们给它一个带有自己的构造函数的新类型：

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

这种类型相当特殊，因为它只包含一个构造函数，而构造函数又只有一个字段。在这种情况下，我们可以使用另一个关键字来定义名为 newtype 的类型：

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

我们构造的新类型具有性能影响，因为它告诉编译器字段中的值与构造函数中包装的值之间存在一对一的对应关系。因此，在类型检查后可以省略构造函数！我们的 newtype 中的类型构造函数在编译后成本为零，因为它根本不存在。这也对更深层次有一些影响，因为新类型定义不如数据定义懒惰。有关更详细的说明，请查看附录B！

可以（也是标准做法）将 newtype 或数据定义中的构造函数命名为与类型本身相同的名称。这样做不是强制性的，如果您愿意，您可以随时为构造函数选择不同的名称，但在较大的项目中，它使哪个值与哪种类型相关联变得更加清晰！

那么，我们现在如何从外部隐藏这种类型呢？答案以模块导出列表的形式提供给我们。有了它，我们可以控制从模块导出的内容以及保持未知的内容！如果我们想导出一个没有构造函数的类型，我们只需写下类型的名称。它看起来像这样：

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

如果我们想导出构造函数，我们也会编写 AssocMap （..） 。

我们现在遇到的一个问题是，我们的函数不是为我们的新类型编写的，而是为简单的关联列表编写的。我们需要重写它们！我们有两个选择：

1. 将新构造函数添加到处理关联列表的每个表达式中
2. 使用列表中的旧函数为新类型的每个函数构造一个包装器

第一个选项可以说更规范，因为我们想为这种类型定义函数。但是，第二个选项允许我们从元组列表上的任何函数构造该类型的函数！因此，我们将选择第二个选项，因为它也使代码更易于阅读。

这也是习惯Haskell的另一个简洁语法的好机会：where关键字。就像我们可以使用 let 关键字在函数中定义内部定义一样，我们也可以使用 where 但定义是在使用它之后出现的。如图4.4所示。

导出列表、新类型和函数的更改如清单 4.5 所示。

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 #4 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) #5 where #5 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

现在我们已经从外部世界正确地封装了我们的类型和函数！可悲的是，我们现在已经使我们的类型无法使用。为什么？这里有一个问题：我们如何创建一个新列表？请记住，我们没有用于构建此类型的构造函数，这意味着我们无法构造任何 AssocMap k v 类型的值！我们怎样才能规避呢？

我们通过为函数创建包装器来构造新类型的成员和更改函数。但是，我们本可以在匹配和构造列表的位置添加构造函数。作为熟悉如何使用这些构造函数的练习，请执行此操作，而不是使用包装器！

虽然我们可以提供一个将关联列表转换为 AssocMap 的函数，但更简单的解决方案是为空映射提供一个值，以及用于添加和删除新映射的函数。幸运的是，我们有我们的 alter 函数，让实现起来变得轻而易举！新函数如清单 4.6 所示。

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

我们不能忘记将新定义添加到我们的导出列表中：

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

现在我们可以尝试一下了！让我们在 GHCi 中加载项目并检查一下：

ghci> insert 1 "Hello" (insert 2 "World" empty) <interactive>:70:1: error: • No instance for (Show (AssocMap Integer String)) arising from a use of 'print' • In a stmt of an interactive GHCi command: print it

哎 呦！似乎我们又错过了一个类型类！Show 类型类用于提供 show 函数，该函数将 Haskell 类型转换为 String 。GHCi 使用这个函数来显示它评估的值，但我们的类型没有该类的实例。

show 并不意味着提供人类可读的 Haskell 价值观表示！Show 类型类是 Read 类型类的对偶，它为 Haskell 值提供自动生成的解析器。但是，如果您不介意 show 的输出是否已派生，或者您不关心将其保留为 Read 实例的双重并自己实现以使其更具可读性，您也可以使用它进行漂亮的打印！

幸运的是，我们可以自动推断它！某些类型类（Eq 和 Show 是其中的两个）可以自动派生以合理的方式运行。为了派生类型的类型类，我们使用派生关键字：

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

Show 的派生实例将生成字符串值，这些值看起来非常类似于类型值也会写在代码中。请注意，这仅在使用映射中的类型时才有效，而这些类型又具有 Show 类型类的实例！

在对类型进行此小改动后，我们终于可以测试我们的函数：

ghci> insert 2 "World" (insert 1 "Hello" empty) AssocMap [(1,"Hello"),(2,"World")] ghci> delete 1 (insert 1 "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

现在我们定义用于查找由其键关联的值的函数。毕竟，这就是地图的目的！对于查找与某个键关联的值的查找函数，我们使用与之前相同的方法，将处理列表的函数包装到我们的新函数中。此外，我们定义了一个函数，该函数在密钥不存在的情况下也提供默认值。这将为我们以后省去一些头痛。这些函数的代码可以在清单 4.7 中找到。由于我们正在创建一个名为 lookup 的函数，因此可能会与从 Prelude 自动导入的查找函数发生冲突。为了规避此问题，我们可以通过以下导入语句隐藏查找函数：

import Prelude hiding (lookup)注意

在我们不想从导入中隐藏函数的情况下（因为我们实际上想使用它），我们必须在这些函数的出现前面加上模块名称。在我们的例子中，这看起来像Prelude.lookup和Data.AssocMap.lookup。

lookup :: Eq k => k -> AssocMap k v -> Maybe v lookup key (AssocMap xs) = lookup' key xs where lookup' key [] = Nothing lookup' key ((key', value) : xs) | key == key' = Just value | otherwise = lookup' key xs findWithDefault :: (Eq k) => v -> k -> AssocMap k v -> v findWithDefault defaultValue key map = case lookup key map of Nothing -> defaultValue Just value -> value

美妙！我们已经完成了从关联列表构建的地图模块。通过仔细检查，我们确保模块内的函数不会违反每个键只能出现一次的不变性，并且映射不能从模块外部“损坏”，因为构造函数不是从模块中导出的。因此，没有我们的函数，模式匹配或构建新地图是不可能的！现在我们可以基于地图的新定义来实现我们的图！

在我们的 Graph 模块中，我们可以导入新的地图数据类型，但请记住，它导出了一个名为 lookup 的函数，该函数将与 Prelude 中的查找冲突！这是一个问题，在更大的项目中只会变得更糟，其中一个模块可能会导入一百个其他模块！非常优雅地打击这种情况的一种方法是合格的进口。如此重要的看起来像这样：

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 Data.List ghci> nub [1,1,1,2,3,4,1,1,1,2,3,4] [1,2,3,4]

我们还为此模块创建一个限定导入，以便我们可以使用其中的函数。

import qualified Data.List as L

现在我们可以构造用于添加边的函数。如果图中不存在节点，则会添加该节点。否则，连接节点的列表将由新的连接节点扩展，并删除重复项。添加多个边缘似乎一点也不复杂。我们只需要在图形中添加一个边列表，为应该添加的每个边调用函数。此外，我们希望定义一个函数，该函数将节点的关联列表和节点列表转换为图形，这在实现上类似于添加多个边的函数。从节点中检索所有连接的节点在我们的地图中是一个简单的查找！如果找不到节点，我们只需返回一个空列表，因为缺少的节点没有连接节点！这些函数如清单 4.8 所示。

addEdge :: Eq a => (a, a) -> DiGraph a -> DiGraph a addEdge (node, child) = M.alter insertEdge node #1 where insertEdge Nothing = Just [child] #2 insertEdge (Just nodes) = Just (L.nub (child : nodes)) #3 addEdges :: Eq a => [(a, a)] -> DiGraph a -> DiGraph a addEdges [] graph = graph #4 addEdges (edge : edges) graph = addEdge edge (addEdges edges graph) #5 buildDiGraph :: Eq a => [(a, [a])] -> DiGraph a buildDiGraph nodes = go nodes M.empty where go [] graph = graph #5 go ((key, value) : xs) graph = M.insert key value (go xs graph) #6 children :: Eq a => a -> DiGraph a -> [a] children = M.findWithDefault [] #7

我们现在有一些函数来处理有向图。让我们看看其中的一些实际操作：

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

我们实现的一个优点是它完全独立于映射的底层实现。我们可以用其他类型替换我们的 AssocMap 类型，只要这种类型具有与之关联的兼容函数。

当仔细查看图形函数时，我们可以看到addEdges和buildDiGraph的实现非常相似。尝试泛化这两个函数，提供一个高阶函数，该函数适用于类似结构中的列表，并将此函数应用于两个定义。此外，我们没有提供从图形中删除节点和边的函数。自己实现这些功能！

现在，我们知道如何构建一个图表，让我们最终将梯形图放在一起！

回顾一下，梯形图包含给定字典中的所有单词，并包含梯形图游戏中一步即可到达的所有单词之间的边缘。步骤构成以下任何转换的组合：

• 在单词中添加字母
• 从单词中删除字母
• 任意重新排序单词中的所有字母

转换需要产生一个单词，该单词又存在于单词梯形图游戏所基于的字典中。这给我们带来了计算挑战！对于我们可以对单词执行的每个转换，我们需要检查结果是否是字典的一部分。那么我们要检查多少个单词呢？让我们粗略估计并假设我们有一个没有重复字母的 5 个字母的单词。我们可以添加 24 个字母中的任何一个，创建 24 个长度为 6 的新单词。删除一个字母有 5 种可能性，创建 5 个长度为 4 的新单词。我们可以更改 5 个字母中的任何一个，每个字母都有 23 种可能性，创建 115 个长度为 5 的新单词。这些新单词中的每一个都可以任意重新排序。n 个字母有多少种排列？它是 n 的阶乘！单词总数归结为：24 * （6！） 5 * （4！） 115 * （5！），归结为31200个单词，我们需要在字典中检查一个五个字母的单词！对于导致16168320的八个字母的单词，对于十个字母的单词1796256000，对于十二个字母的单词282131942400！这只会花费太长时间！

那么，我们如何解决这个问题呢？如果我们有某种缓存或过滤器可以快速告诉我们哪些排列有效，哪些排列无效，这可能会有很大帮助。理想情况下，我们根本不想计算单词的排列，但是我们如何实现这一点呢？假设我们扫描字典一次，对于我们要存储的每个单词，它都有哪些排列。这些排列有什么共同的性质？它们都由相同的字母组成，因此当我们对它们进行排序时，它们是相同的！我们可以扫描字典以创建单词及其排列的映射，方法是对每个单词进行排序以创建一个键，然后将单词保存在与键关联的列表中。如果我们对每个单词都这样做，我们就创建了一个映射，可以将单词映射到字典中的有效排列！

我们可以在一个新的模块中开始实现排列图的想法，我们将称之为 排列图 .类型是从字符串（排列的排序表示形式）到其排列的映射。

type PermutationMap = M.AssocMap String [String]

此映射上的操作与我们的 AssocMap 相同，但我们需要确保，无论何时我们对键进行操作，我们都会对其进行排序。我们可以使用 Data.List 模块中的排序函数来做到这一点。同样，我们为 Data.AssocMap 和 Data.List 模块以及 Data.May 模块使用限定导入。但是，也许我们只想导入单个函数，而我们使用导入列表来执行。这些列表的作用类似于导出列表，并限制要导入的定义。此模块的代码如清单 4.9 所示。

module PermutationMap where import qualified Data.AssocMap as M #1 import qualified Data.List as L import Data.Maybe (fromMaybe) type PermutationMap = M.AssocMap String [String] #2 empty :: PermutationMap empty = M.empty #3 member :: String -> PermutationMap -> Bool member key = M.member (L.sort key) #4 alter :: ( Maybe [String] -> Maybe [String] ) -> String -> PermutationMap -> PermutationMap alter f key = M.alter f (L.sort key) #4 delete :: String -> PermutationMap -> PermutationMap delete key = M.delete (L.sort key) #4 insert :: String -> [String] -> PermutationMap -> PermutationMap insert key = M.insert (L.sort key) #4 lookup :: String -> PermutationMap -> Maybe [String] lookup key = M.lookup (L.sort key) #4 findWithDefault :: [String] -> String -> PermutationMap -> [String] findWithDefault defaultValue key map = fromMaybe [] (PermutationMap.lookup key map) #5

从本质上讲，PermutationMap 类型只是 AssocMap 的一个专用版本，由于我们的多态实现，我们可以自由使用具体类型。此外，就像我们的 Graph 一样，排列映射类型完全独立于映射的实现！

查看排序函数的类型表达式。为什么我们可以在字符串值上使用这个函数？为什么我们可以在新模块中使用 AssocMap 中的多态函数？尝试通过使用GHCi检查类型来找出为什么类型是兼容的。

接下来，我们要构造一个函数，该函数获取单词列表并从中构建排列图。为此，我们可以假设所有单词都是小写的。每个单词都需要添加到地图中。我们希望有多个单词共享相同的键（因为这是我们找到单词所有排列的方式），因此我们必须通过将单词添加到键指向的列表中来添加单词。实现这一点的代码如示例 4.10 所示。

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

这个实现与清单 4.8 中的 addEdges 函数非常相似，但这次我们不分离函数，而是使用 where 将所有需要的定义保留为本地定义。我们也可以反正 go 函数的机制似乎也很熟悉。说实话，存在一个具有这种确切行为的函数，但我们将等待第 5 章介绍它！

现在我们可以测试我们的新函数：

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"]

我们看到每个单词如何与其排序的单词相关联。构建地图后，我们可以快速检索原始单词列表中存在的所有排列。我们不是计算一个单词的所有排列并检查每个排列，而是在地图中执行简单的查找！

现在我们有了计算上可管理的东西，我们可以开始实际构建我们的梯形图了。为此，我们创建了另一个称为Ladder的模块，其中包含我们用例独有的所有功能。首先，我们为单词列表定义一个类型：

type Dictionary = [String]

我们这样做是为了区分字典的用法和常规的字符串列表。我们假设它们包含单词，这些单词仅包含小写字母。现在，我们可以编写一个IO操作，该操作读取带有单词的文件并解析为字典。我们已经知道如何拆分文件的行，但是我们需要过滤字典条目，使它们只包含小写字母 我们可以使用 Data.List 模块中的过滤函数来做到这一点。此函数接收 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 函数执行的任何重复项。代码如示例 4.11 所示。我们还为 Data.List 、Graph 和 PermutationMap 模块创建合格的导入。

module Ladder 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

在这里，我们还看到了如何对函数（在本例中为 L.elems）和 eta 缩减使用中缀符号来摆脱 lambda 抽象。

现在，我们想使用字典中的单词来生成梯形图。为此，我们需要计算单词的所有可能更改（添加字母，删除字母，修改字母），并使用我们从字典本身构建的排列图来计算新形成单词的所有重新排序。我们可以使用buildDiGraph函数，通过计算字典中每个单词的所有有效新单词来构建节点及其各自边缘的列表。假设我们已经有一个函数 computeCandidate 返回给定单词的所有可能候选函数，完成的函数如示例 4.12 所示。

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

但是，我们显然还没有我们应该注意的 computeCandidate 函数！给定一个单词，我们首先需要向其添加一个任意字母，然后使用排列映射来获取它的所有有效排列。这使我们的工作稍微容易一些，因为我们在哪里添加新单词并不重要。我们如何在字符串中添加新字母？一种可能性是使用地图函数：

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"]

删除字母同样可以通过地图进行，因为我们可以遍历单词本身，并且对于每个字母，使用 Data.List 模块中的删除函数将其从单词中删除。请注意，此函数仅删除要删除的元素的第一次出现。

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

同样，我们不关心哪个字母实际上被删除了，因为我们的排列图无论如何都会在查找时对单词进行排序！为了计算我们切换单个字母的单词，我们现在必须组合这两个操作。那是因为我们不想添加刚刚从单词中删除的字母。但是，写下来可能会变得有点麻烦，这就是为什么我们将使用另一种列表语法：列表推导！它们允许我们以非常简单的方式写下列表的定义。列表理解分为两部分。左侧，指定如何构建列表的元素，右侧包含所谓的生成器和防护装置。

以下是一些示例：

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

如我们所见，左侧是针对生成器中与守卫匹配的每个元素进行评估的！使用多个生成器将导致评估左侧来自生成器的元素的交叉乘积。

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

我们可以使用这些理解来构建我们对单词的修改。对于给定的单词，我们可以计算可能的新单词，如下所示：

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

在这里，我们可以观察如何使用列表推导来组合映射和过滤器的功能，此外，还为我们提供了一种将列表与交叉乘积组合的方法。这也扩展到我们喜欢的任意数量的维度，因为我们可以使用任意数量的生成器！这种为列表编写定义的方式通常允许我们将定义保持更短，并且可以说更容易阅读。但是，它主要是个人喜好。

列表推导式也可用于模式匹配。生成器中失败的模式匹配计为跳过的值。通过这种方式，您可以像这样定义 catMaybes 函数：catMaybes xs = [ x |只是 x ← xs ] .任何与 Just x 不匹配的值都将被丢弃。

现在我们可以通过使用我们刚刚提出的定义来完成我们的函数。此外，我们可以从排序的单词中删除所有重复项，以保持地图中的查找量较小。此外，在最终结果中，我们应该从列表中删除原始单词，因为阶梯游戏中的步骤应该更改单词。清单 4.13 中列出了此函数的完整源代码。

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

我们还没有看到的一个函数是 康卡特地图 .它有什么作用？此函数与 concat 函数密切相关，后者只是获取列表列表并通过通过连接它们来创建包含先前列表的所有元素的单个列表来展平它们。concatMap 只是 map 后跟一个 concat 的组合。这对于 map 函数的结果是列表，但您希望将这些列表中的所有元素合并到单个列表中的情况非常有用。由于这很常见，因此此函数已经预定义。

ghci> concat [[1,2,3], [4,5,6]] [1,2,3,4,5,6] ghci> concat ["Hello", " ", "World"] "Hello World" ghci> concatMap (\x -> [1..x]) [1..5] [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"])]

在这里，我们为函数提供了一个包含四个单词的字典。我们可以看到，猫、猫和行为这些词都可以在一步之内到达，而狗不能被任何节点到达，并且在图中也没有邻居。现在，我们可以构建我们想要寻找解决方案的结构，我们可以解决人工智能的核心问题：搜索问题！

知道我们能够从给定的字典中构建梯形图，我们需要执行的唯一计算复杂任务就是在其中搜索。我们的算法的另一个要求是它需要找到最短的路径，以产生一个最佳的单词梯。我们的图表很特别，因为它具有统一的边缘成本，因为它们都没有被称重。在这种情况下，我们保证通过广度优先搜索找到最短路径！

让我们考虑一下图形。当搜索路径时，我们从某个节点开始。从那里我们需要访问每个邻居，然后对我们以前没有访问过的每个新节点的每个邻居重复此过程。在执行此类搜索时，我们创建节点层的顺序。这样的顺序如图4.5所示。

但是，我们需要小心！为了构建广度优先搜索，我们必须同时更新我们正在访问的新节点的边界。我们不能只对每个节点执行递归搜索，因为这将是深度优先搜索，我们放弃在给定节点的每个相邻节点中进行搜索，而是立即继续搜索我们找到的第一个相邻节点。因此，在搜索时，我们必须跟踪当前正在访问的节点，并在每一步中相应地更新它们。如图4.6所示。

我们不仅要搜索路径的存在，还需要确定哪些节点是其中的一部分，以便为单词梯子游戏生成解决方案。为了实现这一点，我们必须保留搜索节点的历史记录，并在搜索节点时跟踪节点的前置节点。为了做到这一点，我们必须确保我们永远不会两次访问一个节点，因为每个节点都必须有一个前置节点，否则我们需要再次搜索整个图以找到我们首先找到的实际路径。为了解决这个问题，我们可以做的是在我们在图中搜索时删除我们从图中看到的每个节点。这对我们的目的可以吗？答案是肯定的！我们不可能从一个节点到另一个节点的最短路径访问一个节点两次，因为它不可能是最短的！可以删除连接同一节点的两个访问的节点，以生成仍将起始节点连接到结束节点的较短路径。这个前身图的创建如图 4.7 所示。

让我们回顾一下。我们的搜索算法需要执行以下操作：

1. 从图形和起始节点作为初始边界开始
2. 收集边界中每个节点的所有相邻节点
3. 从图表中删除当前边界
4. 将边界中的每个节点存储为其各自相邻节点的前置节点
5. 检查目标节点是否是相邻节点的一部分
1. 如果是，则搜索结束，可以回溯前置任务以找到路径
2. 如果没有，则使用相邻节点作为新边界继续搜索（步骤 2）

为了一次删除多个节点，我们需要引入一个为我们执行此操作的新功能。与之前的实现类似，对于应该从图形中删除的每个元素，我们递归地从 AssocMap 模块调用 delete。其代码如示例 4.14 所示。

deleteNodes :: Eq a => [a] -> DiGraph a -> DiGraph a deleteNodes [] graph = graph deleteNodes (x : xs) graph = M.delete x (deleteNodes xs graph)

从我们对搜索算法的描述中可以清楚地看出，我们需要处理某种状态。我们需要跟踪我们的边界，还需要跟踪要搜索的图形（因为我们正在从中删除节点）和我们的前辈。幸运的是，我们已经有一个可用于此目的的类型：我们的DiGraph类型！因此，我们可以将我们的搜索状态表示为它自己的类型，其中包含边界作为元素列表、我们的图和另一个我们用来跟踪前置的图：

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

此外，我们定义了搜索结果的类型。它要么不成功，要么成功，返回我们可以找到的前辈。假设前置图将使回溯解决方案成为可能！

data SearchResult a = Unsuccessful | Successful (DiGraph a)

在我们的实际搜索中，我们必须执行两个任务：执行实际搜索并相应地更新状态，然后回溯前置任务以获得搜索路径。我们函数的一般框架可能如下所示：

bfsSearch :: forall a. Eq a => DiGraph a -> a -> a -> Maybe [a] bfsSearch graph start end | start == end = Just [start] | otherwise = case bfsSearch' ([start], graph, empty) of Successful preds -> Just (findSolution preds) Unsuccessful -> Nothing

我们的函数应该在连接开始节点和结束节点的图形中搜索路径。我们返回路径的可能，因为搜索可能不成功，在这种情况下，我们当然返回 什么都没有 .我们现在专注于实现bfsSearch'。此函数旨在处理搜索状态并返回一个布尔值，告诉我们搜索是否成功以及前置任务。从图形中删除当前边界可以使用新创建的 deleteNodes 函数来实现。当从当前边界中的每个节点收集所有连接的节点（或子节点）时，我们必须确保根据它们在已删除节点的现在更新的图形中的成员资格来过滤它们，因为我们不想将节点添加到边界不再是我们图形的一部分。为了将所有这些新节点添加为前节点，我们构造了一个新的帮助函数，对于节点元组及其连接的节点的列表，将它们反向添加到图中，从而向图形添加边缘，以表示哪个节点在搜索中哪个节点之前。这些函数（在我们的 bfsSearch 函数中用作局部定义）如清单 4.15 所示。

addMultiplePredecessors :: Eq a => [(a, [a])] -> DiGraph a -> DiGraph a addMultiplePredecessors [] g = g addMultiplePredecessors ((n, ch) : xs) g = addMultiplePredecessors xs (go n ch g) #1 where go n [] g = g go n (x : xs) g = go n xs (addEdge (x, n) g) #2 bfsSearch' :: Eq a => SearchState a -> SearchResult a bfsSearch' ([], _, preds) = Unsuccessful #3 bfsSearch' (frontier, g, preds) = let g' = deleteNodes frontier g #4 ch = L.map (\n -> (n, L.filter (`M.member` g') (children n g))) #5 frontier frontier' = L.concatMap snd ch #6 preds' = addMultiplePredecessors ch preds #7 in if end `L.elem` frontier' #8 then Successful preds' #9 else bfsSearch' (frontier', g', preds') #10

最后一个难题是回溯算法，用于从前置图中找到解决方案。我们知道，此图中的节点都只有一个前置节点，除了起始节点，它是唯一不包含前置节点的节点。这允许我们从末端递归回溯到开始节点。一旦找不到更多的前辈，我们就可以停止搜索。该算法的代码如示例 4.16 所示。请注意，执行搜索的辅助函数以相反的顺序生成解决方案。此外，为了使该算法起作用，必须存在解决方案，并且我们对前置图所做的假设必须成立！

findSolution :: Eq a => DiGraph a -> [a] findSolution g = L.reverse (go end) #1 where go x = case children x g of #2 [] -> [x] #3 (v : _) -> x : go v #4

现在，我们能够将所有内容放在一起！在将示例 4.15 和示例 4.16 中的定义添加到带有 where 子句的代码框架中后，我们得出搜索算法的最终定义！但是，这不会编译，而是我们得到一个错误：

• Couldn't match expected type 'a1' with actual type 'a' 'a1' is a rigid type variable bound by the type signature for: findSolution :: forall a1. Eq a1 => DiGraph a1 -> [a1] at .../ladder/src/Graph.hs:... 'a' is a rigid type variable bound by the type signature for: bfsSearch :: forall a. Eq a => DiGraph a -> a -> a -> Maybe [a] at .../ladder/src/Graph.hs:...

这是怎么回事？出于某种原因，bfsSearch和findSolution的类型似乎不匹配，但为什么呢？它们不是都是多态的吗？两者甚至具有相同的类型约束和名称，因此类型应该是兼容的！

为了解决这个问题，让我们再次看一下类型表达式。Haskell向我们隐瞒的是，像这样的类型表达式不存在：

const :: a -> b -> a

Haskell实际上对这种类型的看法略有不同：

const :: forall a b. a -> b -> a

这称为通用量化，隐式执行到默认情况下包含自由类型变量的所有类型签名的最外层。forall 将新的类型变量引入范围，以便声明要使用的函数。在函数声明的外部，这可以解释为一个承诺：对于可以替换 a 和 b 的所有类型，声明成立。很容易看出，当我们玩弄这个函数时，这个承诺成立：

ghci> const (1 :: Int) ("Hello" :: String) 1 ghci> const (True :: Bool) (3.1415 :: Float) True ghci> const (() :: ()) ((\x -> x) :: (a -> a)) ()

我们可以用任意类型替换 a 和 b，并且仍然可以得到结果！虽然这是对函数声明外部的承诺，但它是对函数声明内部定义的限制！这是有道理的，因为具体类型不是由函数声明选择的，而是由函数的被调用方选择的！在函数声明中，类型是固定的（有时在错误消息中称为刚性）。

f :: a -> a f x = y where y = x

此示例中的类型将隐式更改为 forall a. a → a，因此引入了类型变量 a，并且也为声明固定了类型变量 a。可以推断 x 是 a 型，并且由于 y = x，y 也必须是 a 型。类型是正确的！但是，如果我们向 x 添加一个类型表达式并将其声明为 a 型呢？

f :: a -> a f x = y where y = (x :: a)

这将再次引发相同的错误！但是为什么？添加隐式通用量化后，它看起来像这样：

f :: forall a. a -> a f x = y where y = (x :: forall a. a)

forall a. a → a 将变量 a 限制为任意的，但对于函数声明是固定的。这也延伸到 where 子句中的声明！然而，x的a.a做出了承诺，这可以是任意类型的。这个承诺是对函数定义的其余部分做出的，最终导致类型不兼容！x 不能同时是固定类型和任意类型！检查这些属性时，编译器不会考虑类型的名称！

正是在构建我们的搜索函数时出现的确切问题。幸运的是，我们可以告诉Haskell对类型变量执行词法范围，这意味着当forall引入类型变量时，它可以在函数声明的类型中重用，并且仍然引用相同的类型。我们可以通过使用所谓的语言扩展来启用此行为。这些扩展允许我们在全球范围内（通过使用编译器标志）或每个文件更改Haskell编译器的行为。我们感兴趣的语言扩展称为 作用域类型变量 .我们可以通过在模块的开头添加以下行来启用此功能：

{-# LANGUAGE ScopedTypeVariables #-} module Graph where

现在，这允许我们在类型定义中显式使用 forall 并更改其行为。Forall 现在引入了词法作用域的类型变量！这使我们能够通过在最外层的类型签名中显式量化类型变量来构造函数。如清单 4.17 所示。

f :: forall a. a -> a #1 f x = y where y = (x :: a) #2

一个很好的副作用是，对类型的约束被带到其他定义中，因此我们必须仅在最外层的类型签名上应用类型约束！另请注意，没有显式使用 forall 的函数定义的行为仍然与以前相同。

forall 的用法是重载的，并且根据所使用的语言扩展具有不同的含义。除了 ScopedTypeVariables 之外，还存在 RankNTypes 和 ExistentialQuantification，它们对类型系统的工作方式有着深远的影响。一般来说，显式 forall 应该只在需要时使用！但是，ScopedTypeVariables 相对安全，并且在许多项目中全局启用。

修改搜索函数的类型后，我们得出搜索算法的完整（和编译）定义！完整的源代码如清单 4.18 所示。请注意最外层类型签名中的显式 forall，以及类型约束 Eq a 如何仅出现在此签名中，因为类型变量 a 现在在整个函数声明中可用。

type SearchState a = ([a], DiGraph a, DiGraph a) #1 data SearchResult a = Unsuccessful | Successful (DiGraph a) #2 bfsSearch :: forall a. Eq a => DiGraph a -> a -> a -> Maybe [a] #3 bfsSearch graph start end | start == end = Just [start] #4 | otherwise = case bfsSearch' ([start], graph, empty) of #5 Successful preds -> Just (findSolution preds) #6 Unsuccessful -> Nothing where findSolution :: DiGraph a -> [a] findSolution g = L.reverse (go end) #7 where go x = case children x g of #8 [] -> [x] #9 (v : _) -> x : go v #10 addMultiplePredecessors :: [(a, [a])] -> DiGraph a -> DiGraph a addMultiplePredecessors [] g = g addMultiplePredecessors ((n, ch) : xs) g = addMultiplePredecessors xs (go n ch g) #11 where go n [] g = g go n (x : xs) g = go n xs (addEdge (x, n) g) #12 bfsSearch' :: SearchState a -> SearchResult a bfsSearch' ([], _, preds) = Unsuccessful #13 bfsSearch' (frontier, g, preds) = let g' = deleteNodes frontier g #14 ch = L.map (\n -> (n, L.filter (`M.member` g') (children n g))) #15 frontier frontier' = L.concatMap snd ch #16 preds' = addMultiplePredecessors ch preds #17 in if end `L.elem` frontier' #18 then Successful preds' #19 else bfsSearch' (frontier', g', preds') #20

我们通过跟踪访问的节点、修改后的图和已经找到的前置图，为我们的直接图构建了一个广度优先的搜索算法，以查找最短的路径。从访问的节点构建前置图，然后用于通过回溯找到实际解决方案。

为了搜索图中的最短路径，我们使用了广度优先搜索。但是，存在其他搜索算法。如果我们只想找到任何路径并且对其长度不感兴趣，那么深度优先搜索可能是合适的。此外，对普通广度优先搜索的性能改进是双向广度优先搜索，它同时从两侧执行两个搜索，一个从头到尾搜索，另一个从头到尾搜索。一旦两个搜索相遇，就找到了解决方案。实现这两种搜索算法！

现在我们能够构建梯形图，并且还可以在其中找到最短路径，我们拥有构建程序所需的所有部分！

构建一个解决单词梯子游戏的函数相当简单。我们只需要一个字典的开头和结尾单词，我们就完成了！我们可以简单地使用 mkLadderGraph 函数构建梯形图，并使用我们的搜索算法搜索解决方案！梯形图模块中的代码如清单 4.19 所示。

ladderSolve :: Dictionary -> String -> String -> Maybe [String] ladderSolve dict start end = let g = mkLadderGraph dict #1 in G.bfsSearch g start end #2

我们可以保持程序的主模块相当简单。就像上一章一样，如果参数的数量与我们的期望不符，我们会提供帮助文本。否则，我们只需使用 readDictionary 操作构建字典，并使用上述 ladderSolve 函数解决它。然后我们打印解决方案及其长度。该模块的完整代码如清单 4.20 所示。

module Main where import Ladder #1 import System.Environment printHelpText :: String -> IO () #2 printHelpText msg = do putStrLn (msg "\n") progName <- getProgName putStrLn ("Usage: " progName " <filename> <start> <end>") main :: IO () main = do args <- getArgs #3 case args of [dictFile, start, end] -> do #4 dict <- readDictionary dictFile #5 case ladderSolve dict start end of #6 Nothing -> putStrLn "No solution" Just sol -> do print sol putStrLn ("Length: " show (length sol)) _ -> printHelpText "Wrong number of arguments!"

打印操作只是使用 show 和 putStrLn 的组合，并将值打印到 stdout。现在可以测试此应用程序！

为此，代码存储库已经准备好了两个字典文件，small_dictionary.txt包含 200 个单词，large_dictionary.txt包含 58110 个单词。在我们的项目目录中，我们现在可以像这样调用程序：

shell$ stack run -- path/to/small_dictionary.txt cat flower ["cat","oat","lot","volt","love","vowel","lower","flower"] Length: 8 shell$ stack run -- path/to/small_dictionary.txt dog book ["dog","dot","lot","tool","look","book"] Length: 6

这看起来不错！因此，让我们用更大的字典来测试它！井。。。可悲的是，我们无法观察到程序功能的所有荣耀，因为至少在我的机器上，它似乎没有产生结果。只是需要太长时间！我们应该以某种方式改善这一点...

在决定我们要改进什么之前，我们应该首先分析哪个操作需要这么长时间。为此，我们想介绍我们的程序。我们可以通过首先使用 --profile 标志编译带有堆栈的程序来做到这一点。这将在 GHC 中设置一些选项，以便在运行时启用应用程序分析。然后，我们可以使用 RTS -p -RTS 设置基本时间和内存分析的运行时选项。 RTS 和 -RTS 用于开始和结束向 Haskell 运行时系统而不是普通应用程序提供参数。程序的完整调用如下所示：

shell$ stack run --profile -- path/to/small_dictionary.txt dog book RTS -p -RTS

程序完成后，将创建一个文件，在我们的例子中称为 梯子-exe.prof .此文件包含性能分析信息，如下所示：

Mon Jul 25 16:22 2022 Time and Allocation Profiling Report (Final) ladder-exe RTS -N -p -RTS path/to/small_dictionary.txt dog book total time = 0.03 secs (100 ticks @ 1000 us, 8 processors) total alloc = 46,192,080 bytes (excludes profiling overheads) COST CENTRE MODULE SRC %time %alloc lookup.lookup' Data.AssocMap src/Data/AssocMap.hs:(54,5)-(57,34) 54.0 0.1 computeCandidates.uniques Ladder src/Ladder.hs:19:7-50 21.0 26.9 member.member' Data.AssocMap src/Data/AssocMap.hs:(24,5)-(27,32) 14.0 0.0 alter.alter' Data.AssocMap src/Data/AssocMap.hs:(33,5)-(43,40) 5.0 44.7 lookup PermutationMap src/PermutationMap.hs:31:1-34 3.0 12.3 readDictionary Ladder src/Ladder.hs:(10,1)-(14,22) 2.0 0.2 computeCandidates.perms Ladder src/Ladder.hs:20:7-69 0.0 1.7 computeCandidates.modified Ladder src/Ladder.hs:(25,5)-(26,58) 0.0 7.1 computeCandidates.canditates Ladder src/Ladder.hs:18:7-57 0.0 2.5

这是我们计划成本中心的简要概述，这些成本中心主要由我们的职能组成。这告诉我们每个函数花费了多少时间以及在其中分配了多少内存。由此我们可以看到，在 AssocMap 模块中的查找函数中使用了大量时间。整个运行时间的一半以上由这个函数组成！这是有道理的，因为我们不断在图形中查找值，这只是一个 AssocMap .因此，如果我们想加快程序执行速度，我们必须对其进行优化！

问题是：这个函数有什么问题？它是构成我们地图的关联列表中的简单查找。在最坏的情况下，它必须在每次查找时遍历整个列表！这是有道理的，更大的字典将导致更大的图形，这将导致查找值的时间更长！可悲的是，这只是我们在使用关联列表时面临的缓慢现实。这个缺点是他们设计中固有的！我们需要做的是用更快的东西完全替换它。一个很好的候选者是哈希映射，它以其快速访问时间而闻名。

但是，这次我们不是在构建自己的哈希图。我们将简单地使用已经可用的一个！为此，我们需要将依赖项无序容器和可哈希添加到我们的项目中。为此，我们编辑我们的 package.yml 文件以包含这些依赖项。文件的相关部分应如下所示：

dependencies: - base >= 4.7 && < 5 - unordered-containers - hashable

这将自动使堆栈负责下载和构建我们项目的依赖项。现在我们可以用 Data.HashMap.Lazy 替换我们的 Data.AssocMap 模块。此外，在图和排列图模块中，我们需要更改我们的类型以使用 M.HashMap 而不是 M.AssocMap .为了使值成为HashMap中的键，它需要具有Hashable类型类的实例。因此，我们需要更改 Graph 模块中的类型签名，以在其类型约束中包含 Hashable a。此类提供了一个哈希方法，该方法在 HashMap 中使用，可以从 Data.Hashable 模块导入。

用HashMap切换AssocMap并不是巧合，因为我们基本上实现了哈希映射模块中也存在的相同功能。如果你了解这些函数是如何为AssocMap工作的，你现在也知道HashMap模块是如何工作的！

再次编译并运行程序后，我们甚至可以处理大型字典！通过再次启用分析运行程序来再次查看成本中心，向我们展示了一些非常有趣的事情：

computeCandidates.uniques Ladder src/Ladder.hs:19:7-50 67.4 34.7 readDictionary Ladder src/Ladder.hs:(10,1)-(14,22) 4.7 0.2 liftHashWithSalt.step Data.Hashable.Class src/Data/Hashable/Class.hs:656:9-46 4.7 7.2 liftHashWithSalt Data.Hashable.Class src/Data/Hashable/Class.hs:(653,5)-(656,46) 4.7 0.0 lookup# Data.HashMap.Internal Data/HashMap/Internal.hs:597:1-82 2.3 1.3 insert'.go Data.HashMap.Internal Data/HashMap/Internal.hs:(759,5)-(788,76) 2.3 1.1

我们的查找速度如此之快，以至于计算排列图中查找的唯一候选者似乎是一个主要的时间槽！幸运的是，我们可以简单地摆脱它，因为我们添加它只是为了最大限度地减少我们在排列图中必须执行的查找次数。现在地图实现如此之快，不再需要了！又一次性能提升！在对应用程序进行了一些分析之后，但是这次使用大型字典，我们得到了另一个令人惊讶的结果：

readDictionary Ladder src/Ladder.hs:(10,1)-(14,22) 95.7 5.5 readDictionary.words Ladder src/Ladder.hs:13:7-60 1.3 6.0 alter PermutationMap src/PermutationMap.hs:22:1-36 0.4 18.5 readDictionary.lines Ladder src/Ladder.hs:12:7-39 0.4 14.5 insert'.go Data.HashMap.Internal Data/HashMap/Internal.hs:(759,5)-(788,76) 0.3 5.8

我们花最多时间只是阅读文件！这是个好消息，因为这告诉我们我们的算法本身已经非常优化了。但是，有一种方法可以改善文件的读取。到目前为止，我们一直在愉快地使用性能*手，甚至不知道。罪魁祸首称为字符串。问题在于字符串的构造。它们是列表中的单个 Char 值，这样做的问题是列表位于堆上，这意味着字符串的访问成本相当高。当性能至关重要时，必须避免使用字符串类型。合适的替换是文本包中的文本类型或字节串包中的字节字符串。两者都提供了性能更高、更紧凑的字符串表示形式。它们的缺点是我们不能对它们使用通常的列表函数，使它们在使用时稍微不那么便携。我们不会详细讨论如何用任何更快的方式替换我们的 String 用法，因为性能改进是微不足道的。但是，好奇的读者可以自由检查该项目优化版本的代码存储库！

在为性能设计程序时，切换类型应该是您的最后手段。正确选择算法和数据结构比技术细节重要得多。

我们想通过更仔细地研究评估在 Haskell 中的工作原理来结束我们对性能的讨论。与其他语言有很大不同，Haskell是一种惰性求值的语言。这意味着表达式不会立即被计算，而只有在强制计算表达式时才被计算。作为一个例子，让我们看一下：

ghci> const x y = x ghci> const 0 1000^100000000 0

const 函数有两个参数，其中第二个被完全丢弃。在我们执行的评估中会发生什么？表达式 const 0 1000^100000000 减少到只有 0，因为 const x y 减少到 x 。第二个参数，这是一个巨大的数字，应该需要很长时间来计算，只是被丢弃，因此没有被评估！您可以查看附录B以获取更多详细信息！

我们的算法也利用了这种惰性评估！在搜索解决方案之前，我们不会构建整个图。我们在搜索时正在构建图表！仅评估图形中所需的元素。但是，这仅在我们所有的数据结构都是懒惰的情况下才有效。默认情况下，我们自己定义的列表和类型是惰性的。在使用哈希映射提高性能时，我们专门导入了不强制评估值的惰性版本的 HashMap。

虽然似乎懒惰评估通常比其对应的严格评估更受欢迎，但事实并非如此。某些算法，如本章中的搜索算法，受益于懒惰，而其他算法则明显下降。懒惰还可能导致意外的内存使用，这就是为什么一些开发人员在语言扩展的帮助下完全禁止它在他们的项目中的原因。

让我们回顾一下我们在这个项目中取得的成就。我们创建了一个人工智能，给定单词字典，它能够找到单词梯子游戏修改版本的最短解决方案。我们通过实现一种算法来做到这一点，该算法可以创建一个代表游戏可能解决方案的图表，并通过搜索此图表找到解决方案。为此，我们使用关联列表实现了我们自己的映射版本，并将这种类型的功能捆绑到其自己的模块中以实现可重用性。基于此实现，我们创建了另一种映射类型，用于快速检索给定单词的有效排列，以使我们的程序可行。使用我们的自定义地图实现，该图被建模为邻接地图。我们使用广度优先搜索来查找最短路径。在对程序进行测试和分析之后，我们通过哈希映射切换从关联列表构建的映射来提高其性能。

现在我们已经准备好进入下一个单词阶梯世界锦标赛...如果存在这样的事情。

• 类型类用于定义一组类型的函数，以便为这组类型构造多态函数。
• 翻转可用于翻转二进制函数的参数。
• 当以纯粹的方式处理数据结构时，我们从不直接修改它们，而是创建原始值的修改版本。
• 导出列表可用于隐藏类型和函数的构造函数，以确保被调用方不能使我们的值的不变量失效。
• 在只有一个构造函数和一个字段的数据类型上，我们可以使用 newtype 而不是 data 来明确我们想要在不需要的时候创建一个新类型。
• where 可用于在变量和函数在表达式中使用后定义它们。
• 限定导入迫使我们在导入的值前面加上模块名称，使代码更清晰并防止名称冲突。
• 语言扩展 ScopedTypeVariables 可用于显式使用 forall 对类型变量进行词法作用域。
• 使用 --profile 作为堆栈的标志，使用 RTS -p -RTS 作为应用程序的运行时选项，我们可以使程序配置文件成为它的执行。
• 惰性求值只计算绝对需要的表达式，丢弃其他所有内容。