Haskell入门教程：8 解析像素数据

• 从头开始为文本编写解析器
• 结合有效的行动
• 函子、应用器和单子背后的理论
• 使用 Attoparsec 库为二进制数据构建解析器

在前面的章节中，我们以某种方式处理了读取数据的特定任务。无论是文件行还是更复杂的格式，如 CSV。出于我们的目的，我们创建了用于读取此数据的自定义函数，这些函数是为手头的任务量身定制的。但是，这不是我们通常在这些情况下所做的。通常，无论我们使用什么语言，我们都会构造某种解析器来做到这一点。在 Haskell 中，解析器的开发几乎是一种独特的体验，它们如何干净地组成，从简单的构建块构建更大的解析器。

在本章中，我们将编写自己的简化解析器库，以便读取PNM文件，这是一系列简单的图像文件格式，它不仅会教我们如何编写有效的操作，还会教我们如何优雅地处理我们在途中可能遇到的任何错误和故障。我们通过使用应用程序剂和monad来做到这一点，我们将了解它们是如何工作的，以及为什么它们是Haskell中必不可少的构建块。之后，我们将了解 Attoparsec，一个广泛使用的解析器组合器库，它将帮助我们为图像文件创建高性能解析器。

本章将从定义我们试图解决的问题开始。然后我们将构建自己的解析器库来开始解决此任务。最后，我们使用现有的最先进的解析器库来应用我们学到的知识。

自摄影诞生以来，我们不仅对捕捉现实世界感兴趣，而且在创建图像后对其进行修改。这不仅适用于摄影，也适用于任何视觉艺术。在我们的现代世界中，摄影师和艺术家都是幸运的，因为他们的大部分作品已经转移到数字领域，他们的图像只不过是零碎的。巧合的是，计算机是转换和篡改这些位和字节以创建全新事物的大师。

此外，作为程序员，我们有能力让计算机做我们告诉他们做的任何事情。因此，是时候编写能够转换图像数据的软件了！为此，我们必须选择要支持的图像格式。虽然现在有大量高度压缩和复杂的格式，但我们希望通过为 Netbpm 项目的格式编写图像处理库来保持我们的老派。

在 1980 年代，共享图像并不像将它们上传到云中那么简单。如果您想共享任何东西，则必须通过电子邮件完成，这在当时并不是发送二进制数据的最佳选择。如果你想发送图像，它们必须是好的7位ASCII。为了促进这一点，Jef Poskanzer发明了一系列文件格式，可以以ASCII或二进制形式分发，并且没有多余的元数据，使它们易于解析和理解。

这些格式（有时称为可移植任意映射格式 （PNM））是可移植像素图格式 （PPM）、可移植灰度图格式 （PGM） 和可移植位图格式 （PBM）。这些可用于存储彩色、灰度和彩色像素数据。还有一套工具可以使用这些格式，称为netpbm，它允许您将更常用的格式与这些可移植格式相互转换。

让我们快速回顾一下这些格式的工作原理。它们都包含一个始终包含一个幻数的标题。此数字指定正在使用哪种格式，以及其编码是 ASCII 还是二进制。文件扩展名通常不用于确定我们正在使用的格式类型。然后，标题继续显示图像的宽度和高度。对于 PPM 和 PGM 格式，第四个值表示单个数据点的最大值。让我们看一下清单 8.1 中的示例。

P1 # PBM in ASCII 2 2 # 2x2 pixel size 1 0 0 1

如我们所见，标题可以包含由 # 表示的注释。它们也始终采用 ASCII，无论幻数如何。本示例指定一个宽 2 像素、高 2 像素的位图图像。以下二进制数据表示这些像素的值。放大生成的图像，我们得到如图 8.1 所示的结果。

在表 8.1 中，我们分别看到了文件格式、幻数和包含的数据的概述。我们可以看到，每种格式都有两个幻数，对应于该格式的 ASCII 和二进制版本。

PNM 格式的标头始终以 ASCII 编码！

对于位图和灰度图文件，标题后面的单个值对应于图像中的单个像素。但是，在像素图格式中，像素由三个值组成，每个值分别代表构成该像素的红色、绿色和蓝色值。

表 8.1.PNM 格式的幻数概述

我们可以在示例 8.2 的标头中看到这个最大值的用法。标头中的元素也没有严格的规则。它们可以放在一行中，但通常将幻数、图像尺寸和最大值分成不同的行。此外，图像数据可以分成单行，但并非必须如此。为了便于阅读，建议文件中的最大行长度为 76，但同样，当我们只对存储数据供计算机读取感兴趣时，不必遵守此建议。

P2 10 14 # PGM in ASCII with 10x14 pixels 9 # Values from 0 (black) to 9 (white) 9 6 3 4 9 9 9 9 9 9 8 4 2 2 6 9 9 9 9 9 8 6 9 5 4 9 9 9 9 9 8 9 9 9 4 9 9 9 9 9 9 9 9 9 4 7 9 9 9 9 9 9 9 9 3 6 9 9 9 9 9 9 9 6 1 3 9 9 9 9 9 9 9 4 0 3 8 9 9 9 9 9 7 0 4 4 8 9 9 9 9 9 4 1 7 5 6 9 9 9 9 7 1 3 9 6 5 9 9 8 9 5 0 7 9 8 3 8 9 6 8 1 2 8 9 8 3 3 4 4 5 2 5 9 9 9 7 2 1 7

清单 8.2 中所示的 PGM 文件的图像结果如图 8.2 所示。使用 netpbm 和 ImageMagick 工具，我们可以轻松地将这些文件与其他更常见的文件格式（如 jpeg 或 png）进行转换。

现在，我们已经了解了这些文件格式的工作原理，我们可以考虑如何在程序中读取这些文件。

读取信息，无论是文件、网络数据包还是来自串行端口的数据，都需要我们描述预期的结构。无论我们读取CSV文件，编程语言的源代码还是（在我们的例子中）图像文件，都是如此。描述此结构通常使用解析器来实现。解析器是程序或程序的一部分，它将字符串或字节转换为可以在所述程序中解释的数据。解析器有两个核心职责：

• 验证数据的结构，并在验证失败时报告错误
• 将字符或字节字符串转换为本机数据类型

从理论上讲，我们可以通过编写简单的函数来实现这些目标，就像我们在第 5 章中解析 CSV 文件时所做的那样。这样做的缺点是，仅通过查看其定义就很难理解解析器的期望。由于我们不想重复这一点，并且我们正在处理 Haskell 的解析问题，因此我们还有几个目标：

• 解析功能应该是可组合的
• 解析器的定义应该提供有关预期结构的见解

因此，让我们在 Haskell 中编写一个通用解析器。首先，我们必须为它想出一个类型。随着我们的发展，这种类型将根据需要而转变。

由于解析器将输入转换为某些本机数据类型，因此解析器可能只是一个简单的函数：

type Parser a = Text -> a

对于我们的简化解析器，我们将处理 文本数据类型 来自 数据.文本 .如果我们想为 PNM 格式的幻数编写一个解析器，我们可以这样做：

data MagicNumber = P1 | P2 | P3 | P4 | P5 | P6 deriving (Eq, Show) magicNumberP :: Parser MagicNumber magicNumberP "P1" = P1 magicNumberP "P2" = P2 magicNumberP "P3" = P3 magicNumberP "P4" = P4 magicNumberP "P5" = P5 magicNumberP "P6" = P6

我们的解析器称为 魔术数字P ，可以从文本中读取一个幻数。在本章的其余部分，我们假设在整个项目上启用了 OverloadString 语言扩展。但是，很明显，我们的解析器使用非详尽的模式匹配，如果解析失败，我们的程序会崩溃。因此，我们的类型应该编码失败的可能性。

就像在变量名称中为 m 添加 May 和 Either 值的前缀一样，在解析器上放置后缀 P 也很常见！

正如我们在前面的章节中学到的，这可以通过 Any 类型来完成。这也使我们能够在解析器中返回错误消息。我们可以像这样更新类型：

type ErrorMessage = String type Parser a = Text -> Either ErrorMessage a

使用这个新的幻数解析器如下所示：

magicNumberP :: Parser MagicNumber magicNumberP "P1" = Right P1 magicNumberP "P2" = Right P2 magicNumberP "P3" = Right P3 magicNumberP "P4" = Right P4 magicNumberP "P5" = Right P5 magicNumberP "P6" = Right P6 magicNumberP t = Left $ "Could not parse \"" T.unpack t "\" as magic number"

此函数现在不会在分析失败时崩溃，但会返回错误消息。

ghci> magicNumberP "P3" Right P3 ghci> magicNumberP "Not a magic number" Left "Could not parse \"Not a magic number\" as magic number"

虽然这似乎有效，但我们遇到了一个问题：我们如何将此解析器与其他解析器组合以完全读取 PNM 文件的标头？我们需要能够将标题的不同部分解析为不同的类型，同时忽略空格、换行符和注释。如图8.3所示。

我们的 magicNumberP 解析器能够解析标头的第一部分，但由此我们无法解析文件的更多部分。这是因为我们的解析器不会返回其余的输入供我们进一步解析。我们可以通过让我们的解析器不仅返回结果，还返回解析后剩余的其余输入来解决此问题。这样我们就可以将其传递给另一个解析器。解析器的最终类型如示例 8.3 所示。分析结果包含其余的输入和运行分析器的解析结果。此外，我们将解析器包装在带有用于访问内部函数的字段的 newtype 中。

type ErrorMessage = String #1 type ParseResult a = Either ErrorMessage (T.Text, a) #2 newtype Parser a = Parser {runParser :: T.Text -> ParseResult a} #3

在本章的其余部分，我们假设我们的模块包含限定名称为 T 的 Data.Text 导入。我们现在可以重写我们的magicNumerP，但在我们完成之前，我们应该考虑为我们的解析器考虑更基本的构建块。我们已经知道我们必须为我们的幻数解析固定字符串，那么为什么不为字符串创建一个通用的解析器呢？

我们可以通过创建一个函数来做到这一点，该函数读取与指定字符串一样多的字符并将它们与该字符串进行比较。如果比较成功，我们可以从输入中删除这些字符并返回结果。这个函数如清单 8.4 所示。

string :: T.Text -> Parser T.Text string str = Parser $ \t -> if T.take (T.length str) t == str #1 then Right (T.drop (T.length str) t, str) #2 else Left $ "failed to parse \"" T.unpack str "\"" #3

此解析器现在可以解析标头的幻数：

ghci> runParser (string "P1") "P1 100 100" (" 100 100",Right "P1") ghci> runParser (string "P1") "P2 100 100" ("P2 100 100",Left "failed to parse \"P1\"")

我们可以看到如果输入不是以指定的字符串开头，解析器是如何失败的，以及它如何在成功解析时返回其余的输入。但是，这还不足以为 MagicNumber 定义解析器，因为我们仍然需要将解析的字符串转换为 Haskell 类型。我们要做的是将我们的解析器文本转换为 解析器魔术数字 .这看起来类似于函子可以做的事情，事实上，函子解析器的实例正是这里所需要的，因为我们想要转换解析器的内部值。

在实例所需的 fmap 定义中，我们可以使用这样一个事实，即函子 要么 和 函子 （（，） a） 实例已经存在。此实例的定义如清单 8.5 所示。

instance Functor Parser where fmap f p = Parser $ \t -> fmap (fmap f) (runParser p t) #1

为什么会这样？由于 fmap 适用于 Any 的 Right 值和元组的最后一个值，因此我们能够转换解析结果的类型和值。

ghci> fmap ( 1) (1,1) :: (Int, Int) (1,2) ghci> fmap ( 1) (Right 1) :: Either Int Int Right 2 ghci> fmap ( 1) (Left 1) :: Either Int Int Left 1

请记住，Right 表示我们的解析器已成功解析，元组的第二个值是解析结果。因此，外部 fmap 应用于 Either 类型，内部 fmap f 应用于 Right 构造函数中的元组。

对于我们的幻数，我们现在可以定义解析器：

ghci> p1P = fmap (const P1) $ string "P1" ghci> :t p1P p1P :: Parser MagicNumber ghci> runParser p1P "P1 100 100" Right (" 100 100",P1) ghci> runParser p1P "P2 100 100" Left "failed to parse \"P1\""

每当我们想应用像 fmap （const X） 这样的表达式时，我们都可以将其简化为 Functor 类型类中的运算符来做到这一点。（<$） 运算符用于为函子映射提供常量值。使用此运算符，我们可以定义解析器：

magicNumberP1P :: Parser MagicNumber magicNumberP1P = P1 <$ string "P1" ... magicNumberP6P :: Parser MagicNumber magicNumberP6P = P6 <$ string "P6"

现在我们为每个幻数提供了一个解析器。为了解析文件的整个头，我们应该担心接下来组合解析器。我们如何利用这些不同的部分来构建更大的结构？

假设我们不是在尝试解析以一般幻数开头的文件，而是解析一个固定的数字。我们将选择 P1 .在此标头中，图像数据没有最大值，因此标头仅由幻数、宽度和高度组成。为了简单起见，我们不担心注释，并假设标题由一行组成，值之间有空格。因此，标头可能如下所示：

P1 100 100

解析任意数量的空间可以通过构造一个解析器来实现，该解析器具有我们从 Data.List 和 Data.Text 中知道的 takeWhile 功能，该功能读取输入，而某些谓词保留输入的字符。由于我们的函数对文本值进行操作，因此我们可以使用 Data.Text 中的函数来构建解析器。如清单 8.6 所示。

takeWhile :: (Char -> Bool) -> Parser T.Text takeWhile p = Parser $ \t -> Right (T.dropWhile p t, T.takeWhile p t) #1

使用它，我们可以为空格和由数字组成的字符串构建解析器：

spaces :: Parser T.Text spaces = takeWhile (' ' ==)

使用 takeWhile 和 fmap，我们还可以为整数定义一个解析器：

integer :: Parser Integer integer = read . T.unpack <$> takeWhile (`elem` ['0' .. '9'])

此解析器的一个问题是它会在空输入上使程序崩溃。稍后我们将为数值编写一个更好的解析器。

现在我们可以为标头定义一个类型：

data Header = Header { width :: Integer, height :: Integer } deriving (Show)

我们希望创建一个解析器标头，并有一种方法将我们的空间和整数组件组合在一起，然后为实际数据类型构建一个解析器。为了清楚地指定标头的预期结构，它可能如下所示：

Header <_> (string "P1" <_> spaces <_> integer) <_> (spaces <_> integer)

这将使我们能够清楚地指示如何读取幻数、宽度和高度，以及哪些解析结果将用作 Header 数据类型中的字段。（<_>） 运算符只是一个占位符。我们需要提出运营商来代替它。无论这些运算符是什么，它们都需要将错误从任何解析器传播到已完成的解析器。

为了更好地理解这个问题，让我们看看 Header 是什么。它是一个构造函数，但它也是整数→整数→标头类型的函数。让我们想象一下，我们可以将类型更改为解析器整数→解析器整数→解析器标头。这将使我们能够插入整数作为两个参数，我们最终会得到 解析器头 .

由此我们可以推断，我们真正想要的是解析器的应用程序进行排序并收集最终结果。我们所说的集合是指结果的任何类型的聚合，其中可能包括忽略某些结果或以某种方式组合它们。我们本质上希望将函数应用于多个解析器值（在本例中为 Header）。

函子类已经为我们提供了 fmap 将一元函数应用于解析器 .那么如果我们将标头应用于整数会发生什么？

ghci> :t Header <$> integer Header <$> integer :: Parser (Integer -> Header)

它会产生一个带有函数作为内部类型的解析器。我们如何从这里继续？我们如何应用这个解析器？这就是一个新的类型类发挥作用的地方： 应用。

应用函子或简称应用函子是对函子的扩展，它允许将函子上下文中的函数应用于上下文中的另一个值，从而使对这些操作进行排序成为可能。为了更清楚地说明这一点，让我们看一下 Applicative 的类定义：

class Functor f => Applicative f where pure :: a -> f a (<*>) :: f (a -> b) -> f a -> f b liftA2 :: (a -> b -> c) -> f a -> f b -> f c (*>) :: f a -> f b -> f b (<*) :: f a -> f b -> f a {-# MINIMAL pure, ((<*>) | liftA2) #-}

这种类型的类最重要的函数是纯函数和（<*>）。Pure用于获取一个值并将其放入由f表示的函数上下文中。（<*>） 用于将上下文中的函数应用于其中的值。本质上，我们可以将此运算符的类型重写为 f （a → b） → （f a → f b），这意味着运算符将上下文中的函数转换为上下文外部的函数。这就是应用剂如此特别的原因。函子可以将普通函数转换为使用函件包装值的函数，如图 8.4 所示。

然而，应用词在函数上下文中发挥功能，并将它们提升到正常上下文中，我们可以在其中组合它。如图8.5所示。

在我们开始担心其他函数之前，让我们看一个示例。也许类型有一个 Applicative 的实例，其中 （<*>） 如果函数包装在 Just 构造函数中的 Just 构造函数中，则应用该函数位于 Just 构造函数中的值上。如果任何 可能 值为“无”，则最终结果也是“无”。

ghci> Just ( 1) <*> Just 1 :: Maybe Int Just 2 ghci> Just ( 1) <*> Nothing :: Maybe Int Nothing ghci> Nothing <*> Just 1 :: Maybe Int Nothing ghci> Nothing <*> Nothing :: Maybe Int Nothing ghci> pure 100 :: Maybe Int :: Maybe Int Just 100

由于我们现在可以愉快地组合函数，因此我们可以将它们应用于 可能上下文中的更多值。

ghci> add3 x y z = x y z ghci> pure add3 <*> Just 1 <*> Just 2 <*> Just 3 :: Maybe Int Just 6

使用纯函数将函数提升到上下文中是很常见的，但是使用部分函数应用程序（就像我们在 Header 示例中看到的那样）和 fmap ，我们可以实现更简洁的语法。

ghci> add3 <$> Just 1 <*> Just 2 <*> Just 3 :: Maybe Int Just 6

但是应用类中的其余函数是什么？liftA2 用于提升任何二进制函数以处理函数上下文中的参数。

ghci> liftA2 ( ) (Just 1) (Just 2) :: Maybe Int Just 3

（<*） 和 （*>） 的特殊之处在于它们丢弃了第一个或第二个参数，但仍会评估其效果。我们的意思是，该论证的结果与最终结果相关。对于 也许 ，如果任何参数在排序时计算为 Nothing，则整个项的计算结果为 Nothing。对于 （<*>） 的这些丢弃版本也是如此。

ghci> Just (1 :: Int) <* Just (2 :: Int) Just 1 ghci> Just 1 <* Nothing :: Maybe Int Nothing

为什么这与我们有关？Applicative 类为我们提供了对解析器进行排序的可能性。此输入将通过在其他解析器留下的输入上按顺序调用后续解析器来按顺序解析。虽然乍一看似乎很奇怪，我们必须为函数值的解析器构造一个函数，但一旦我们应用它，它就有意义了。应用解析器实例的代码如清单 8.7 所示。

instance Applicative Parser where pure x = Parser $ \t -> Right (t, x) #1 (<*>) a b = Parser $ \t -> case runParser a t of #2 Left msg -> Left msg #3 Right (rest, f) -> runParser (fmap f b) rest #4

Pure创建一个解析器，它不消耗任何输入并返回固定值。（<*>） 运算符首先在第一个解析器上运行输入，如果此解析步骤的结果不成功，我们返回 ErrorMessage 和消息的其余部分。否则，我们在其余部分上运行第二个解析器，应用第一个解析器返回的函数 fmap .

现在，我们可以玩 对我们的解析器进行排序 .例如，我们可以规范化两个单词之间的空格。

ghci> :{ ghci| helloWorldP = (\x _ z -> x <> " " <> z) ghci| <$> string "Hello" ghci| <*> spaces ghci| <*> string "World" ghci| :} ghci> runParser helloWorldP "Hello World" Right ("","Hello World") ghci> runParser helloWorldP "Hello World" Right ("","Hello World") ghci> runParser helloWorldP "Helloooo World" Left "failed to parse \"World\""

在这里，我们看到每个解析器如何在前一个解析器留下的给定输入上工作。可以用 （<*） 做出相同的定义：

ghci> :{ ghci| hw = (\x y -> x <> " " <> y) ghci| <$> string "Hello" ghci| <* spaces ghci| <*> string "World" ghci| :}

这使我们最终完成了示例标头的解析器。我们可以使用 （<*>） 从前面使用 （<$>） 来完成它。

ghci> :{ ghci| headerP = Header ghci| <$> (string "P1" *> spaces *> integer) ghci| <*> (spaces *> integer) ghci| :} ghci> runParser headerP "P1 100 200" Right ("",Header {width = 100, height = 200}) ghci> runParser headerP "P2 100 200" Left "failed to parse \"P1\"" ghci> runParser headerP "P1 100 " Right ("",Header {width = 100, height = *** Exception: Prelude.read: no parse

这种写下解析器的应用风格很常见，因此值得研究一下。应用（就像函子一样）在阅读Haskell代码时会遇到的一个非常类，仅仅是因为它能够组合效果，这有助于我们编写仍然可以自由组合但遵循其语义严格规则的代码。所有这些都仅通过类型系统来确保！到目前为止，我们遇到的许多类型，如 也许 ，要么甚至IO都有此类的实例。

应用函子等价于所谓的（松散）幺半函子。我们可以使用它们将两个函数值组合成一个元组，从而组合它们。

class Functor f => Monoidal f where unit :: f () (**) :: f a -> f b -> f (a, b)

要使此类等效于 Applicative，必须能够将一个类的任何实例转换为另一个类。表明这是可能的！

现在，我们已经为简化的标头构建了一个解析器。到目前为止，我们还没有做到的是让解析器接受多个幻数。在我们的示例中，我们也可以允许 P4 作为幻数，但这会使我们的解析器失败。我们必须找到一种在解析器中对替代方案进行编码的方法。答案在另一个类型类中出现。

解析器的 （<*>） 实现可以理解为“然后”语义。第一个解析器解析输入，然后第二个解析器也分析输入。为了对解析器的替代方案进行编码，我们需要实现“or else”语义。这意味着如果第一个解析器失败，则必须将原始输入（不消耗任何内容）传递给第二个解析器，然后希望不会失败。

此确切语义对于 Alternative 类型类的实例是必需的。让我们看看它的定义。

class Applicative f => Alternative f where empty :: f a (<|>) :: f a -> f a -> f a some :: f a -> f [a] many :: f a -> f [a] {-# MINIMAL empty, (<|>) #-}

最小定义（由空和（<|>）组成）看起来与Monoid的定义可疑地相似，事实上，它们是相似的！empty 是 （<|>） 的单位元素，它是 Alternative 的关联二进制操作。事实上，替代是应用函子上的幺半群！

如果 （<*>） 在单个参数失败时失败，则 （<|>） 仅在两个参数都失败时失败。我们可以快速试验这种语义，再次使用 也许.

ghci> Just 1 <|> Just 2 :: Maybe Int Just 1 ghci> Just 1 <|> Nothing :: Maybe Int Just 1 ghci> Nothing <|> Just 2 :: Maybe Int Just 2 ghci> Nothing <|> Nothing :: Maybe Int Nothing

如果我们认为 Nothing 是失败的，我们现在了解了我们的解析器应该如何表现。为了给我们的解析器一些更有意义的错误消息，我们可以编写一个函数来修改解析器的错误消息。如清单 8.8 所示。

modifyErrorMessage :: (ErrorMessage -> ErrorMessage) -> Parser a -> Parser a modifyErrorMessage f p = Parser $ \t -> case runParser p t of #1 Left msg -> Left $ f msg #2 result -> result #3

有了这个函数，我们可以创建一个实例 替代解析器 ，如清单 8.9 所示。对于 empty 成为标识元素，它总是必须失败，因此我们可以编写一个解析器，它甚至不消耗输入，但总是在其结果中返回一些 Left 值。对于 （<|>），我们必须运行第一个解析器，如果失败，则运行第二个解析器，使用我们新的 modifyErrorMessage 函数通过在第一个解析器的错误消息前面加上前缀来修改可能的错误消息。

instance Alternative Parser where empty = Parser $ \_ -> Left "empty alternative" (<|>) a b = Parser $ \t -> case runParser a t of #1 Left msg -> runParser (modErr msg b) t #2 right -> right #3 where modErr msg = modifyErrorMessage (\msg' -> msg " and " msg') #4

有了这个实例，我们现在能够在解析器中对选择进行编码。有趣的是，这可以通过高度嵌套的解析器来完成。因此，如果一个解析器成功解析了大部分输入，然后发现我们的解析不能成功，（<|>）可以回滚以再次尝试使用另一个解析器。让我们看一个例子：

ghci> import Control.Applicative ghci> runParser (string "A" <|> string "B") "A" Right ("","A") ghci> runParser (string "A" <|> string "B") "B" Right ("","B") ghci> runParser (string "A" <|> string "B") "C" Left "failed to parse \"A\" and failed to parse \"B\""

请注意 Control.Applicative 的导入。到目前为止我们讨论的类型类（函子，应用和替代）都在那里定义。为了使用（<|>），需要导入它。

虽然 Alternative 实例本身非常有用，但它还具有另外两个功能：一些和许多。这两个函数都重复应用给定的应用函子，直到它无法再应用，在我们的例子中意味着解析器失败。然后，应用函子的结果将收集到列表中。它们之间的唯一区别是许多永远不会失败。如果第一个应用程序失败，则返回空列表。然而，有些人需要至少一个成功的申请才能成功。在这个意义上，有些意味着一个或多个，许多意味着零或更多。

许多可以这样定义：

many f = some f <|> pure []

要么我们得到一个或多个元素，要么返回一个空列表。但是，我们如何定义一些？尝试为它提出一个实现。

使用这两个函数，我们现在可以创建一个解析器，该解析器经常任意解析某些令牌。

ghci> runParser (many $ string "A") "AAA" Right ("",["A","A","A"]) ghci> runParser (many $ string "A") "" Right ("",[]) ghci> runParser (some $ string "A") "AAA" Right ("",["A","A","A"]) ghci> runParser (some $ string "A") "" Left "failed to parse \"A\""

回想一下我们对空间的定义，它是用takeWhile 解析器实现的。如果我们想创建一个解析器来确保输入中至少存在一个空格，我们可以很容易地做到这一点，如示例 8.10 所示。

someSpaces :: Parser T.Text someSpaces = T.concat <$> some (string " ") #1

最后，我们必须讨论如何使用许多替代解析器写下案例。我们真的想将它们与 （<|>） 运算符大规模组合在一起吗？最好只指定一个解析器列表，然后逐个尝试。这可以通过 Data.Foldable 中的 asum 函数来实现。它使用给定类型的替代实例的语义折叠给定结构。

ghci> :i asum asum :: (Foldable t, Alternative f) => t (f a) -> f a ghci> runParser (asum [string "A", string "B"]) "A" Right ("","A") ghci> runParser (asum [string "A", string "B"]) "B" Right ("","B") ghci> runParser (asum [string "A", string "B"]) "C" Left "failed to parse \"A\" and failed to parse \"B\" and empty alternative")

请注意错误消息如何以“空替代项”结尾。这是我们的替代解析器实现的标识元素的错误消息！asum 实际上将结构的所有元素与 Alternative 给出的幺半群语义相结合，用 （<|>） 折叠它们，最后一个元素为空（这是空结构的默认值）。

一些和许多是根据替代和应用中定义的功能定义的。如果你把一个参数传递给他们，这个论点是恒定的，并且总是成功的，你就会导致一个无限循环！一个例子可能是：一些（仅 1 个）。

使用这个方便的函数，我们可以创建一个用作别名的函数，以使我们的代码更易于理解。

choice :: [Parser a] -> Parser a choice = asum

有了替代方案，我们只剩下一块拼图。几乎可以解析 PNM 文件的标头。我们可以在解析器中对幻数的选择进行编码，能够跳过任意多个空格并读取整数。我们缺少的是一点逻辑，它告诉我们，如果幻数不是 P1 或 P4 时，我们只需要解析数据点的最大值。为了解决可组合性和错误处理的问题，我们从函子升级到应用器。但是，我们现在要解决的这个问题将需要我们更进一步......

到目前为止，解析器仅依赖于它读取的输入，而不依赖于先前解析器的结果。这使得解析器几乎不可能对上下文和已解析数据提供的其他信息进行操作。让我们回顾一下解析 PNM 文件标头时的问题：

P2 3 2 1 1 0 1 0 1 0

此处显示的标头指定最大值为 1 的灰度贴图文件。因此，唯一可能的值是 it 和 0 .此文件的解析器需要读取幻数，从中推断它需要读取最大值，然后继续读取数据。在幻数为 P1 的情况下，将跳过幻数并立即读取数据。在这里，我们必须对读取的幻数进行大小写区分。首先，让我们为 PNM 标头创建一个更具体的类型，如清单 8.11 所示。

data Header = Header { magicNumber :: MagicNumber, #1 width :: Integer, #2 height :: Integer, #2 maxVal :: Maybe Integer #3 } deriving (Eq, Show) #4

我们必须解析标题的幻数、宽度和高度。然后我们必须做出选择。要么我们不解析最大值，因为它不需要，要么我们读取它。我们根据解析的幻数做出此选择。

但是，应用程序不允许这样做！事实证明，它们使我们能够编写解析器，但不能区分大小写。我们不能根据已经读取的值来改变我们的行为。为了解决这个问题，我们必须引入另一个概念。正如应用是函子的扩展一样，现在我们来看看应用函数的扩展：Monad。

Monads是Haskell的核心概念，可能是函数式编程中最有用和最有趣的概念之一。它们允许将值包装成 monadic 类型，并允许任意函数对它们进行操作。正如我们在应用程序中看到的那样，monads 允许这些函数的组合遵守我们可以为用例定义的规则。让我们看一下类型类：

class Applicative m => Monad m where (>>=) :: m a -> (a -> m b) -> m b (>>) :: m a -> m b -> m b return :: a -> m a {-# MINIMAL (>>=) #-}

在哈斯克尔，所有的单子也是应用词。对于 Monad 实例来说，最重要且唯一必需的函数是 （>>=） 俗称绑定。它接收一个一元值 m a 和一个作用于该一元值内部值的函数，返回一个新的一元值，可能是不同类型的 m b 。然后从绑定函数返回此值。第二个函数 （>>） 类似于 （>>=）。它计算第一个一元值，但忽略其结果并返回第二个参数。返回不仅在应用类中看起来像纯值，而且本质上是纯值，将值包装成一元值。

在我们之前，我们将纯的结果称为函子上下文中的值。现在，我们将它们称为一元值，因为这些术语是可以互换的。有时我们将一元值 m a 称为操作，因为它们可能会改变底层 monad 结构中的某些状态。这些操作可以产生效果。区分评估或不评估操作非常重要，因为它可能会产生巨大的差异。

为了了解这个类，我们再次看一个示例实例：Monad May。

ghci> return 1 :: Maybe Int Just 1 ghci> (Just 1) >>= (\x -> return (x 1)) :: Maybe Int Just 2 ghci> (Just 1) >>= (\x -> return (x 1)) >>= (\x -> return (x * 2)) :: Maybe Int Just 4 ghci> Nothing >>= (\x -> return (x 1)) :: Maybe Int Nothing

就像 （<*>） 如果参数是 Nothing 则生成 Nothing 一样，（>>=） 对第一个参数执行相同的操作！在这里，我们可以看到如何使用绑定函数来访问 monad 内部的值（在本例中为 也许）。传递给绑定的函数可以使用我们喜欢的任何语言功能具有任意复杂的行为，只要类型签名签出即可。这意味着我们可以在传递给 bind 的函数中使用 bind ，这允许我们组合任意数量的值，这些值包装在 monadic 类型中。作为一个例子，我们可以看一下清单 8.12 中所示的函数。

monadd :: (Num a, Monad m) => m a -> m a -> m a monadd xm ym = xm >>= #1 (\x -> #1 ym >>= #2 (\y -> #2 return $ x y #3 ) )

此函数接收两个 monad 值，使用 （>>=） 解开它们的包装，并以新的 monadic 值返回它们的总和。

ghci> monadd (Just 1) (Just 2) Just 3 ghci> monadd Nothing (Just 2) Nothing ghci> monadd (Just 1) Nothing Nothing ghci> monadd Nothing Nothing Nothing

通过使用绑定函数，我们可以在处理上述值时构造和组合任意逻辑。需要注意的一点是，我们不必担心失败状态。正如我们从清单 8.12 中的例子中看到的，我们不必担心值为 Nothing（在使用 Maybe 的情况下）。绑定函数确保我们可以访问一个值，否则我们的术语只是计算为 无 .这个特性使我们的monads成为处理副作用的绝佳候选者。

有时我们说Haskell没有副作用。这不是真的。如果Haskell没有副作用，它就不会有IO。Haskell根本没有任意的副作用，而是受控的副作用，这些副作用通过类型系统与纯代码明确分开！

事实上，我们从第 3 章开始就一直在使用 monads！事实证明，IO是一个monad。在 IO 中完成的副作用在绑定函数中控制和处理。我们在 IO 中使用的返回函数正是来自 Monad 类型类的返回。事实证明，我们在不知情的情况下使用了 IO 的绑定函数。Haskell提供的do符号是绑定函数的语法糖！

m >>= f

这个简单的术语相当于：

do x <- m f x

另一个绑定函数更容易翻译。

m1 >> m2

该术语变为：

do _ <- m1 m2

请注意，这个截图如何清楚地表明将计算第一个参数。通过了解绑定和 do 表示法之间的关系，我们可以快速重写示例，从清单 8.12 改写为 使用 do 表示法：

monadd' :: (Num a, Monad m) => m a -> m a -> m a monadd' xm ym = do x <- xm y <- ym return $ x y

do符号清楚地表明何时以及如何使用来自一元值评估的值。

在我们深入讨论 monads 之前，我们首先应该看看如何在解析器中使用它们。为了创建一个Monad Parser实例，我们必须定义函数返回和（>>=）。对于返回的实现，我们可以简单地使用来自应用实例的纯值。bind 函数需要评估作为第一个参数给出的解析器，然后使用此解析器的结果评估作为第二个参数给出的函数，并对其余输入运行生成的解析器（来自函数的评估）。如示例 8.13 所示。在第一个解析器失败的情况下，我们必须短路，因为函数不存在任何值，所以我们只是在这一点上失败。

instance Monad Parser where return = pure #1 (>>=) p f = Parser $ \t -> case runParser p t of #2 Left msg -> Left msg #3 Right (rest, x) -> runParser (f x) rest #4

使用它，我们现在可以使用do表示法来编写我们的解析器！

helloWorldP = do h <- string "Hello" _ <- someSpaces w <- string "World" return $ h <> " " <> w

将此与本章前面的应用符号进行比较。功能仍然相同。正如预期的那样，在 do 块中解析失败会导致整个解析器失败。

ghci> runParser helloWorldP "Hello World" Right ("","Hello World") ghci> runParser helloWorldP "Hello World" Right ("","Hello World") ghci> runParser helloWorldP "Bye Bye World" Left "failed to parse \"Hello\""

然而，我们没有引入monads来取代应用，而是扩展它们。具体来说，我们希望能够根据已经读取的值做出决策。这可能包括转换解析的字符串，这使我们有机会改进以前的整数解析器。

通过使用 do 表示法，我们可以像以前一样读取数值。然后，通过使用 readMay，我们可以检测转换为整数值是否失败或成功。这看起来像示例 8.14 所示的代码。

integer :: Parser Integer integer = do intStr <- takeWhile (`elem` ['0' .. '9']) #1 case readMaybe (T.unpack intStr) of #2 Just value -> return value #3 Nothing -> #4 Parser $ \_ -> Left $ "Could not convert \"" T.unpack intStr "\" as an integer"

此解析器现在可以安全地从输入中读取字符，并将转换失败转换为解析器故障。我们可以这样做，因为monads允许我们对先前操作的评估产生的值采取行动。

现在，我们终于能够为我们的标头构造一个解析器。我们读取幻数、至少一个空格、宽度、至少一个空格、高度，然后可以选择更多的空格和基于幻数的最大值。这是通过示例 8.15 中所示的解析器实现的。

headerP :: Parser Header headerP = do magicNumber <- choice #1 [ magicNumberP1P, magicNumberP2P, magicNumberP3P, magicNumberP4P, magicNumberP5P, magicNumberP6P ] _ <- someSpaces #2 width <- integer #3 _ <- someSpaces #2 height <- integer #3 maxVal <- do #4 if magicNumber == P1 || magicNumber == P4 then return Nothing #5 else Just <$> (someSpaces *> integer) #6 return Header {..} #7

此处介绍的标头解析器使用了我们到目前为止讨论的所有概念。本章前面介绍的幻数解析器是按选择组合的。选择列表中分析幻数的第一个解析器。由于它们解析不同的字符串没有歧义，因此我们按哪个顺序写下它们真的无关紧要。但是，如果一个解析器仅解析另一个解析器的前缀，则顺序很重要。我们使用 someSpaces 来解析，但忽略值之间的空格。

我们使用 _ ← someSpaces 通过指示结果值不应分配给任何名称来忽略空格，因此我们使用 _ .我们必须这样做，因为 someSpace 的结果不是 （） ，否则我们可能会失去绑定值。这可以通过 Control.Monad 中的 void 函数来简化，将结果映射到 （）。因此，可以重写它以取消某些空间，这清楚地表明我们忽略了操作的结果。

宽度和高度由清单 8.14 中的整数解析器解析。 最大值的解析器在一个新的 do 块中构造。在这里，我们可以对之前解析的值进行大小写区分。在我们需要解析最大值的情况下，我们也解析了一些空格，但使用 Applicative 实例中的 （*>） 忽略它们。值得注意的是，如果这些解析器中的任何一个失败，整个解析器都会失败。这是 monads 的重要属性，它使我们更容易构建更复杂的应用程序，同时不必考虑影响和错误，因为它们是由 Monad 实例的定义处理的。

如果不对monads进行一些进一步的讨论，本节将是不完整的。关于函子、应用器和单子，需要注意一些事项：

• 它们帮助我们使用类型系统将纯代码与有效代码分开
• 它们是处理效果的一种方法
• 它们并不总是引用透明的
• 他们遵循特定的规则

应用程序词和monads最重要的属性之一是它们如何帮助我们管理和控制纯代码的效果。仅从它们的定义来看，我们看到的类是纯粹的，但它们能做的不一定是纯粹的。IO monad就是一个很好的例子。在IO monad中，我们可以与环境进行交互。这是一种效果！然而，这不是我们通常认为的副作用，因为它不会发生在我们的纯函数中，而是发生在 IO monad 之外。当然，为了让Haskell程序做任何有用的事情，必须得出合乎逻辑的结论，即我们所有的代码都必须存在于IO monad中。这就是为什么主要类型是 IO （） 的原因。

这应该让我们思考。为什么我们不能摆脱单子？为什么没有类型 （Monad m） => m a -> a 的函数允许我们在纯代码中访问 monad 中的值？因为它会使我们使用 monad 的原因无效！Monad 类给出的方法只允许我们将值引入 monadic 上下文（使用 return），但除了使用 bind 函数外，不允许提取它们。这是故意的。如果不仔细处理我们可能管理的任何状态，我们就无法摆脱 monads。

举个例子，让我们看一下 May monad。在失败的情况下，它通常采用“无”值。一个函数 也许 a -> a 不能为这种类型构造，而不会使函数部分化。from也许确实为我们提供了相同的功能，但需要一个默认值。因此，我们可以突破 May monad，但我们需要确保我们可以自己处理可能的错误状态。

对于 IO 来说，这几乎不是真的。函数 unsafePerformIO 能够突破 IO monad。但是，使用它可能会导致意想不到的效果，例如效果产生顺序错误或多次应用。在更复杂的代码中，unsafePerformIO 甚至会导致运行时出现类型错误。

这几乎是不言而喻的，但你不应该使用 不安全的执行IO .大多数可以通过它解决的问题也可以通过其他方式解决。如果你正在使用它，你应该真正知道你在做什么，并确保它的使用不会导致你的程序出现问题。

Monads并不是处理效果的全部和最终目的。它们是处理影响的一种可能方法。其他语言实现自己的效果系统，通常提供部分支持。Java 要求程序员指定可以从方法中抛出哪些异常。然后，调用函数需要指定它也可以引发该异常或处理异常。这是一个在异常领域处理效果的系统。

我们希望函数是纯函数的一个原因是引用透明。简而言之，这意味着我们能够在不更改程序结果的情况下将函数应用程序替换为其结果值。这里有一个小例子：

f x = x 1

项 f 1 的计算结果总是为 2，因此我们用值 1 替换 f 2 没有区别。实际上，我们程序中所有出现的f 1都可以更改为2。如果我们的所有函数都是引用透明的，我们可以用之前发生的相同应用程序的结果替换它们的所有应用程序。可悲的是，并非我们所做的一切都可以参考透明。IO monad 和像 getLine 这样的操作就是一个微不足道的例子。从文件中读取用户输入或数据，与网络或其他接互或生成随机数。所有这些都不是参考透明的。幸运的是，我们可以（并且确实）在IO和其他monads中分离出这些。虽然像 may monad 这样的 monad 在引用上是透明的，但 monads 不一定是。

最后，让我们谈谈法律和秩序。就像我们在半群和幺半群中看到的那样，函子、应用和一元的实例应该遵循一定的定律。附录B对这些法律进行了更彻底的探讨。最重要的规则之一是纯和回报的定义应该是相同的。

事实证明，应用比Monad有更多的实例。在为一元结构编写一般函数时，记住这一点很重要。有时我们可以保持函数更通用，只需要假设一个应用实例，这使我们能够在更多类型上使用我们的代码。

我们最不想处理的就是失败。失败是人性的一部分，我们解析工作的本质也是如此。分析可能会失败。事实上，我们已经在函数中对失败的解析进行了建模。字符串和整数可能会失败。我们可以概括这种行为吗？事实证明，我们可以通过更多类型类的帮助。

第一个是在Control.Monad.Fail模块中提供给我们的，称为MonadFail。引入它是为了解决 monad 内部模式匹配时出现的问题。下面是一个示例：

mhead :: (Monad m) => m [a] -> m a mhead m = do (x : _) <- m return x

这个一元版本头的定义不编译！原因是在列表中执行的隐式和不完整模式匹配。模式匹配可能会失败。在这种情况下，不清楚如何在 monad 中进入内部故障状态。这就是 MonadFail 类型类的用武之地，它通过 fail 方法提供此功能。该类相当简单：

class Monad m => MonadFail m where fail :: String -> m a

Fail 会收到一条错误消息（可以选择完全忽略该消息），并且必须提供响应故障的 monadic 值。因为也许这是相当微不足道的。失败只是忽略消息并导致 Nothing 。

现在，我们可以更改一元头函数的类型：

mhead :: (MonadFail m) => m [a] -> m a mhead m = do (x : _) <- m return x

它现在可以编译，我们可以尝试一下：

ghci> mhead (return [1]) :: Maybe Int Just 1 ghci> mhead (return []) :: Maybe Int Nothing ghci> mhead (return [1]) :: IO Int 1 ghci> mhead (return []) :: IO Int *** Exception: user error (Pattern match failure in 'do' block at ...

对于 IO monad，我们会收到一个异常。我们还没有介绍如何处理异常，但将在下一章中介绍。此外，事实证明，即使不使用无可辩驳的模式提供 MonadFail 实例，也有办法让 mhead 进行编译。关于这些问题的讨论见附录B。

为了处理这个问题并更普遍地处理故障，我们可以为我们的解析器类型提供一个 MonadFail 实例。我们已经看到了如何在 empty 的定义中对这样的失败状态进行编码，并在整数解析器中对错误进行编码。

instance MonadFail Parser where fail s = Parser $ \t -> Left s #1

该实例如清单 8.16 所示。这将允许我们在无法继续解析时使用 fail。使用它，我们可以清理我们的整数解析器：

integer :: Parser Integer integer = do intStr <- takeWhile (`elem` ['0' .. '9']) case readMaybe (T.unpack intStr) of Just value -> return value Nothing -> fail $ "Could not convert \"" T.unpack intStr "\" as an integer"

赋予 monads 失效能力的另一种方法是 MonadPlus 类型类。类似于替代是应用的幺半群，MonadPlus是单子的幺半群！它的定义与替代非常相似：

class (Alternative m, Monad m) => MonadPlus m where mzero :: m a mplus :: m a -> m a -> m a

事实证明，mzero 的默认实现为空，mplus 的默认实现为 （<|>） ，两者都来自 Alternative 类型类。如果我们想在定义 MonadPlus 解析器实例时使用这些默认实现，我们可以在一行中执行此操作：

instance MonadPlus Parser

但是，我们可能需要更改 mzero 方法的错误消息。如清单 8.17 所示。

instance MonadPlus Parser where mzero = modifyErrorMessage (const "mzero") empty #1

在此定义中使用空是故意的，因为我们希望反映 mzero 中空定义的变化。两者的行为方式应相似。MonadPlus ，类似于 替代 ，允许我们实现失败，在 monads （ msum ） 和对操作结果的过滤器 （ mfilter ） 之间进行选择。

ghci> smallerTen = mfilter (< 10) integer ghci> greaterTwenty = mfilter (> 20) integer ghci> px = msum [smallerTen, greaterTwenty] ghci> px' = modifyErrorMessage (const "value not < 10 or > 20") px ghci> runParser px' "1" ("",Right 1) ghci> runParser px' "100" ("",Right 100) ghci> runParser px' "15" ("15",Left "value not < 10 or > 20")

请注意，这些函数不仅适用于我们的解析器类型。它们适用于所有单子。许多函数如 msum 和 mfilter 在 Control.Monad 和 Control.Applicative 中定义，可帮助您更好地组合功能。

关于单子的讨论到此结束。虽然这似乎是一个无关紧要的转移，但了解它们非常重要。Monadic编程是一种帮助我们控制效果的范式，而Haskell的独特之处在于它的核心语言支持它。

到目前为止，我们的解析器能够处理图像文件的标头。现在，是时候扩展它以最终读取完整的图像数据了。

我们已经介绍了如何编写可组合且抗故障的解析器。此外，我们已经看到了如何为 PNM 文件的标头实现一个。现在是时候为整个图像文件构建一个解析器了，这意味着解析标头并继续解析图像数据。在解析过程中，我们必须验证数据是否足够或太多，以及是否超过了标头中找到的可选最大值。

此外，我们需要讨论一个问题，到目前为止我们一直忽略。根据幻数，数据可能不会以文本形式提供给我们，而是以字节的形式提供给我们。我们的解析器不支持这一点。此外，我们的解析器有局限性，缺乏对许多事情的支持：

• 解析器不会跟踪解析输入中的位置
• 因此，它不知道已经解析了多少数据
• 其错误消息不包括语法错误的位置
• 解析时必须存在完整的输入
• 因此不支持流输入（来自文件或网络）
• 我们需要将完整的输入加载到内存中，然后才能开始解析
• 仅支持文本作为输入
• 无法解析二进制数据
• 分析器无法检测到编码问题，并失败并显示一般错误消息

解决这些问题并非易事，这就是为什么我们要将注意力转向一种新型的解析器，它可以解决所有这些问题。解析的主题在 Haskell 的世界中得到了广泛的研究。一些图书馆已经从这项工作中脱颖而出。也许最有影响力的是Parsec库，它有一个与我们编写的解析器非常相似的解析器。该库的主要思想是monadic解析器可以从解析器组合器构建。这些组合器只是一等函数。我们已经在不知道的情况下使用了解析器组合器，比如takeWhile，choice和monadic绑定函数。

具有许多有用的解析器组合器的库是解析器组合器库。它具有诸如 between 这样的函数，它将解析器应用于输入的开头、中间和结尾，以及跳过解析器的零个或多个成功应用程序的 skipMany。以下是示例：

ghci> import Control.Monad.Combinators ghci> parenInteger = between (string "(") (string ")") integer ghci> runParser parenInteger "(123)" ("",Right 123) ghci> runParser parenInteger "(123" ("",Left "failed to parse \")\"") ghci> skipSpaces = skipMany $ string " " ghci> integerWithSpaces = between skipSpaces skipSpaces integer ghci> runParser integerWithSpaces " 123 " ("",Right 123)

查找库提供的函数，并尝试自己重新实现它们！

Haskell最先进的解析器组合器库是Megaparsec和Attoparsec。Megaparsec是解析器组合器库的瑞士军刀。它可用于解析文本或字节，提供对详细错误消息的强大支持，并具有多种方法来更好地控制解析器的行为方式。另一方面，Attoparsec 是一个高度专业化的库，用于为原始字节数据构建解析器，重点是性能。一个值得注意的功能是对增量输入的内置支持，因此可以在开始解析之前无需将完整的文件内容加载到内存中即可解析大文件。但是，应该注意的是，由于解析器支持任意回溯，一旦完全提供给解析器，整个输入将驻留在内存中。

出于我们的目的，我们希望将注意力转移到 Attoparsec 上，并用它为 PNM 文件构建一个解析器。事实上，这应该是一个简单的切换，因为库中的解析器在大多数情况下的行为与我们的解析器一样。就像我们的库一样，Attoparsec具有字符串函数。但是，解析器不处理文本，而是处理字节字符串类型。这种类型具有类似于 文本 ，由字节串包提供，因此我们可以将其视为替代我们通常处理文本数据的方式。

ByteString 是一种类似列表的数据结构，其元素类型为 Word8 的值，这些元素是 8 位无符号整数。这意味着单个字符只是 0 到 255 之间的整数。Data.ByteString.Internal 模块为我们提供了函数 c2w 和 w2c 来转换 Char 到 Word8 并返回，如果我们想将我们的普通 Char 类型与 字节字符串 结合使用。幸运的是，实例IsString ByteString已经存在，因此我们可以写下普通字符串并将它们重新解释为ByteString。

为了让我们使用新类型和新库，我们必须将 bytestring 和 attoparsec 添加到 package.yaml 中的依赖项中。完成此操作后，让我们尝试新类型。Attoparsec解析器由非常简单的构建块组成。它的中心类型是用于解析字节字符串值的解析器类型。此类型和解析所需的大多数函数都可以从 Data.Attoparsec.ByteString 模块导入。还有 Data.Attoparsec.Text 模块，它公开了处理 Text 值的等效函数和类型，就像我们的解析器一样。但是，由于我们需要处理二进制数据，我们将选择前者。

ghci> import Data.Attoparsec.ByteString as AP ghci> AP.parse (AP.string "Hello") "Hello" Done "" "Hello" ghci> AP.parse (AP.string "Hello") "hello" Fail "hello" [] "string" ghci> AP.parse (AP.string "Hello") "He" Partial _

我们使用限定名称在 GHCi 中导入模块，以便我们可以使用它而不会与其自己的解析器模块冲突。如我们所见，该模块导出了一个类型为 ByteString -> 解析器 ByteString 的字符串函数，其工作原理与我们之前的字符串函数一样。parse 是 Parser a -> ByteString -> Result a 类型的函数，它将解析器应用于给定输入。Result 类型与我们在解析器中构建的类型略有不同。它有三个构造函数：完成以成功解析，在失败时失败，如果解析器没有严格失败但没有足够的输入来完成解析，则为部分。“完成”和“失败”在其第一个字段中携带其余未分析的输入。但是，Partial 包含一个可用于其余输入的延续函数。

ghci> Partial c = AP.parse (AP.string "Hello") "He" ghci> Partial c2 = c "l" ghci> c2 "lo" Done "" "Hello"

在此示例中，我们忽略来自不完整模式匹配的编译器警告。如我们所见，部分结果中的函数可用于增量解析输入。在本章中，我们在很大程度上对这个功能不感兴趣，只解析整个输入。为此，我们可以使用类型为 Parser a -> ByteString -> 任一字符串 a 的 parseOnly 函数，它与我们的 runParser 函数非常相似。事实上，它们的工作方式都是一样的。来自 parseOnly 的结果不能是“部分”，要么成功，要么失败。

我们有一个很好的函数集合来构建解析器：

• word8 ：： word8 -> 解析器 word8
• 从输入中读取特定字节
• anyWord8 ：： Parser Word8
• 从输入中读取任何字节
• 字符串 ：： 字节字符串 -> 解析器字节字符串
• 读取特定的字节字符串
• skipWhile ：： （word8 -> bool） -> parser （）
• 只要给定谓词有效，就会跳过字节
• 采取 ：： int -> 解析器字节字符串
• 读取特定数量的字节
• takeWhile ：： （Word8 -> Bool） -> 解析器字节字符串
• 只要给定谓词有效，就读取字节

如我们所见，这些功能中的大多数都是专门用于处理的 Word8 。如果我们想使用 Char，我们可以使用 Data.Attoparsec.ByteString.Char8 模块，该模块公开了用于解析 ASCII 字母、数字的函数，并且通常更容易处理 Char 值。

现在我们可以认真地解析我们的图像数据了。首先，让我们定义我们正在使用的数据类型。我们已经为我们的标题提供了一个类型，但我们想提供一个小的调整。PNM 文件中任何数据的绝对最大值为 65535，这是 16 位无符号整数的最大值。这可以用 Data.Word 模块中的 Word16 表示。因此，我们将用 也许 Word16 将可能整数切换为我们的可选最大值。实际的原始数据只是一堆 Word16 值。我们可以瞄准一种更紧凑的存储像素值的方式，因为将 16 位用于位图有点浪费，但我们目前没有优化我们的框架。这些类型如清单 8.18 所示。

data MagicNumber = P1 | P2 | P3 | P4 | P5 | P6 #1 deriving (Eq, Show) data Header = Header #2 { magicNumber :: MagicNumber, width :: Integer, height :: Integer, maxVal :: Maybe Word16 } deriving (Eq, Show) data RawPixel = Single Word16 #3 | RGB Word16 Word16 Word16 #4 deriving (Eq, Show) newtype RawData = RawData #5 { pixels :: [RawPixel] } deriving (Eq, Show) data PNM = PNM #6 { header :: Header, imageData :: RawData } deriving (Eq, Show)

为了使用 Attoparsec 为标头构建一个解析器，我们必须对标头的初始解析器进行一些小的调整。我们将借此机会用库提供的函数替换我们自己编写的函数。在下面的代码清单中，我们将假定要导入这些模块：

import Data.Attoparsec.ByteString import qualified Data.Attoparsec.ByteString.Char8 as C8 import qualified Data.ByteString as BS

覆盖了这些模块后，我们就可以开始解析我们的标头了。解析幻数与我们之前的解析器实现没有变化。由于库 Parser 类型具有与我们的定义等效的函子、应用器和 Monad 实例，因此我们可以使用 （<$） 运算符来解析输入并返回一个 MagicNumber，如示例 8.19 所示。

magicNumberP1P :: Parser MagicNumber magicNumberP1P = P1 <$ string "P1" #1 ... magicNumberP6P :: Parser MagicNumber magicNumberP6P = P6 <$ string "P6" #2

通过这种方式，我们可以解析一个固定的字符串，并立即将其转换为Haskell值。

使用 OverloadStrings，我们实际上可以省略使用固定字符串解析器的字符串。只需像这样写下字符串就足够了：P1 <$ “P1” .但是，这可能不如显式使用字符串那样可读，这就是为什么我们选择不在本章中使用此快捷方式的原因。

Data.Attoparsec.ByteString.Char8 模块还为我们提供了一个整数解析器的替代品，即 Integral a => 解析器 a 类型的十进制解析器，用于解析十进制值。我们必须解决的一个问题是跳过空格。在 PNM 格式中，空格是以下任何字符：' ' ， \n ， \r ， \f ， \v 和 \t 。与之前类似，我们可以使用 满足 并检查给定的 Char 是否是我们认为是空格的字符。但是，在某些时候，我们希望解析至少一个空格字符。为此，我们可以使用 skipMany1，它至少应用一次给定的解析器并完全忽略读取值。如清单 8.20 所示。

whitespace :: Parser () whitespace = void $ #1 C8.satisfy $ #2 \c -> #3 c == ' ' || c == '\n' || c == '\t' || c == '\r' || c == '\v' || c == '\f' whitespaces :: Parser () whitespaces = skipMany1 whitespace #4

接下来，我们还希望能够解析（然后忽略）标题中可能发生的注释。此类注释以 % 字符开头，并在换行符中的某个点结束。我们可以通过使用 char ：： char -> 解析器将其转换为解析器，以读取字符并采取 While 读取字符，直到找到换行符。解析器的代码如示例 8.21 所示。

comment :: Parser BS.ByteString comment = C8.char '%' >> C8.takeWhile (/= '\n') #1

值得注意的是，这个解析器需要读取注释，所以如果我们想使用它来选择性地解析注释，我们需要忽略失败。在我们的标题中，我们希望忽略空格和注释。可悲的是，我们不知道它们何时会出现在标题中，因此我们需要在幻数和我们正在读取的其他值之间忽略它们。为此，我们可以构造另一个解析器，以跳过这些无关的信息。

skipWhitespace :: Parser () skipWhitespace = option () $ #1 choice #2 [ comment >> skipWhitespace, #3 whitespaces >> skipWhitespace #4 ]

正如我们在示例 8.22 中看到的，我们可以构造这个跳过空格的解析器，方法是提供读取注释或空格的选项，然后再次递归调用解析器以读取另一个注释或一组空格。但是，如果我们遇到真实数据并且解析这些东西失败怎么办？为了解决这个问题，我们使用选项 ：： 替代项 f => a -> f a -> f a 尝试应用第二个参数中的操作，如果失败，则提供第一个参数给出的默认值。

现在，我们可以组合所有这些解析器来解析清单 8.18 中的新标头类型。在解析器的元素之间，我们允许使用任意注释和空格 skipWithespace .在标头的末尾，我们还解析单个空格，因为规范要求标头以一个空格结尾。这一次，我们使用 Data.Attoparsec.ByteString.Char8 中的十进制来解析 Word16 值。除此之外，与我们上次的实现相比没有太大变化。新解析器的代码如清单 8.23 所示。

headerP :: Parser Header headerP = do skipWhitespace magicNumber <- choice #1 [ magicNumberP1P, magicNumberP2P, magicNumberP3P, magicNumberP4P, magicNumberP5P, magicNumberP6P ] skipWhitespace width <- C8.decimal #2 skipWhitespace height <- C8.decimal #2 maxVal <- do if magicNumber == P1 || magicNumber == P4 then return Nothing else Just <$> (skipWhitespace *> C8.decimal) #3 whitespace return Header {..}

处理完标题后，我们现在可以开始解析图像数据了。

PNM 文件格式中的不同格式对其数据进行编码的方式都不同。让我们回顾一下不同的格式。对于幻数 P1（位图）、P2（灰度图）和 P3（像素图），数据以 ASCII 编码。对于位图，只有两个可能的值，即 1 和 0，对于灰度图和像素图，接受的值取决于标题中给出的最大值。像素值是灰度贴图的单个十进制值和像素图中每个像素的三个十进制值。幻数 P4（位图）、P5（灰度图）和 P6（像素图）具有类似的规则。但是，数据以二进制编码。对于二进制位图，每个位对应于单个像素，其中像素的出现顺序与位的顺序相同，这意味着必须逐字节读取文件，将位从最高有效位解析为最低有效位。当必须读取的像素数不能被 8 整除时，超浮位将被忽略。对于二进制灰度贴图和像素图，其规则与 ASCII 对应项相同。但是，根据最大值应用特殊规则。默认情况下，单个字节构成一个值。如果最大值大于 255，则该值无法放入单个字节，因此必须为每个像素值读取两个字节。

让我们从为 ASCII 编码文件编写解析器开始。目前，我们只对解析单个像素感兴趣，稍后将使用它们来解析完整数据。从上面的讨论中我们知道位图的像素数据归结为解析常量（1和0）。解析灰度图和像素图需要我们解析十进制值。在我们的解析器中，我们不会立即检查是否超过了标头中给出的最大值。我们只对解析文件中存在的原始数据感兴趣。这些解析器的代码如示例 8.24 所示。

p1PixelP :: Parser RawPixel p1PixelP = Single <$> choice #1 [ 1 <$ C8.char '1', 0 <$ C8.char '0' ] p2PixelP :: Parser RawPixel p2PixelP = Single <$> C8.decimal #2 p3PixelP :: Parser RawPixel p3PixelP = do #3 r <- C8.decimal whitespaces g <- C8.decimal whitespaces b <- C8.decimal return $ RGB r g b

类型为 Integral a => Parser a 的十进制解析器可以解析任何整数值。Haskell能够推断出在我们的实例中解析的值是 Word16 的类型 ，因为这些是为构造函数给出的类型。在 p1PixelP 和 p2PixelP 的实现中，我们使用 （<$>） 将单个值的构造函数应用于解析的数据。对于 p3PixelP，我们使用 do 表示法来解析十进制值之间的任意数量的空格，因为文件格式的规范不强制要求在十几个值之间固定数量的空格。

处理好ASCII编码像素后，我们接下来可以处理二进制格式。首先，让我们讨论灰度图和像素图，因为位图有些特殊。对于这两种格式，我们实际上需要为每个幻数两个解析器，因为我们要么需要读取一个字节（Word8）要么需要两个字节（Word16）来获取值。Attoparsec已经为我们提供了anyWord8 ：： Parser Word8解析器，它读取一个字节。但是，没有任何Word16解析器可供我们使用，这意味着我们必须构建自己的解析器。

为了编写这个解析器，我们必须考虑如何将多个字节组合成一个更大的单词。假设我们有两个紧挨着的字节。我们想将它们读作 Word16 .我们可以做的是连续读取第一个字节，然后读取第二个字节。为了组合它们，我们必须将它们重新解释为 16 位字，并将第一个字节向左移动 8 位。这样，字节将填满 8 位字的前 16 位，并在其下半部分为在其后读取的字节腾出空间。假设将值向左移动只会在第一个字节被写下来的地方留下 0，我们可以通过执行按位 OR 运算来插入第二个字节。这样，第二个字节中为 0 的值将保持 0，而 1 的值将变为 1 。

这种低级操作被提供给我们作为Data.Bits模块。在那里我们找到了 Bits 类型类，它为各种数据类型定义了按位运算，其中包括我们的字类型 Word8 和 Word16 .在此类中，我们还发现方法 shift ：： a -> Int -> a 向左移动一个值，以及 （.|.） ：： a -> a -> 执行按位 OR 运算的运算符。让我们快速实验一下。

ghci> import Data.Word ghci> import Data.Bits ghci> byte1 = 1 :: Word8 ghci> byte2 = 1 :: Word8 ghci> shift byte1 8 0 ghci> shift (fromIntegral byte1 :: Word16) 8 256 ghci> byte1_16 = fromIntegral byte1 :: Word16 ghci> byte2_16 = fromIntegral byte2 :: Word16 ghci> shift byte1_16 8 .|. byte2_16 257

正如我们所看到的，将具有单个位（作为其最低有效位）的 Word8 移动 8 位会导致 0，因为我们在单个字节中的空间不足。但是，通过使用fromIntegral将其转换为Word16，为要移动的位腾出了空间。正如我们也可以看到的，将一个字节移动 8 位并用第二个字节执行按位 OR，可以有效地按照我们想要的顺序将两者结合起来。如图 8.6 所示。

我们可以使用它来构建我们的 anyWord16 解析器，方法是读取两个字节并以上述方式组合它们。它的实现如清单 8.25 所示。

anyWord16 :: Parser Word16 anyWord16 = do h <- fromIntegral <$> anyWord8 #1 l <- fromIntegral <$> anyWord8 #1 return $ shift h 8 .|. l #2

同样，我们使用fromIntegral将我们的Word8值转换为Word16，以便按位运算起作用。有了这个功能，我们可以为8位和16位的灰度和像素图构建解析器。它们的实现（如示例 8.26 所示）非常简单，因为这次我们不必担心空格。

p5PixelWord8P :: Parser RawPixel p5PixelWord8P = Single <$> (fromIntegral <$> anyWord8) #1 p5PixelWord16P :: Parser RawPixel p5PixelWord16P = Single <$> anyWord16 #2 p6PixelWord8P :: Parser RawPixel p6PixelWord8P = RGB <$> p <*> p <*> p #3 where p = fromIntegral <$> anyWord8 p6PixelWord16P :: Parser RawPixel p6PixelWord16P = RGB <$> anyWord16 <*> anyWord16 <*> anyWord16 #4

现在剩下的就是使用二进制位图。如前所述，我们必须按位解析这些文件，这意味着每个位都是一个像素值。我们无法按位解析文件，因此我们必须重新考虑如何从读取的字节中提取值。同样，来自 Data.Bits 的 Bits 类型类为我们提供了一个有用的函数来实现这个称为 testBit ：： a -> Int -> Bool，它允许我们检查某个偏移量处的值位。使用此函数，我们可以解析单个字节并从中返回八个像素值。如示例 8.27 所示，我们可以看到二进制像素映射格式的像素值解析器的实现。

p4PixelP :: Parser ( RawPixel, RawPixel, RawPixel, RawPixel, RawPixel, RawPixel, RawPixel, RawPixel ) p4PixelP = do w <- anyWord8 #1 let parseBitAtIndex n = Single $ if testBit w n then 1 else 0 #2 return ( parseBitAtIndex 7, #3 parseBitAtIndex 6, #3 parseBitAtIndex 5, #3 parseBitAtIndex 4, #3 parseBitAtIndex 3, #3 parseBitAtIndex 2, #3 parseBitAtIndex 1, #3 parseBitAtIndex 0 #3 )

在此实现中，我们在元组中单独解析每个位，因为我们已经知道 Word8 值中有多少位。我们将这些值从最有效位到最低有效位解析，就像为 PNM 文件指定的那样。这样我们就可以访问每个位值。但是，在解析完整文件时，我们需要确保忽略不再是图像一部分的超浮位（如果图像的像素总量不能被 8 整除）。

通过为单个像素值构建解析器，我们现在可以为图像文件的主体构建解析器。

图像文件主体的解析器可以通过对已经解析的标头进行大小写区分来构建，并根据给定的幻数和最大值，我们从上一小节中选择其中一个解析器来读取数据。由于除二进制位图解析器之外的所有解析器都读取单个 RawPixel 值，因此我们可以根据需要像素（宽度乘以图像的高度）多次简单地重复其应用。此外，我们构造了一个可选的空格解析器，可用于我们的 ASCII 编码数据。对于位图，数据中不需要空格，但我们仍然允许它们捕获换行符。对于二进制灰度和像素图，我们必须根据给定的最大值选择正确的解析器。否则我们会忽略它。我们这样做是因为如果值大于标头中的最大值，我们的解析器在此阶段不应失败。我们想稍后检查这些属性。唯一的特殊情况是二进制位图，其解析方式必须略有不同。我们将很快介绍此案例。对于不，让我们讨论清单 8.28 中给出的图像数据解析器的实现。

dataP :: Header -> Parser RawData dataP (Header {..}) = do pixels <- case (magicNumber, maxVal) of (P1, _) -> count' $ whitespaces' *> p1PixelP #1 (P2, _) -> count' $ whitespaces' *> p2PixelP #1 (P3, _) -> count' $ whitespaces' *> p3PixelP #1 (P4, _) -> p4DataP width' height' #1 (P5, Just mv) -> count' $ #1 if mv <= 255 #2 then p5PixelWord8P #2 else p5PixelWord16P #2 (P6, Just mv) -> count' $ #1 if mv <= 255 #2 then p6PixelWord8P #2 else p6PixelWord16P #2 _ -> error $ #3 "Internal error: " show magicNumber " without maximum value in header!" return $ RawData pixels where whitespaces' = option () whitespaces #4 count' = count (width' * height') #5 width' = fromInteger width height' = fromInteger height

count' 函数根据需要多次应用给定的解析器。幻数和最大值的情况提供了正确的操作，评估该操作以读取像素值。我们的类型允许 P5 和 P6 可以在没有最大值的情况下发生。但是，这是不允许的，这应该会导致内部错误。如果发生这种情况，标头分析器应该失败。因此，如果我们真的遇到这个问题，这意味着我们的标头解析器以某种方式表现出不正确的行为。

正如我们所看到的，我们所有的解析器都与count一起使用，除了二进制位图的解析器。这是因为我们从不从解析器中读取单个 RawPixel 值，而是一次读取八个。我们必须构造一个算法来解析字节中的值，但一旦解析了足够的值就会停止。此外，这些二进制位图还包含值的栅格。每一行由图像宽度指定的位数定义。但是，这些行以字节为单位打包！这意味着每一行可以包含一些必须忽略的额外位。根据规范，我们可以简单地忽略这些多余的位。为了实现这一点，我们可以定义一个递归操作，通过递归读取所需数量的位并忽略其余位来单独解析每一行。然后我们可以将这些行连接成一个大型的 RawPixel 值列表。此实现如清单 8.29 所示。

p4DataP :: Int -> Int -> Parser [RawPixel] p4DataP width height = do rows <- count height (reverse <$> readRow width []) #1 return $ concat rows where readRow n pxs | n <= 0 = return pxs #2 | otherwise = do (b7, b6, b5, b4, b3, b2, b1, b0) <- p4PixelP #3 case n of 1 -> return $ b7 : pxs #4 2 -> return $ b6 : b7 : pxs #4 3 -> return $ b5 : b6 : b7 : pxs #4 4 -> return $ b4 : b5 : b6 : b7 : pxs #4 5 -> return $ b3 : b4 : b5 : b6 : b7 : pxs #4 6 -> return $ b2 : b3 : b4 : b5 : b6 : b7 : pxs #4 7 -> return $ b1 : b2 : b3 : b4 : b5 : b6 : b7 : pxs #4 8 -> return $ b0 : b1 : b2 : b3 : b4 : b5 : b6 : b7 : pxs #4 _ -> readRow #5 (n - 8) (b0 : b1 : b2 : b3 : b4 : b5 : b6 : b7 : pxs)

在这里，我们在考虑位的顺序时必须小心。我们将位从最高有效位到最低有效位解析，但我们以相反的顺序将它们添加到每行的结果列表中。然后将这些列表颠倒过来。我们跟踪需要在 readRow 中读取多少元素，以便一旦我们需要的元素少于 9 个，我们就可以为结果提供适量的值。

我们以相反的顺序添加值的原因是为了性能。否则，我们不能使用 （:)构造函数，但需要使用追加函数 （ ）。追加函数非常昂贵，因为它需要在添加新元素之前遍历整个列表。对于大型列表，快速递归执行此操作变得不可行。以相反的顺序添加元素，然后反转整个结果更便宜。

读取所有行后，我们可以连接所有值以接收 [RawPixel] 的完整数据。

通过对所有格式的解析，我们可以将所有部分放在一起！

使用 headerP 和 dataP，我们为图像文件的标头和正文构建了解析器。现在我们把它们放在一起，为通用PNM文件构建一个解析器。如清单 8.30 所示。

pnmP :: Parser PNM pnmP = do header <- headerP #1 imageData <- dataP header #2 option () whitespaces #3 return PNM {..} parsePNM :: BS.ByteString -> Either String PNM parsePNM = parseOnly (pnmP <* endOfInput) #4

读取标头和数据后，我们还会跳过文件中可能仍然存在的任何空格。我们这样做是为了确定我们已经到达文件末尾。在parsePNM中，如果我们没有读取完整的输入，我们积极地强制要求解析必须失败，我们通过使用endOfInput来做到这一点。如果 pnmP 的应用没有导致解析器在文件末尾停止，则输入将失败。

我们在本章中展示的解析器只能从文件中读取单个PNM图像。但是，该规范允许在单个文件中存在多个图像。你能修改我们的解析函数以允许这样做吗？

如果您想试用我们新构建的解析器，本书的存储库提供了不同大小和格式的示例图像。

我们已经为PNM文件格式构建了一个解析器，并且能够从文件中读取图像数据。在下一章中，我们将讨论使用并行性处理这些数据以加快执行速度。

• 函子用于以引用透明的方式修改由效果评估产生的值
• 应用程序可用于编写有效的操作，例如处理输入或分析文件中的内容
• 替代使应用程序可以在成功和失败操作之间进行选择，例如，使解析器可以从递归结构解析的深处返回错误消息
• Monads 可用于编写有效的操作，同时使先前操作的结果影响新结果，有效地链接操作，同时仍保持一致的错误处理
• MonadFail用于为monadic类型提供失败的可能性，这用于使monad显式进入失败状态
• MonadPlus是替代的monadic对应物，使monad能够在成功和失败的行动之间进行选择
• 当我们需要在低级别操作数字和字节串时，可以使用 Data.Bits 中的函数实现位级操作