endnoteword怎么关联,endnote如何关联上word

导出列表、新类型和函数的更改如清单 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 作为应用程序的运行时选项，我们可以使程序配置文件成为它的执行。
• 惰性求值只计算绝对需要的表达式，丢弃其他所有内容。