另一个 Haskell 教程/单子
| Haskell | |
|---|---|
| |
| 另一个 Haskell 教程 | |
| 前言 | |
| 简介 | |
| 入门 | |
| 语言基础 (解决方案) | |
| 类型基础 (解决方案) | |
| IO (解决方案) | |
| 模块 (解决方案) | |
| 高级语言 (解决方案) | |
| 高级类型 (解决方案) | |
| 单子 (解决方案) | |
| 高级 IO | |
| 递归 | |
| 复杂性 | |
学习 Haskell 时最难掌握的概念是理解和使用单子。我们可以在这里区分两个子组件：(1) 学习如何使用现有的单子，以及 (2) 学习如何编写新的单子。如果你想使用 Haskell，你必须学习如何使用现有的单子。另一方面，只有当你想要成为“超级 Haskell 大师”时，你才需要学习如何编写自己的单子。但是，如果你能掌握编写自己的单子的方法，那么用 Haskell 编程会更加愉快。
到目前为止，我们已经看到了单子的两种用途。第一个用途是 IO 操作：我们已经看到，通过使用单子，我们可以摆脱在 IO 章节中介绍的 RealWorld 解决方案所带来的问题。第二个用途是在关于 类-计算 的部分中表示不同类型的计算。在这两种情况下，我们都需要一种对操作进行排序的方法，并且发现一个足够好的定义（至少对于计算而言）是
class Computation c where
success :: a -> c a
failure :: String -> c a
augment :: c a -> (a -> c b) -> c b
combine :: c a -> c a -> c a
让我们看看这个定义是否能够让我们执行 IO。本质上，我们需要一种方法来表示从操作中获取一个值，并在其上执行一些新的操作（就像 函数-io 部分中的示例一样，稍微改写一下）
main = do s <- readFile "somefile" putStrLn (show (f s))
但这就是 augment 所做的。使用 augment，我们可以将上面的代码写成
main = -- note the lack of a "do" readFile "somefile" `augment` \s -> putStrLn (show (f s))
这似乎已经足够了。实际上，它比足够还要多。
单子的定义是我们 Computation 类的略微简化版本。Monad 类有四个方法（但第四个方法可以用第三个方法来定义）
class Monad m where
return :: a -> m a
fail :: String -> m a
(>>=) :: m a -> (a -> m b) -> m b
(>>) :: m a -> m b -> m b
在这个定义中，return 等效于我们的 success；fail 等效于我们的 failure；>>=（读作：“绑定”）等效于我们的 augment。>>（读作：“然后”）方法只是一个忽略 a 的 >>= 版本。这将会非常有用；虽然，正如之前提到的，它可以用 >>= 来定义
a >> x = a >>= \_ -> x
Do 符号
[edit | edit source]我们已经暗示了单子与 do 符号之间存在联系。在这里，我们使这种关系具体化。实际上，do 符号并没有什么神奇之处，它仅仅是单子操作的“语法糖”。
正如我们之前提到的，使用我们的 Computation 类，我们可以将上面的程序定义为
main =
readFile "somefile" `augment` \s ->
putStrLn (show (f s))
但我们现在知道，augment 在单子世界中被称为 >>=。因此，这个程序实际上读作
main =
readFile "somefile" >>= \s ->
putStrLn (show (f s))
而这在此时已经是完全有效的 Haskell 代码：如果你定义了一个函数 f :: Show a => String -> a，你就可以编译并运行这个程序）
这表明我们可以将
x <- f g x
翻译成 f >>= \x -> g x。这正是编译器所做的。如果我们不使用隐式布局，那么谈论 do 会更容易（请参见 布局 部分了解如何执行此操作）。有四个转换规则
do {e}→edo {e; es}→e >> do {es}do {let decls; es}→let decls in do {es}do {p <- e; es}→let ok p = do {es} ; ok _ = fail "..." in e >>= ok
同样，我们将逐一详细说明这些规则
转换规则 1
[edit | edit source]第一个转换规则 do {e} → e 指出（正如我们之前所说），在执行单个操作时，是否使用 do 都是无关紧要的。这本质上是 do 的归纳定义的基例。基例有一个操作（即这里的 e）；另外三个转换规则处理有多个操作的情况。
转换规则 2
[edit | edit source]这表明 do {e; es} → e >> do {es}。这告诉我们，如果我们有一个操作（e）后跟一个操作列表（es），该怎么做。在这里，我们使用了之前定义的 >> 函数。这条规则简单地说，要 do {e; es}，我们首先执行操作 e，丢弃结果，然后 do es。
例如，如果 e 是对于某个字符串 s 的 putStrLn s，那么 do {e; es} 的转换就是执行 e（即打印字符串），然后 do es。这显然是我们想要的。
转换规则 3
[edit | edit source]这表明 do {let decls; es} → let decls in do {es}。这条规则告诉我们如何处理 do 语句中的 let。我们将 let 内的声明提升出来，并 do 声明后的所有内容。
转换规则 4
[edit | edit source]这表明 do {p <- e; es} → let ok p = do {es} ; ok _ = fail "..." in e >>= ok。同样，这里也不太清楚究竟发生了什么。但是，这条规则的另一种表述，它与之大致等价，是：do {p <- e; es} → e >>= \p -> es。在这里，很清楚发生了什么。我们运行操作 e，然后将结果发送到 es，但首先将结果命名为 p。
定义如此复杂的原因是，p 不必仅仅是一个变量；它可以是某个复杂的模式。例如，以下代码是有效的
foo = do ('a':'b':'c':x:xs) <- getLine
putStrLn (x:xs)
在这里，我们假设操作`getLine`的结果将以字符串“abc”开头，并将至少包含一个额外的字符。问题变成了如果这个模式匹配失败会发生什么。编译器可以像往常一样简单地抛出一个错误，用于模式匹配失败。但是，由于我们在一个单子中，我们可以访问一个特殊的`fail`函数，并且我们更希望使用该函数来失败，而不是使用“catch all”`error`函数。因此，如定义的翻译允许编译器用关于模式匹配失败的适当错误消息填充`...`。除此之外，这两个定义是等效的。
所有单子都必须遵守三个规则，称为“单子定律”（确保你的单子遵守这些规则是你自己的责任）
return a >>= f≡f af >>= return≡ff >>= (\x -> g x >>= h)≡(f >>= g) >>= h
让我们逐个看一下这些定律
这表明 return a >>= f ≡ f a。假设我们把单子看作计算。这意味着如果我们创建一个简单的计算，它简单地返回值 `a`，而不考虑其他任何因素（这是 `return a` 部分）；然后将其与其他计算 `f` 绑定在一起，那么这等同于直接在 `a` 上执行计算 `f`。
例如，假设 `f` 是函数 `putStrLn`，而 `a` 是字符串“Hello World”。这条定律表明，将结果为“Hello World”的计算绑定到 `putStrLn` 与简单地将其打印到屏幕上是相同的。这似乎是合理的。
在 `do` 表示法中，这条定律表明以下两个程序是等效的
law1a = do x <- return a f x law1b = do f a
第二个单子定律表明，对于某些计算 `f`，`f >>= return` ≡ `f`。换句话说，这条定律表明，如果我们执行计算 `f`，然后将结果传递给简单的 `return` 函数，那么我们所做的只是执行了计算。
这条定律必须成立，这应该是显而易见的。为了理解这一点，将 `f` 看作 `getLine`（从键盘读取字符串）。这条定律表明，读取一个字符串，然后返回读取的值，与仅仅读取字符串完全相同。
在 `do` 表示法中，这条定律表明以下两个程序是等效的
law2a = do x <- f return x law2b = do f
这表明 f >>= (\x -> g x >>= h) ≡ (f >>= g) >>= h。乍一看，这条定律不如其他两个定律容易理解。它本质上是单子的结合律。
注意
在单子的世界之外，如果 是结合的，则 。例如，`+` 和 `*` 是结合的，因为对这些函数进行括号操作不会产生影响。另一方面，`-` 和 `/` 不是结合的，因为例如 。
如果我们丢弃带有 lambda 的混乱，我们会发现这条定律表明：`f >>= (g >>= h)` ≡ `(f >>= g) >>= h`。这条定律背后的直觉是，当我们串联操作时，操作分组的方式无关紧要。
为了得到一个具体的例子，将 `f` 看作 `getLine`。将 `g` 看作一个操作，它以一个值作为输入，将其打印到屏幕上，通过 `getLine` 读取另一个字符串，然后返回这个新读取的字符串。将 `h` 看作 `putStrLn`。
让我们考虑一下 `(\x -> g x >>= h)` 的作用。它接受一个名为 `x` 的值，并在其上运行 `g`，将结果馈送到 `h`。在这种情况下，这意味着它将接受一个值，打印它，读取另一个值，然后打印该值。因此，定律的整个左侧首先读取一个字符串，然后执行我们刚刚描述的操作。
另一方面，考虑 `(f >>= g)`。这个操作从键盘读取一个字符串，打印它，然后读取另一个字符串，并将这个新读取的字符串作为结果返回。当我们将它与定律右侧的 `h` 绑定时，我们得到一个操作，它执行由 `(f >>= g)` 描述的操作，然后打印结果。
显然，这两个操作是相同的。
虽然这个解释相当复杂，并且定律的文本也相当复杂，但实际含义很简单：如果我们有三个操作，并且我们按相同的顺序将它们组合在一起，那么我们放置括号的位置无关紧要。剩下的只是符号。
在 `do` 表示法中，这条定律表明以下两个程序是等效的
law3a = do
x <- f
do y <- g x
h y
law3b = do
y <- do x <- f
g x
h y
我们可以创建的最简单的单子之一是状态传递单子。在 Haskell 中，所有状态信息通常必须作为参数显式传递给函数。使用单子，我们可以有效地隐藏一些状态信息。
假设我们有一个类型为 `a -> b` 的函数 `f`，我们需要向这个函数添加状态。一般来说，如果状态的类型为 `state`，我们可以通过将 `f` 的类型更改为 `a -> state -> (state, b)` 来对它进行编码。也就是说，新版本的 `f` 接受原始类型为 `a` 的参数和一个新的状态参数。此外，除了返回类型为 `b` 的值之外，它还会返回一个更新的状态，编码在一个元组中。
例如，假设我们有一个二叉树，定义如下
data Tree a = Leaf a | Branch (Tree a) (Tree a)
现在，我们可以编写一个简单的映射函数，将某个函数应用于每个叶子的值
mapTree :: (a -> b) -> Tree a -> Tree b
mapTree f (Leaf a) = Leaf (f a)
mapTree f (Branch lhs rhs) =
Branch (mapTree f lhs) (mapTree f rhs)
这很好用，直到我们需要编写一个函数，将叶子从左到右编号。从某种意义上说，我们需要将状态添加到 `mapTree` 函数中，该状态跟踪我们到目前为止已经编号了多少个叶子。我们可以将该函数增强为类似于以下内容
mapTreeState :: (a -> state -> (state, b)) ->
Tree a -> state -> (state, Tree b)
mapTreeState f (Leaf a) state =
let (state', b) = f a state
in (state', Leaf b)
mapTreeState f (Branch lhs rhs) state =
let (state' , lhs') = mapTreeState f lhs state
(state'', rhs') = mapTreeState f rhs state'
in (state'', Branch lhs' rhs')
这开始变得有点笨拙，类型签名也越来越难理解。我们想要做的是抽象出状态传递部分。也就是说，`mapTree` 和 `mapTreeState` 之间的区别是：(1) 增强的 `f` 类型，(2) 我们将类型 `-> Tree b` 替换为 `-> state -> (state, Tree b)`。请注意，这两种类型都以完全相同的方式发生了变化。我们可以通过类型别名声明抽象出这一点
type State st a = st -> (st, a)
为了配合这种类型，我们编写了两个函数
returnState :: a -> State st a
returnState a = \st -> (st, a)
bindState :: State st a -> (a -> State st b) ->
State st b
bindState m k = \st ->
let (st', a) = m st
m' = k a
in m' st'
让我们依次检查一下这些函数。第一个函数 `returnState` 接受类型为 `a` 的值，并创建一个类型为 `State st a` 的东西。如果我们把 `st` 看作状态，把类型为 `a` 的值看作值，那么这是一个不改变状态并返回值 `a` 的函数。
`bindState` 函数看起来很像 `mapTreeState` 中的内部 `let` 声明。它接受两个参数。第一个参数是一个操作，它返回类型为 `a` 的东西，状态为 `st`。第二个参数是一个函数，它接受这个 `a` 并生成一个类型为 `b` 的东西，同样也具有相同的状态。`bindState` 的结果本质上是将 `a` 转换为 `b` 的结果。
`bindState` 的定义接受一个初始状态 `st`。它首先将这个状态应用于称为 `m` 的 `State st a` 参数。这会返回一个新的状态 `st'` 和一个值 `a`。然后，它让函数 `k` 作用于 `a`，生成一个类型为 `State st b` 的东西，称为 `m'`。最后，我们使用新的状态 `st'` 运行 `m'`。
我们编写了一个新函数 `mapTreeStateM`，并给它赋予以下类型
mapTreeStateM :: (a -> State st b) -> Tree a -> State st (Tree b)
使用这些“管道”函数（`returnState` 和 `bindState`），我们可以编写这个函数，而无需显式地讨论状态
mapTreeStateM f (Leaf a) = f a `bindState` \b -> returnState (Leaf b) mapTreeStateM f (Branch lhs rhs) = mapTreeStateM f lhs `bindState` \lhs' -> mapTreeStateM f rhs `bindState` \rhs' -> returnState (Branch lhs' rhs')
在 `Leaf` 的情况下，我们将 `f` 应用于 `a`，然后将结果绑定到一个函数，该函数接受结果并返回一个具有新值的 `Leaf`。
在 `Branch` 的情况下，我们递归地处理左侧，将结果绑定到一个函数，该函数递归地处理右侧，并将该结果绑定到一个简单的函数，该函数返回新创建的 `Branch`。
正如您可能已经猜到的，State st 是一个单子，returnState 类似于重载的 return 方法，而 bindState 类似于重载的 >>= 方法。事实上，我们可以验证 State st a 符合单子定律。
定律 1 声明：return a >>= f ≡ f a。让我们计算左侧，代入我们的名称。
returnState a `bindState` f
==>
\st -> let (st', a) = (returnState a) st
m' = f a
in m' st'
==>
\st -> let (st', a) = (\st -> (st, a)) st
in (f a) st'
==>
\st -> let (st', a) = (st, a)
in (f a) st'
==>
\st -> (f a) st
==>
f a
在第一步中，我们只是代入 bindState 的定义。在第二步中，我们简化最后两行并代入 returnState 的定义。在第三步中，我们将 st 应用于 lambda 函数。在第四步中，我们将 st' 重命名为 st 并删除 let。在最后一步中，我们进行 eta 归约。
继续 定律 2，我们需要证明 f >>= return ≡ f。如下所示。
f `bindState` returnState
==>
\st -> let (st', a) = f st
in (returnState a) st'
==>
\st -> let (st', a) = f st
in (\st -> (st, a)) st'
==>
\st -> let (st', a) = f st
in (st', a)
==>
\st -> f st
==>
f
最后，我们需要证明 State 符合第三定律：f >>= (\x -> g x >>= h) ≡ (f >>= g) >>= h。这更复杂一些，所以我们只在这里概述一下证明。请注意，我们可以将左侧写为
\st -> let (st', a) = f st
in (\x -> g x `bindState` h) a st'
==>
\st -> let (st', a) = f st
in (g a `bindState` h) st'
==>
\st -> let (st', a) = f st
in (\st' -> let (st'', b) = g a
in h b st'') st'
==>
\st -> let (st' , a) = f st
(st'', b) = g a st'
(st''',c) = h b st''
in (st''',c)
这里值得注意的是，我们对同一个 let 级别的两个动作应用都进行了操作。由于 let 是结合的，这意味着我们可以根据需要进行括号运算，结果不会改变。当然，这是一个非正式的、“挥手式”的论证，我们需要进行更多推导才能真正证明，但这提供了一般思路。
现在我们知道 State st 实际上是一个单子，我们希望将其设为 Monad 类的一个实例。不幸的是，直接这样做行不通。我们无法编写
instance Monad (State st) where { ... }
这是因为您无法根据未完全应用的类型同义词创建实例。相反，我们需要做的是将类型同义词转换为 newtype，如下所示
newtype State st a = State (st -> (st, a))
不幸的是，这意味着我们需要在 Monad 实例声明中对 State 构造函数进行一些打包和解包，但这并不难。
instance Monad (State state) where
return a = State (\state -> (state, a))
State run >>= action = State run'
where run' st =
let (st', a) = run st
State run'' = action a
in run'' st'
现在，我们可以编写我们的 mapTreeM 函数，如下所示
mapTreeM :: (a -> State state b) -> Tree a ->
State state (Tree b)
mapTreeM f (Leaf a) = do
b <- f a
return (Leaf b)
mapTreeM f (Branch lhs rhs) = do
lhs' <- mapTreeM f lhs
rhs' <- mapTreeM f rhs
return (Branch lhs' rhs')
这比以前干净得多。事实上，如果我们删除类型签名，我们会得到更通用的类型
mapTreeM :: Monad m => (a -> m b) -> Tree a ->
m (Tree b)
也就是说，mapTreeM 可以运行在 任何 单子中，而不仅仅是我们的 State 单子。
现在，将状态方面封装成计算的好处是，我们可以提供获取和更改当前状态的函数。它们看起来像
getState :: State state state getState = State (\state -> (state, state)) putState :: state -> State state () putState new = State (\_ -> (new, ()))
这里，getState 是一个单子操作，它获取当前状态，保持不变地传递它，然后将其作为值返回。putState 函数获取一个新状态，并生成一个忽略当前状态并插入新状态的操作。
现在，我们可以编写我们的 numberTree 函数，如下所示
numberTree :: Tree a -> State Int (Tree (a, Int))
numberTree tree = mapTreeM number tree
where number v = do
cur <- getState
putState (cur+1)
return (v,cur)
最后，我们需要能够通过提供初始状态来运行操作。
runStateM :: State state a -> state -> a runStateM (State f) st = snd (f st)
现在，我们可以提供一个示例树
testTree =
Branch
(Branch
(Leaf 'a')
(Branch
(Leaf 'b')
(Leaf 'c')))
(Branch
(Leaf 'd')
(Leaf 'e'))
并对其进行编号
示例
State> runStateM (numberTree testTree) 1
Branch (Branch (Leaf ('a',1)) (Branch (Leaf ('b',2))
(Leaf ('c',3)))) (Branch (Leaf ('d',4))
(Leaf ('e',5)))
这似乎是为一个简单的事情做了大量的工作。但是，请注意 mapTreeM 的新能力。我们还可以从左到右打印树的叶子，如下所示
示例
State> mapTreeM print testTree 'a' 'b' 'c' 'd' 'e'
这完全依赖于 mapTreeM 拥有更通用的类型，它涉及任意单子——而不仅仅是状态单子。此外，我们可以编写一个操作，它将每个叶子的值设置为它的旧值以及所有之前的值
fluffLeaves tree = mapTreeM fluff tree
where fluff v = do
cur <- getState
putState (v:cur)
return (v:cur)
并可以查看它的实际操作
示例
State> runStateM (fluffLeaves testTree) []
Branch (Branch (Leaf "a") (Branch (Leaf "ba")
(Leaf "cba"))) (Branch (Leaf "dcba")
(Leaf "edcba"))
事实上，您甚至不需要编写自己的单子实例和数据类型。所有这些都在 Control.Monad.State 模块中内置。在那里，我们的 runStateM 被称为 evalState；我们的 getState 被称为 get；我们的 putState 被称为 put。
此模块还包含一个 状态转换器单子，我们将在关于 转换器 的部分中讨论它。
常用单子
[edit | edit source]事实证明，我们很多喜欢的类型实际上本身就是单子。例如，考虑列表。它们有一个单子定义，看起来类似于
instance Monad [] where
return x = [x]
l >>= f = concatMap f l
fail _ = []
这使我们能够在 do 符号中使用列表。例如，给定定义
cross l1 l2 = do x <- l1 y <- l2 return (x,y)
我们得到一个交叉乘积函数
示例
Monads> cross "ab" "def"
[('a','d'),('a','e'),('a','f'),('b','d'),('b','e'),
('b','f')]
这与列表推导形式非常相似，这并非巧合
示例
Prelude> [(x,y) | x <- "ab", y <- "def"]
[('a','d'),('a','e'),('a','f'),('b','d'),('b','e'),
('b','f')]
列表推导形式只是使用列表的单子语句的简写形式。事实上，在旧版本的 Haskell 中，列表推导形式可以用于 任何 单子——而不仅仅是列表。但是，在当前版本的 Haskell 中，这不再允许。
Maybe 类型也是一个单子，失败表示为 Nothing，成功表示为 Just。我们得到以下实例声明
instance Monad Maybe where
return a = Just a
Nothing >>= f = Nothing
Just x >>= f = f x
fail _ = Nothing
我们可以对 Maybe 使用与列表相同的 交叉乘积 函数。这是因为 do 符号适用于任何单子，并且 cross 函数中没有与列表相关的任何内容。
示例
Monads> cross (Just 'a') (Just 'b')
Just ('a','b')
Monads> cross (Nothing :: Maybe Char) (Just 'b')
Nothing
Monads> cross (Just 'a') (Nothing :: Maybe Char)
Nothing
Monads> cross (Nothing :: Maybe Char)
(Nothing :: Maybe Char)
Nothing
这意味着如果我们只使用单子运算符编写一个函数（例如，来自关于 类 部分的 searchAll），我们就可以使用任何单子，具体取决于我们的意思。使用真正的单子函数（不是 do 符号），searchAll 函数看起来像
searchAll g@(Graph vl el) src dst
| src == dst = return [src]
| otherwise = search' el
where search' [] = fail "no path"
search' ((u,v,_):es)
| src == u =
searchAll g v dst >>= \path ->
return (u:path)
| otherwise = search' es
此函数的类型为 Monad m => Graph v e -> Int -> Int -> m [Int]。这意味着无论我们当前使用的是哪个单子，此函数都将执行计算。假设我们有以下图
gr = Graph [(0, 'a'), (1, 'b'), (2, 'c'), (3, 'd')]
[(0,1,'l'), (0,2,'m'), (1,3,'n'), (2,3,'m')]
它表示一个具有四个节点的图，分别标记为 a,b,c 和 d。从 a 到 b 和 c 都有边。从 b 和 c 到 d 也都有边。使用 Maybe 单子，我们可以计算从 a 到 d 的路径
示例
Monads> searchAll gr 0 3 :: Maybe [Int] Just [0,1,3]
我们提供了类型签名，以便解释器知道我们使用的是哪个单子。如果我们尝试在相反方向搜索，则没有路径。无法找到路径在 Maybe 单子中表示为 Nothing
示例
Monads> searchAll gr 3 0 :: Maybe [Int] Nothing
请注意，字符串“no path”已经消失，因为 Maybe 单子没有办法记录它。
如果我们在列表单子中执行相同的不可能搜索，我们会得到空列表，表示没有路径
示例
Monads> searchAll gr 3 0 :: [[Int]] []
如果我们执行可能的搜索，我们会得到包含第一条路径的列表
示例
Monads> searchAll gr 0 3 :: [[Int]] [[0,1,3]]
您可能期望此函数调用返回 所有 路径，但按照代码所示，它不会。有关使用列表表示不确定性的更多信息，请参阅关于 Plus 的部分。
如果我们使用 IO 单子，我们实际上可以访问错误消息，因为 IO 知道如何跟踪错误消息
示例
Monads> searchAll gr 0 3 :: IO [Int] Monads> it [0,1,3] Monads> searchAll gr 3 0 :: IO [Int] *** Exception: user error Reason: no path
在第一种情况下，我们需要键入 it 以使 GHCi 实际评估搜索。
此 searchAll 实现有一个问题：如果它找到一条没有通向解决方案的边，它将无法回溯。这与 search' 中对 searchAll 的递归调用有关。例如，考虑如果 searchAll g v dst 找不到路径会发生什么。此实现无法恢复。例如，如果我们删除从节点 b 到节点 d 的边，我们仍然应该能够找到从 a 到 d 的路径，但此算法无法找到它。我们定义
gr2 = Graph [(0, 'a'), (1, 'b'), (2, 'c'), (3, 'd')]
[(0,1,'l'), (0,2,'m'), (2,3,'m')]
然后尝试搜索
示例
Monads> searchAll gr2 0 3 *** Exception: user error Reason: no path
为了解决这个问题，我们需要一个类似于我们的 Computation 类中的 combine 函数的函数。我们将在关于 Plus 的部分中看到如何做到这一点。
| 练习 |
|---|
验证 Maybe 是否符合三个单子定律。 |
| 练习 |
|---|
|
类型 instance Monad (Either String) where。 |
单子组合器
[edit | edit source]Monad/Control.Monad 库包含一些非常有用的单子组合器，这些组合器尚未得到深入讨论。我们将在本节中讨论的组合器及其类型如下所示
(=<<) :: (a -> m b) -> m a -> m bmapM :: (a -> m b) -> [a] -> m [b]mapM_ :: (a -> m b) -> [a] -> m ()filterM :: (a -> m Bool) -> [a] -> m [a]foldM :: (a -> b -> m a) -> a -> [b] -> m asequence :: [m a] -> m [a]sequence_ :: [m a] -> m ()liftM :: (a -> b) -> m a -> m bwhen :: Bool -> m () -> m ()join :: m (m a) -> m a
在以上内容中，m 始终被假定为是 Monad 的一个实例。
通常，以下划线结尾的函数与没有下划线的函数等效，只是它们不返回值。
=<< 函数与 >>= 完全相同，只是它以相反的顺序接收参数。例如，在 IO 单子中，我们可以编写以下两种方法之一
示例
Monads> writeFile "foo" "hello world!" >>
(readFile "foo" >>= putStrLn)
hello world!
Monads> writeFile "foo" "hello world!" >>
(putStrLn =<< readFile "foo")
hello world!
mapM、filterM 和 foldM 是我们旧的朋友 map、filter 和 foldl 封装在单子内部。这些函数（尤其是 foldM）在使用单子时非常有用。例如，我们可以使用 mapM_ 在屏幕上打印一个列表
示例
Monads> mapM_ print [1,2,3,4,5] 1 2 3 4 5
我们可以使用 foldM 对一个列表求和，并在每个步骤打印中间和
示例
Monads> foldM (\a b ->
putStrLn (show a ++ "+" ++ show b ++
"=" ++ show (a+b)) >>
return (a+b)) 0 [1..5]
0+1=1
1+2=3
3+3=6
6+4=10
10+5=15
Monads> it
15
sequence 和 sequence_ 函数只是“执行”一个操作列表。例如
示例
Monads> sequence [print 1, print 2, print 'a'] 1 2 'a' Monads> it [(),(),()] Monads> sequence_ [print 1, print 2, print 'a'] 1 2 'a' Monads> it ()
我们可以看到，带下划线的版本不返回每个值，而没有下划线的版本返回返回值的列表。
liftM 函数将一个非单子函数“提升”为一个单子函数。（不要将其与在关于 转换器 的部分中用于单子转换器的 lift 函数混淆。）这对于缩短代码（除其他事项外）非常有用。例如，我们可能想要编写一个函数，该函数将文件中的每一行都加上其行号。我们可以使用以下方法做到这一点
numberFile :: FilePath -> IO () numberFile fp = do text <- readFile fp let l = lines text let n = zipWith (\n t -> show n ++ ' ' : t) [1..] l mapM_ putStrLn n
但是，我们可以使用 liftM 缩短此代码
numberFile :: FilePath -> IO () numberFile fp = do l <- lines `liftM` readFile fp let n = zipWith (\n t -> show n ++ ' ' : t) [1..] l mapM_ putStrLn n
事实上，您可以使用 liftM 对文件进行任何形式的（纯）处理。例如，也许我们还想要将行拆分为单词；我们可以使用以下方法做到这一点
... w <- (map words . lines) `liftM` readFile fp ...
请注意，括号是必需的，因为 (.) 函数具有与 `liftM` 相同的固定性。
将纯函数提升到单子中在其他单子中也很有用。例如，liftM 可以用来在 Just 内部应用函数。例如
Monads> liftM (+1) (Just 5) Just 6 Monads> liftM (+1) Nothing Nothing
when 函数仅在满足条件时执行单子操作。因此，如果我们只想打印非空行
示例
Monads> mapM_ (\l -> when (not $ null l) (putStrLn l))
["","abc","def","","","ghi"]
abc
def
ghi
当然，也可以使用 filter 来完成同样的操作，但有时 when 更方便。
最后，join 函数是列表上 concat 的单子等价物。实际上，当 m 是列表单子时，join 正好是 concat。在其他单子中，它完成类似的任务。
示例
Monads> join (Just (Just 'a')) Just 'a' Monads> join (Just (Nothing :: Maybe Char)) Nothing Monads> join (Nothing :: Maybe (Maybe Char)) Nothing Monads> join (return (putStrLn "hello")) hello Monads> return (putStrLn "hello") Monads> join [[1,2,3],[4,5]] [1,2,3,4,5]
当我们进入本章更高级的主题时，这些函数将变得更加有用，Io 高级。
MonadPlus
[edit | edit source]仅给出 >>= 和 return 函数，就无法编写类型为 c a -> c a -> c a 的函数，例如 combine。但是，这样一个函数非常普遍有用，它存在于另一个名为 MonadPlus 的类中。除了具有 combine 函数外，MonadPlus 的实例还具有“零”元素，它是“加”（即组合）操作下的标识。定义是
class Monad m => MonadPlus m where mzero :: m a mplus :: m a -> m a -> m a
为了获得对 MonadPlus 的访问权限，你需要导入 Monad 模块（或者在层次结构库中导入 Control.Monad）。
在关于 Common 的部分中，我们展示了 Maybe 和列表都是单子。事实上，它们也都是 MonadPlus 的实例。在 Maybe 的情况下，零元素是 Nothing；在列表的情况下，它是空列表。Maybe 上的 mplus 操作是 Nothing，如果两个元素都是 Nothing；否则，它是第一个 Just 值。对于列表，mplus 与 ++ 相同。
也就是说，实例声明看起来像
instance MonadPlus Maybe where mzero = Nothing mplus Nothing y = y mplus x _ = x instance MonadPlus [] where mzero = [] mplus x y = x ++ y
我们可以使用此类重新实现我们一直在探索的搜索函数，这样它将探索所有可能的路径。新函数如下所示
searchAll2 g@(Graph vl el) src dst
| src == dst = return [src]
| otherwise = search' el
where search' [] = fail "no path"
search' ((u,v,_):es)
| src == u =
(searchAll2 g v dst >>= \path ->
return (u:path)) `mplus`
search' es
| otherwise = search' es
现在，当我们在 search' 中遍历边列表时，如果我们遇到匹配的边，我们不仅会探索这条路径，而且还会在对 search' 的递归调用中继续探索当前节点的出边。
IO 单子不是 MonadPlus 的实例；我们无法使用此单子执行搜索。我们可以看到，当使用列表作为单子时，我们 (a) 在 gr 中获得所有可能的路径，以及 (b) 在 gr2 中获得一条路径。
示例
MPlus> searchAll2 gr 0 3 :: [[Int]] [[0,1,3],[0,2,3]] MPlus> searchAll2 gr2 0 3 :: [[Int]] [[0,2,3]]
你可能很想这样实现
searchAll2 g@(Graph vl el) src dst
| src == dst = return [src]
| otherwise = search' el
where search' [] = fail "no path"
search' ((u,v,_):es)
| src == u = do
path <- searchAll2 g v dst
rest <- search' es
return ((u:path) `mplus` rest)
| otherwise = search' es
但请注意，这并不能做到我们想要的效果。在这里，如果对 searchAll2 的递归调用失败，我们不会尝试继续执行 search' es。对 mplus 的调用必须在顶层才能生效。
| 练习 |
|---|
|
假设我们将 search' es `mplus`
(searchAll2 g v dst >>= \path ->
return (u:path))
当你使用列表时，你会期望这如何改变结果 在gr 上的单子？为什么？ |
单子转换器
[edit | edit source]通常我们想将单子“叠加”在彼此之上。例如，可能存在一个情况，你需要通过 IO 单子访问 IO 操作，并通过某些状态单子访问状态函数。为了实现这一点，我们引入一个 MonadTrans 类，它本质上将一个单子的操作“提升”到另一个单子。你可以将其视为将单子堆叠在彼此之上。此类具有一个简单的方法：lift。MonadTrans 的类声明为
class MonadTrans t where lift :: Monad m => m a -> t m a
这里的想法是 t 是外部单子，m 存在于它内部。为了执行类型为 Monad m => m a 的命令，我们首先将其提升到转换器中。
转换器最简单的示例（也可能是最有用的）是状态转换器单子，它是在任意单子周围包装的状态单子。之前，我们定义状态单子为
newtype State state a = State (state -> (state, a))
现在，我们不再使用类型为 state -> (state, a) 的函数作为单子，而是假设存在其他一些单子 m，并将内部操作设置为类型为 state -> m (state, a) 的东西。这导致了以下状态转换器的定义
newtype StateT state m a =
StateT (state -> m (state, a))
例如，我们可以将 m 视为 IO。在这种情况下，我们的状态转换器单子能够在 IO 单子中执行操作。首先，我们将它设为 MonadTrans 的实例
instance MonadTrans (StateT state) where
lift m = StateT (\s -> do a <- m
return (s,a))
在这里，将 m 域中的函数提升到 StateT state 域中，只需保持状态（s 值）不变并执行操作即可。
当然，我们还需要使 StateT 本身成为单子。这是相对简单的，前提是 m 已经是单子
instance Monad m => Monad (StateT state m) where
return a = StateT (\s -> return (s,a))
StateT m >>= k = StateT (\s -> do
(s', a) <- m s
let StateT m' = k a
m' s')
fail s = StateT (\_ -> fail s)
return 定义背后的想法是我们保持状态不变，只需在封闭的单子中返回状态/a 对。请注意，return 定义中对 return 的使用是指封闭的单子，而不是状态转换器。
在绑定定义中，我们创建一个新的 StateT，它以状态 s 作为参数。首先，它将此状态应用于第一个操作 (StateT m)，并获得新的状态和答案作为结果。然后，它在这个新状态上运行 k 操作，并获得一个新的转换器。最后，它将新状态应用于此转换器。此定义几乎与我们在关于 State 的部分中描述的标准（非转换器）State 单子的绑定定义相同。
fail 函数将调用传递给封闭单子中的 fail，因为状态转换器本身不知道如何处理失败。
当然，为了实际使用此单子，我们需要提供函数 getT、putT 和 evalStateT。这些类似于我们在关于 State 的部分中提到的 getState、putState 和 runStateM
getT :: Monad m => StateT s m s getT = StateT (\s -> return (s, s)) putT :: Monad m => s -> StateT s m () putT s = StateT (\_ -> return (s, ())) evalStateT :: Monad m => StateT s m a -> s -> m a evalStateT (StateT m) state = do (s', a) <- m state return a
这些函数应该很直观。但是请注意，evalStateT 的结果实际上是封闭单子中的单子操作。这是单子转换器的典型特征：它们不知道如何在封闭的单子中实际运行东西（它们只知道如何提升操作）。因此，你得到的是内部单子（在我们的例子中是 IO）中的单子操作，你需要自己运行它。
我们可以使用状态转换器重新实现我们从关于 State 的部分中提到的 mapTreeM 函数版本。这里唯一的变化是，当我们到达叶子时，我们打印出叶子的值；当我们到达分支时，我们只打印出“分支”。
mapTreeM action (Leaf a) = do
lift (putStrLn ("Leaf " ++ show a))
b <- action a
return (Leaf b)
mapTreeM action (Branch lhs rhs) = do
lift (putStrLn "Branch")
lhs' <- mapTreeM action lhs
rhs' <- mapTreeM action rhs
return (Branch lhs' rhs')
此函数与我们在关于 State 的部分中提到的函数之间的唯一区别是 lift (putStrLn ...) 作为第一行的调用。lift 告诉我们我们要在封闭的单子中执行命令。在本例中，封闭的单子是 IO，因为提升的命令是 putStrLn。
此函数的类型比较复杂
mapTreeM :: (MonadTrans t, Monad (t IO), Show a) =>
(a -> t IO a1) -> Tree a -> t IO (Tree a1)
忽略一下类约束，它表明 mapTreeM 接受一个操作和一棵树，并返回一棵树。这与以前一样。在其中，我们要求 t 是单子转换器（因为我们在其中应用了 lift）；我们要求 t IO 是单子，因为我们使用 putStrLn 我们知道封闭的单子是 IO；最后，我们要求 a 是 show 的实例——这仅仅是因为我们使用 show 来显示叶子的值。
现在，我们只需更改 numberTree 以使用此版本的 mapTreeM 以及 get 和 put 的新版本，最终得到
numberTree tree = mapTreeM number tree
where number v = do
cur <- getT
putT (cur+1)
return (v,cur)
使用此，我们可以运行我们的单子
示例
MTrans> evalStateT (numberTree testTree) 0
Branch
Branch
Leaf 'a'
Branch
Leaf 'b'
Leaf 'c'
Branch
Leaf 'd'
Leaf 'e'
*MTrans> it
Branch (Branch (Leaf ('a',0))
(Branch (Leaf ('b',1)) (Leaf ('c',2))))
(Branch (Leaf ('d',3)) (Leaf ('e',4)))
在我们关于 MonadPlus 的讨论中没有指定的一个问题是，我们的搜索算法将无法在包含循环的图上终止。考虑
gr3 = Graph [(0, 'a'), (1, 'b'), (2, 'c'), (3, 'd')]
[(0,1,'l'), (1,0,'m'), (0,2,'n'),
(1,3,'o'), (2,3,'p')]
在这个图中，从节点 b 到节点 a 有一条后向边。如果我们尝试运行 searchAll2，无论我们使用什么单子，它都将无法终止。此外，如果我们将这条错误的边移到列表的末尾（并将其称为 gr4），则 searchAll2 gr4 0 3 的结果将包含无限数量的路径：我们可能只希望路径不包含循环。
为了解决这个问题，我们需要引入状态。也就是说，我们需要跟踪我们访问过的节点，以便我们不再访问它们。
我们可以按如下方式执行此操作
searchAll5 g@(Graph vl el) src dst
| src == dst = do
visited <- getT
putT (src:visited)
return [src]
| otherwise = do
visited <- getT
putT (src:visited)
if src `elem` visited
then mzero
else search' el
where
search' [] = mzero
search' ((u,v,_):es)
| src == u =
(do path <- searchAll5 g v dst
return (u:path)) `mplus`
search' es
| otherwise = search' es
在这里，我们隐式地使用状态转换器（参见对 getT 和 putT 的调用）来跟踪已访问的状态。只有当我们遇到我们尚未访问的状态时，我们才会继续递归。此外，当我们递归时，我们会将当前状态添加到我们已访问状态集中。
现在，我们可以运行状态转换器，即使在循环图上也能得到正确的路径
示例
MTrans> evalStateT (searchAll5 gr3 0 3) [] :: [[Int]] [[0,1,3],[0,2,3]] MTrans> evalStateT (searchAll5 gr4 0 3) [] :: [[Int]] [[0,1,3],[0,2,3]]
在这里，作为 evalStateT 参数提供的空列表是初始状态（即初始已访问列表）。在我们的例子中，它是空的。
我们还可以提供一个 execStateT 方法，该方法不会返回结果，而是返回最终状态。此函数如下所示
execStateT :: Monad m => StateT s m a -> s -> m s execStateT (StateT m) state = do (s', a) <- m state return s'
这在我们这里并不那么有用，因为它将返回与 evalStateT 完全相反的结果（尝试一下，看看！），但总的来说可能很有用（例如，如果我们需要知道 numberTree 中使用了多少个数字）。
| 练习 |
|---|
|
编写一个基于 示例 Exploring 0 -> 3 Exploring 1 -> 3 Exploring 3 -> 3 Exploring 2 -> 3 Exploring 3 -> 3 MTrans> it [[0,1,3],[0,2,3]] 为了实现这一点，你必须定义自己的列表单子 转换器并为其创建适当的实例。 |
| 练习 |
|---|
|
将 |
解析单子
[edit | edit source]事实证明，某些类别的解析器都是单子。这使得在 Haskell 中构建解析库非常干净。在本章中，我们首先在关于 一个简单的解析单子 的部分中构建我们自己的（小型）解析库，然后在最后一部分中介绍 Parsec 解析库。
考虑解析的任务。一个简单的解析 Monad 很像一个状态 Monad，其中状态是未解析的字符串。我们可以准确地表示为
newtype Parser a = Parser
{ runParser :: String -> Either String (String, a) }
我们再次使用 Left err 表示错误条件。这产生了 Monad 和 MonadPlus 的标准实例
instance Monad Parser where
return a = Parser (\xl -> Right (xl,a))
fail s = Parser (\xl -> Left s)
Parser m >>= k = Parser $ \xl ->
case m xl of
Left s -> Left s
Right (xl', a) ->
let Parser n = k a
in n xl'
instance MonadPlus Parser where
mzero = Parser (\xl -> Left "mzero")
Parser p `mplus` Parser q = Parser $ \xl ->
case p xl of
Right a -> Right a
Left err -> case q xl of
Right a -> Right a
Left _ -> Left err
现在，我们想要构建一个解析“原语”库。最基本的原语是一个解析特定字符的解析器。这个函数看起来像
char :: Char -> Parser Char
char c = Parser char'
where char' [] = Left ("expecting " ++ show c ++
" got EOF")
char' (x:xs)
| x == c = Right (xs, c)
| otherwise = Left ("expecting " ++
show c ++ " got " ++
show x)
这里，解析器只有在输入的第一个字符是预期字符时才会成功。
我们可以使用这个解析器构建一个解析字符串“Hello”的解析器
helloParser :: Parser String helloParser = do char 'H' char 'e' char 'l' char 'l' char 'o' return "Hello"
这表明将这些解析器组合在一起是多么容易。我们不需要担心底层字符串——Monad 会为我们处理这些。我们只需要组合这些解析器原语。我们可以通过使用 runParser 并提供输入来测试这个解析器
示例
Parsing> runParser helloParser "Hello"
Right ("","Hello")
Parsing> runParser helloParser "Hello World!"
Right (" World!","Hello")
Parsing> runParser helloParser "hello World!"
Left "expecting 'H' got 'h'"
我们可以有一个稍微更通用的函数，它将匹配任何符合描述的字符
matchChar :: (Char -> Bool) -> Parser Char
matchChar c = Parser matchChar'
where matchChar' [] =
Left ("expecting char, got EOF")
matchChar' (x:xs)
| c x = Right (xs, x)
| otherwise =
Left ("expecting char, got " ++
show x)
使用这个，我们可以编写一个不区分大小写的“Hello”解析器
ciHelloParser = do c1 <- matchChar (`elem` "Hh") c2 <- matchChar (`elem` "Ee") c3 <- matchChar (`elem` "Ll") c4 <- matchChar (`elem` "Ll") c5 <- matchChar (`elem` "Oo") return [c1,c2,c3,c4,c5]
当然，我们可以使用类似于 matchChar ((=='h') . toLower) 的东西，但上面的实现同样有效。我们可以测试这个函数
示例
Parsing> runParser ciHelloParser "hELlO world!"
Right (" world!","hELlO")
最后，我们可以有一个函数，它将匹配任何字符
anyChar :: Parser Char
anyChar = Parser anyChar'
where anyChar' [] =
Left ("expecting character, got EOF")
anyChar' (x:xs) = Right (xs, x)
除了这些原语之外，我们通常还构建一些组合器。例如，many 组合器将接受解析类型为 a 的实体的解析器，并将其转换为解析类型为 [a] 的实体的解析器（这是一个 Kleene-star 运算符）
many :: Parser a -> Parser [a]
many (Parser p) = Parser many'
where many' xl =
case p xl of
Left err -> Right (xl, [])
Right (xl',a) ->
let Right (xl'', rest) = many' xl'
in Right (xl'', a:rest)
这里的想法是，首先我们尝试应用给定的解析器 p。如果失败，我们成功，但返回空列表。如果 p 成功，我们递归并继续尝试应用 p，直到它失败。然后我们返回我们累积的成功列表。
一般来说，会有很多这样的函数，它们会被隐藏在一个库中，这样用户就无法实际查看 Parser 类型内部。但是，使用它们，你可以构建例如解析（非负）整数的解析器
int :: Parser Int int = do t1 <- matchChar isDigit tr <- many (matchChar isDigit) return (read (t1:tr))
在这个函数中，我们首先匹配一个数字（isDigit 函数来自模块 Char/Data.Char），然后匹配尽可能多的其他数字。然后我们 read 结果并返回它。我们可以像以前一样测试这个解析器
示例
Parsing> runParser int "54"
Right ("",54)
*Parsing> runParser int "54abc"
Right ("abc",54)
*Parsing> runParser int "a54abc"
Left "expecting char, got 'a'"
现在，假设我们要解析一个 Haskell 风格的 Int 列表。这变得有点困难，因为在某些时候，我们将解析一个逗号或一个右大括号，但我们不知道这什么时候会发生。这就是 Parser 是 MonadPlus 实例这一事实派上用场的地方：我们首先尝试一个，然后尝试另一个。
考虑以下代码
intList :: Parser [Int]
intList = do
char '['
intList' `mplus` (char ']' >> return [])
where intList' = do
i <- int
r <- (char ',' >> intList') `mplus`
(char ']' >> return [])
return (i:r)
这段代码首先解析并打开大括号。然后，使用 mplus，它尝试两件事之一：使用 intList' 解析，或解析一个右大括号并返回一个空列表。
intList' 函数假设我们还没有到达列表的末尾，因此它首先解析一个 int。然后它解析列表的其余部分。但是，它不知道我们是否已经到达末尾，因此它再次使用 mplus。一方面，它尝试解析一个逗号，然后递归；另一方面，它解析一个右大括号并返回空列表。无论哪种方式，它都只是将它本身解析的 int 预先附加到开头。
你应该注意的一件事是，你向 mplus 提供参数的顺序。考虑以下解析器
tricky = mplus (string "Hal") (string "Hall")
你可能期望这个解析器解析“Hal”和“Hall”这两个词；但是，它只解析前者。你可以用以下方法看到这一点
示例
Parsing> runParser tricky "Hal"
Right ("","Hal")
Parsing> runParser tricky "Hall"
Right ("l","Hal")
这是因为它尝试解析“Hal”，它成功了，然后它不再尝试解析“Hall”。
你可以尝试通过提供一个解析器原语来解决这个问题，该原语检测文件末尾（实际上是字符串末尾）
eof :: Parser ()
eof = Parser eof'
where eof' [] = Right ([], ())
eof' xl = Left ("Expecting EOF, got " ++
show (take 10 xl))
然后你可以使用 eof 重写 tricky
tricky2 = do s <- mplus (string "Hal") (string "Hall") eof return s
但这也不起作用，因为我们可以很容易地看到
示例
Parsing> runParser tricky2 "Hal"
Right ("",())
Parsing> runParser tricky2 "Hall"
Left "Expecting EOF, got \"l\""
这是因为，同样地，mplus 不知道它需要解析整个输入。因此，当你向它提供“Hall”时，它只解析“Hal”并将最后一个“l”留在那里以供稍后解析。这会导致 eof 生成错误消息。
正确实现方法是
tricky3 =
mplus (do s <- string "Hal"
eof
return s)
(do s <- string "Hall"
eof
return s)
我们可以看到这有效
示例
Parsing> runParser tricky3 "Hal"
Right ("","Hal")
Parsing> runParser tricky3 "Hall"
Right ("","Hall")
这之所以有效，正是因为 mplus 的每一侧都知道它必须读取末尾。
在这种情况下，修复解析器以接受“Hal”和“Hall”这两个词非常简单，因为我们假设我们将立即读取文件末尾。不幸的是，如果我们不能立即消除歧义，生活就会变得更加复杂。这是解析中的一个普遍问题，与单子解析关系不大。大多数解析器库（例如，Parsec，参见关于 Parsec 的部分）采用的解决方案是只识别“LL(1)”语法：这意味着你必须能够使用一个标记的预读来消除输入的歧义。
| 练习 |
|---|
|
编写一个解析器 |
有了这个单子解析器，添加有关源位置的信息就很容易了。例如，如果我们正在解析一个大型文件，报告发生错误的行号可能会有所帮助。我们可以简单地通过扩展 Parser 类型并修改实例和原语来做到这一点
newtype Parser a = Parser
{ runParser :: Int -> String ->
Either String (Int, String, a) }
instance Monad Parser where
return a = Parser (\n xl -> Right (n,xl,a))
fail s = Parser (\n xl -> Left (show n ++
": " ++ s))
Parser m >>= k = Parser $ \n xl ->
case m n xl of
Left s -> Left s
Right (n', xl', a) ->
let Parser m2 = k a
in m2 n' xl'
instance MonadPlus Parser where
mzero = Parser (\n xl -> Left "mzero")
Parser p `mplus` Parser q = Parser $ \n xl ->
case p n xl of
Right a -> Right a
Left err -> case q n xl of
Right a -> Right a
Left _ -> Left err
matchChar :: (Char -> Bool) -> Parser Char
matchChar c = Parser matchChar'
where matchChar' n [] =
Left ("expecting char, got EOF")
matchChar' n (x:xs)
| c x =
Right (n+if x=='\n' then 1 else 0
, xs, x)
| otherwise =
Left ("expecting char, got " ++
show x)
char 和 anyChar 的定义没有给出，因为它们可以用 matchChar 来编写。many 函数只需要修改以包含新的状态。
现在，当我们运行一个解析器并且出现错误时，它将告诉我们包含错误的行号
示例
Parsing2> runParser helloParser 1 "Hello" Right (1,"","Hello") Parsing2> runParser int 1 "a54" Left "1: expecting char, got 'a'" Parsing2> runParser intList 1 "[1,2,3,a]" Left "1: expecting ']' got '1'"
我们可以使用之前练习中的 intListSpace 解析器来查看它是否确实有效
示例
Parsing2> runParser intListSpace 1
"[1 ,2 , 4 \n\n ,a\n]"
Left "3: expecting char, got 'a'"
Parsing2> runParser intListSpace 1
"[1 ,2 , 4 \n\n\n ,a\n]"
Left "4: expecting char, got 'a'"
Parsing2> runParser intListSpace 1
"[1 ,\n2 , 4 \n\n\n ,a\n]"
Left "5: expecting char, got 'a'"
我们可以看到，发生错误的行号随着我们在错误的“a”之前添加额外的换行符而增加。
随着你继续开发你的解析器，你可能想要添加越来越多的功能。幸运的是，Graham Hutton 和 Daan Leijen 已经在 Parsec 库中为我们做到了这一点。本节旨在作为 Parsec 库的介绍；它绝不涵盖整个库，但它应该足以让你开始。
与我们的库一样，Parsec 提供了一些基本函数来从字符构建解析器。这些是：char，它与我们的 char 相同；anyChar，它与我们的 anyChar 相同；satisfy，它与我们的 matchChar 相同；oneOf，它接受一个 Char 列表并匹配其中的任何一个；以及 noneOf，它是 oneOf 的反面。
Parsec 用于运行解析器的主要函数是 parse。但是，除了解析器之外，这个函数还接受一个表示你正在解析的文件名的字符串。这样它就可以给出更好的错误消息。我们可以尝试使用上面的函数进行解析
示例
ParsecI> parse (char 'a') "stdin" "a"
Right 'a'
ParsecI> parse (char 'a') "stdin" "ab"
Right 'a'
ParsecI> parse (char 'a') "stdin" "b"
Left "stdin" (line 1, column 1):
unexpected "b"
expecting "a"
ParsecI> parse (char 'H' >> char 'a' >> char 'l')
"stdin" "Hal"
Right 'l'
ParsecI> parse (char 'H' >> char 'a' >> char 'l')
"stdin" "Hap"
Left "stdin" (line 1, column 3):
unexpected "p"
expecting "l"
这里，我们可以看到我们的解析器和 Parsec 之间的一些区别：首先，当我们运行 parse 时，不会返回字符串的其余部分。其次，生成的错误消息要好得多。
除了基本字符解析函数之外，Parsec 还为以下操作提供原语：spaces，它与我们的相同；space，它解析单个空格；letter，它解析一个字母；digit，它解析一个数字；string，它与我们的相同；以及其他一些。
我们可以用 Parsec 编写我们的 int 和 intList 函数
int :: CharParser st Int
int = do
i1 <- digit
ir <- many digit
return (read (i1:ir))
intList :: CharParser st [Int]
intList = do
char '['
intList' `mplus` (char ']' >> return [])
where intList' = do
i <- int
r <- (char ',' >> intList') `mplus`
(char ']' >> return [])
return (i:r)
首先，请注意类型签名。st 类型变量只是一个我们没有使用的状态变量。在 int 函数中，我们使用 many 函数（内置于 Parsec）以及 digit 函数（也内置于 Parsec）。intList 函数实际上与我们之前编写的函数相同。
但是请注意，显式使用 mplus 不是组合解析器的首选方法：Parsec 提供了一个 <|> 函数，它是 mplus 的同义词，但看起来更漂亮
intList :: CharParser st [Int]
intList = do
char '['
intList' <|> (char ']' >> return [])
where intList' = do
i <- int
r <- (char ',' >> intList') <|>
(char ']' >> return [])
return (i:r)
我们可以测试一下
示例
ParsecI> parse intList "stdin" "[3,5,2,10]" Right [3,5,2,10] ParsecI> parse intList "stdin" "[3,5,a,10]" Left "stdin" (line 1, column 6): unexpected "a" expecting digit
除了这些基本组合器之外，Parsec 还提供了一些其他有用的组合器
choice接受一个解析器列表，并在它们之间执行或操作（<|>）。
option接受一个类型为a的默认值和一个返回类型为a的解析器。然后它尝试使用解析器进行解析，但如果解析失败，它使用默认值作为返回值。
optional接受一个返回()的解析器并有选择地运行它。
between接受三个解析器：一个打开解析器，一个关闭解析器和一个中间解析器。它按顺序运行它们并返回中间解析器的值。例如，这可以用于处理intList解析器上的括号。
notFollowedBy接受一个解析器并返回一个解析器，该解析器只有在给定解析器失败时才成功。
假设我们要解析一个简单的计算器语言，它只包含加法和乘法。此外，为了简单起见，假设每个嵌入式表达式都必须用括号括起来。我们可以为这种语言提供一个数据类型
data Expr = Value Int
| Expr :+: Expr
| Expr :*: Expr
deriving (Eq, Ord, Show)
然后编写一个解析这种语言的解析器
parseExpr :: Parser Expr
parseExpr = choice
[ do i <- int; return (Value i)
, between (char '(') (char ')') $ do
e1 <- parseExpr
op <- oneOf "+*"
e2 <- parseExpr
case op of
'+' -> return (e1 :+: e2)
'*' -> return (e1 :*: e2)
]
这里，解析器在两个选项之间交替（我们可以使用<|>，但我希望展示choice组合器的实际应用）。第一个选项简单地解析一个整数，然后将其封装在Value构造函数中。第二个选项使用between解析括号之间的文本。它首先解析一个表达式，然后解析加号或乘号，最后解析另一个表达式。根据操作符的类型，它返回e1 :+: e2或e1 :*: e2。
我们可以修改此解析器，使其不再计算Expr，而是直接计算值
parseValue :: Parser Int
parseValue = choice
[int
,between (char '(') (char ')') $ do
e1 <- parseValue
op <- oneOf "+*"
e2 <- parseValue
case op of
'+' -> return (e1 + e2)
'*' -> return (e1 * e2)
]
我们可以将其用作
示例
ParsecI> parse parseValue "stdin" "(3*(4+3))" Right 21
现在，假设我们要在语言中引入绑定。也就是说，我们希望能够在表达式中使用“let x = 5 in”语句，然后使用我们定义的变量。为了实现这一点，我们需要使用 Parsec 中内置的getState和setState（或updateState）函数。
parseValueLet :: CharParser (FiniteMap Char Int) Int
parseValueLet = choice
[ int
, do string "let "
c <- letter
char '='
e <- parseValueLet
string " in "
updateState (\fm -> addToFM fm c e)
parseValueLet
, do c <- letter
fm <- getState
case lookupFM fm c of
Nothing -> unexpected ("variable " ++ show c ++
" unbound")
Just i -> return i
, between (char '(') (char ')') $ do
e1 <- parseValueLet
op <- oneOf "+*"
e2 <- parseValueLet
case op of
'+' -> return (e1 + e2)
'*' -> return (e1 * e2)
]
int和递归情况保持不变。我们添加了另外两个情况，一个用于处理 let 绑定，另一个用于处理使用情况。
在 let 绑定情况下，我们首先解析“let”字符串，然后解析我们要绑定的字符（letter 函数是 Parsec 的一个解析字母字符的原语），然后解析其值（一个parseValueLet）。然后，我们解析“in”并更新状态以包含此绑定。最后，我们继续解析剩余部分。
在使用情况下，我们简单地解析字符，然后在状态中查找它。但是，如果它不存在，我们将使用 Parsec 原语unexpected 报告错误。
我们可以使用runParser命令来查看此解析器的实际应用，该命令使我们能够提供初始状态
示例
ParsecI> runParser parseValueLet emptyFM "stdin"
"let c=5 in ((5+4)*c)"
Right 45
*ParsecI> runParser parseValueLet emptyFM "stdin"
"let c=5 in ((5+4)*let x=2 in (c+x))"
Right 63
*ParsecI> runParser parseValueLet emptyFM "stdin"
"((let x=2 in 3+4)*x)"
Right 14
请注意，括号不会影响变量的定义。例如，在最后一个示例中，"x" 的使用在某种意义上是在定义范围之外的。但是，我们的解析器没有注意到这一点，因为它以严格的从左到右的方式操作。为了解决此遗漏，需要删除绑定（见练习）。
| 练习 |
|---|
|
修改 |