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

我们的上一个项目是一个流行的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所示。