第 12 章：单子及更多内容（Monads and more）
原文：Graham Hutton, Programming in Haskell, Second Edition, Chapter 12。维护者已确认本书可翻译并发布用于学习研究。
本章通过考虑那些可泛化到一系列参数化类型上的函数，提升 Haskell 中可达到的通用程度。这类参数化类型包括列表、树和输入输出动作。特别地，我们会介绍函子、应用函子和单子，它们分别捕获映射、函数应用和带效果编程的通用概念。
12.1 函子（Functors）
本章介绍的三个新概念，都是把某个常见编程模式抽象成一个定义的例子。我们先用下面两个简单函数回顾这个想法：
inc :: [Int] -> [Int]
inc [] = []
inc (n:ns) = n+1 : inc ns
sqr :: [Int] -> [Int]
sqr [] = []
sqr (n:ns) = n^2 : sqr ns
这两个函数以相同方式定义：空列表映射为自身；非空列表映射为“把某个函数应用到列表头部，并递归处理尾部的结果”。唯一重要区别是应用到每个整数上的函数：第一个例子中是增量函数 (+1)，第二个例子中是平方函数 (^2)。把这个模式抽象出来，就得到熟悉的库函数 map：
map :: (a -> b) -> [a] -> [b]
map f [] = []
map f (x:xs) = f x : map f xs
使用 map 后，我们的两个例子只需给出要应用到每个整数上的函数，就可以更紧凑地定义：
inc = map (+1)
sqr = map (^2)
更一般地说，把一个函数映射到某个数据结构中的每个元素上，这个想法并不限于列表类型，而是可以进一步抽象到许多参数化类型上。支持这类映射函数的类型类称为函子（functors）。在 Haskell 中，这个概念由标准 Prelude 中的下面类声明捕获：
class Functor f where
fmap :: (a -> b) -> f a -> f b
也就是说，为了让参数化类型 f 成为 Functor 类的实例，它必须支持一个指定类型的函数 fmap。直觉上，fmap 接收一个类型为 a -> b 的函数和一个类型为 f a 的结构，其中元素类型为 a；然后它把该函数应用到每个这样的元素上，得到一个类型为 f b 的结构，其中元素类型现在为 b。f 必须是参数化类型，也就是接收另一个类型作为参数的类型，这一点会在类型推断期间根据类声明中 fmap 的指定类型里 f 对类型 a 和 b 的应用自动确定。
示例
正如预期，列表类型可以通过简单地把 fmap 定义为函数 map 而成为函子：
instance Functor [] where
-- fmap :: (a -> b) -> [a] -> [b]
fmap = map
这个声明中的符号 [] 表示不带类型参数的列表类型。它基于这样一个事实：类型 [a] 也可以更原始地写作列表类型 [] 对参数类型 a 的应用，即 [] a。还要注意，上面 fmap 的类型写在注释中，而不是显式写出，因为 Haskell 不允许在实例声明中写这类类型信息。不过，它有助于指导 fmap 的定义，也有文档价值，所以我们会把这类类型写在注释中。
第二个例子是内置类型 Maybe a，它表示类型为 a 的值可能失败或成功：
data Maybe a = Nothing | Just a
把 Maybe 类型做成函子很直接，只需定义一个合适类型的 fmap 函数：
instance Functor Maybe where
-- fmap :: (a -> b) -> Maybe a -> Maybe b
fmap _ Nothing = Nothing
fmap g (Just x) = Just (g x)
这里把参数函数命名为 g，以避免和本节中用 f 表示函子混淆。也就是说，把函数映射到失败值上，会传播失败；而对成功值，则把函数应用到底层值，并重新用标签包装结果。例如：
> fmap (+1) Nothing
Nothing
> fmap (*2) (Just 3)
Just 6
> fmap not (Just False)
Just True
用户定义的类型也可以做成函子。例如，假设声明一种二叉树类型，其叶子中包含数据：
data Tree a = Leaf a | Node (Tree a) (Tree a)
deriving Show
deriving 子句确保树可以显示在屏幕上。参数化类型 Tree 随后可以通过定义 fmap 函数做成函子，该函数会把给定函数应用到树中的每个叶子值：
instance Functor Tree where
-- fmap :: (a -> b) -> Tree a -> Tree b
fmap g (Leaf x) = Leaf (g x)
fmap g (Node l r) = Node (fmap g l) (fmap g r)
例如：
> fmap length (Leaf "abc")
Leaf 3
> fmap even (Node (Leaf 1) (Leaf 2))
Node (Leaf False) (Leaf True)
Haskell 中使用的许多函子 f 都类似上面三个例子：f a 是一个包含类型为 a 的元素的数据结构，这有时称为容器类型，而 fmap 会把给定函数应用到每个这样的元素上。不过，并非所有实例都符合这个模式。例如，IO 类型并不是通常意义上的容器类型，因为它的值表示输入输出动作，我们无法访问其内部结构，但它仍然可以很容易地做成函子：
instance Functor IO where
-- fmap :: (a -> b) -> IO a -> IO b
fmap g mx = do {x <- mx; return (g x)}
在这个例子中，fmap 会把一个函数应用到参数动作的结果值上，因此提供了一种处理这类值的手段。例如：
> fmap show (return True)
"True"
最后总结一下使用函子的两个关键好处。首先，函数 fmap 可以用于处理任何函子结构中的元素。也就是说，我们可以为本质相同的函数使用同一个名字，而不必为每个实例发明单独的名字。其次，我们可以定义可用于任何函子的通用函数。例如，前面那个把列表中每个整数递增的函数，可以通过使用 fmap 而不是 map，泛化到任意函子类型：
inc :: Functor f => f Int -> f Int
inc = fmap (+1)
例如：
> inc (Just 1)
Just 2
> inc [1,2,3,4,5]
[2,3,4,5,6]
> inc (Node (Leaf 1) (Leaf 2))
Node (Leaf 2) (Leaf 3)
函子律
除了提供指定类型的函数 fmap，函子还需要满足两个等式定律：
fmap id = id
fmap (g . h) = fmap g . fmap h
第一个等式说明 fmap 保持恒等函数，也就是说，把 fmap 应用到这个函数上，会返回同一个函数。注意，这个等式中两个 id 的类型不同：左边的 id 类型为 a -> a，因此 fmap id 的类型为 f a -> f a，这意味着右边的 id 也必须具有类型 f a -> f a，整个等式才类型正确。
第二个等式说明 fmap 也保持函数组合，也就是说，把 fmap 应用于两个函数的组合，与分别把 fmap 应用于这两个函数再组合，结果相同。为了让组合类型正确，组成函数 g 和 h 必须分别具有类型 b -> c 和 a -> b。
结合 fmap 的多态类型，函子律确保 fmap 的确执行的是映射操作。以列表为例，它们确保参数列表的结构会被 fmap 保持，也就是说，元素不会被添加、删除或重新排列。例如，假设我们用另一个版本替换内置列表函子，其中 fmap 会反转列表元素的顺序：
instance Functor [] where
-- fmap :: (a -> b) -> [a] -> [b]
fmap g [] = []
fmap g (x:xs) = fmap g xs ++ [g x]
如果你想在 GHCi 中尝试这个例子，必须先声明自己的列表类型，并相应修改上面的声明，以避免与内置列表函子冲突。这个声明类型正确，但不满足函子律，下面的例子展示了这一点：
> fmap id [1,2]
[2,1]
> id [1,2]
[1,2]
> fmap (not . even) [1,2]
[False,True]
> (fmap not . fmap even) [1,2]
[True,False]
我们在示例小节中定义的所有函子都满足函子律。在第 16 章讨论程序推理技术时，我们会看到如何形式化证明这类性质。事实上，对于 Haskell 中任意参数化类型，最多只有一个函数 fmap 能满足所需定律。也就是说，如果可以把某个参数化类型做成函子，那么只有一种方式可以做到。因此，我们为列表、Maybe、Tree 和 IO 定义的实例都是唯一确定的。
12.2 应用函子（Applicatives）
函子抽象的是把一个函数映射到结构中每个元素上的想法。现在假设我们希望推广这个想法，允许映射任意数量参数的函数，而不仅限于单参数函数。更准确地说，假设我们希望定义一组层次化的 fmap 函数，其类型如下：
fmap0 :: a -> f a
fmap1 :: (a -> b) -> f a -> f b
fmap2 :: (a -> b -> c) -> f a -> f b -> f c
fmap3 :: (a -> b -> c -> d) -> f a -> f b -> f c -> f d
...
注意，fmap1 只是 fmap 的另一个名字，而 fmap0 是被映射函数没有参数时的退化情形。一种做法是为每种情形声明一个特殊版本的函子类：Functor0、Functor1、Functor2，依此类推。例如，这样我们就可以写：
> fmap2 (+) (Just 1) (Just 2)
Just 3
不过，这在很多方面都不令人满意。首先，我们必须手工声明 Functor 类的每个版本，尽管它们都遵循类似模式。其次，不清楚应该声明多少这类类，因为它们有无限多个，但我们只能声明有限多个。最后，如果把类型为 (a -> b) -> f a -> f b 的 fmap 看作内置函数应用运算符 (a -> b) -> a -> b 的推广，那么我们可能会期望某种形式的柯里化可以用来得到所需行为。特别是，对于参数数量不同的函数，我们并不需要特殊版本的应用，而是在像 add x y = x + y 这样的定义中依赖柯里化。
事实上，借助柯里化的想法，可以发现任意所需参数数量的 fmap 版本，都可以用下面两个基本函数构造出来：
pure :: a -> f a
(<*>) :: f (a -> b) -> f a -> f b
也就是说，pure 把类型为 a 的值转换成类型为 f a 的结构，而 <*> 是函数应用的一种推广形式，其中参数函数、参数值和结果值都包含在 f 结构中。与普通函数应用一样，运算符 <*> 写在两个参数之间，并假定向左结合。例如：
g <*> x <*> y <*> z
表示：
((g <*> x) <*> y) <*> z
pure 和 <*> 的典型用法具有下面形式：
pure g <*> x1 <*> x2 <*> ... <*> xn
这类表达式称为应用风格（applicative style），因为它与普通函数应用记法 g x1 x2 ... xn 相似。在两种情况下，g 都是一个柯里化函数，接收类型分别为 a1 ... an 的 n 个参数，并产生类型为 b 的结果。不过，在应用风格中，每个参数 xi 的类型是 f ai 而不仅仅是 ai，整体结果类型是 f b 而不是 b。使用这个想法后，可以定义映射函数的层次结构：
fmap0 :: a -> f a
fmap0 = pure
fmap1 :: (a -> b) -> f a -> f b
fmap1 g x = pure g <*> x
fmap2 :: (a -> b -> c) -> f a -> f b -> f c
fmap2 g x y = pure g <*> x <*> y
fmap3 :: (a -> b -> c -> d) -> f a -> f b -> f c -> f d
fmap3 g x y z = pure g <*> x <*> y <*> z
...
自己检查这些定义的类型是一个有用练习。不过，实践中通常不需要显式定义这类映射函数，因为它们可以在需要时构造出来，下一节会看到这一点。支持 pure 和 <*> 函数的函子类称为应用函子（applicative functors），简称 applicatives。在 Haskell 中，这个概念由下面内置类声明捕获：
class Functor f => Applicative f where
pure :: a -> f a
(<*>) :: f (a -> b) -> f a -> f b
示例
利用 Maybe 是函子、因而支持 fmap 这一事实，可以很直接地把这个类型做成应用函子：
instance Applicative Maybe where
-- pure :: a -> Maybe a
pure = Just
-- (<*>) :: Maybe (a -> b) -> Maybe a -> Maybe b
Nothing <*> _ = Nothing
(Just g) <*> mx = fmap g mx
也就是说，函数 pure 把一个值转换成成功结果，而运算符 <*> 会把一个可能失败的函数应用到一个可能失败的参数上，产生一个可能失败的结果。例如：
> pure (+1) <*> Just 1
Just 2
> pure (+) <*> Just 1 <*> Just 2
Just 3
> pure (+) <*> Nothing <*> Just 2
Nothing
以这种方式，Maybe 的应用风格支持一种异常式编程：我们可以把纯函数应用到可能失败的参数上，而不需要自己管理失败传播，因为这会由应用函子机制自动处理。
现在转向列表类型，标准 Prelude 中包含下面的实例声明：
instance Applicative [] where
-- pure :: a -> [a]
pure x = [x]
-- (<*>) :: [a -> b] -> [a] -> [b]
gs <*> xs = [g x | g <- gs, x <- xs]
也就是说，pure 把一个值转换成单元素列表，而 <*> 接收一列函数和一列参数，并依次把每个函数应用到每个参数上，返回所有结果构成的列表。例如：
> pure (+1) <*> [1,2,3]
[2,3,4]
> pure (+) <*> [1] <*> [2]
[3]
> pure (*) <*> [1,2] <*> [3,4]
[3,4,6,8]
应该如何理解这些例子？关键是把类型 [a] 看作 Maybe a 的推广，它允许成功时有多个结果。更准确地说，可以把空列表看作表示失败，而非空列表表示结果可能成功的所有方式。因此，在上面最后一个例子中，第一个参数有两个可能值（1 或 2），第二个参数有两个可能值（3 或 4），从而得到四个可能的乘法结果（3、4、6 或 8）。
更一般地说，考虑一个返回两个整数列表相乘的所有可能方式的函数，它可以用列表推导式定义：
prods :: [Int] -> [Int] -> [Int]
prods xs ys = [x*y | x <- xs, y <- ys]
利用列表是应用函子这一事实，现在也可以给出一个应用风格定义，它避免为中间结果命名：
prods :: [Int] -> [Int] -> [Int]
prods xs ys = pure (*) <*> xs <*> ys
总之，列表的应用风格支持一种非确定性编程：我们可以把纯函数应用到多值参数上，而不需要管理值的选择或失败传播，因为这些都由应用函子机制处理。
本节考虑的最后一个类型是 IO。它可以用下面的声明做成应用函子：
instance Applicative IO where
-- pure :: a -> IO a
pure = return
-- (<*>) :: IO (a -> b) -> IO a -> IO b
mg <*> mx = do {g <- mg; x <- mx; return (g x)}
在这个例子中，pure 由 IO 类型的 return 函数给出，而 <*> 会把一个不纯函数应用到一个不纯参数上，得到一个不纯结果。例如，可以用应用风格定义一个从键盘读取给定数量字符的函数：
getChars :: Int -> IO String
getChars 0 = return []
getChars n = pure (:) <*> getChar <*> getChars (n-1)
也就是说，基本情形只是返回空列表；递归情形则把 cons 运算符应用到读取第一个字符的结果和剩余字符列表上。注意，在后一种情形中，无需为提供给 cons 函数的参数命名；如果使用 do 记法定义，就需要命名它们。
更一般地说，IO 的应用风格支持一种交互式编程：我们可以把纯函数应用到不纯参数上，而不需要管理动作的顺序执行或结果值的提取，因为这些都会由应用函子机制自动处理。
带效果编程
我们引入应用函子的最初动机，是希望把映射的想法推广到多参数函数。这是对应用函子概念的有效解释，但从上面三个实例可以看出，还有另一种更抽象的观点。
这些实例的共同主题是，它们都涉及带效果编程。每种情况下，应用函子机制都提供运算符 <*>，让我们可以用熟悉的应用风格编写程序，其中函数被应用到参数上。关键区别在于：参数不再只是普通值，也可能带有效果，例如可能失败、可能以多种方式成功，或执行输入输出动作。这样，应用函子也可以看作对“把纯函数应用到带效果参数上”这一想法的抽象，而允许的效果的具体形式取决于底层函子的性质。
除了为某种带效果编程提供统一方法之外，使用应用函子还有一个重要好处：可以定义可用于任意应用函子的通用函数。例如，标准库提供了下面的函数：
sequenceA :: Applicative f => [f a] -> f [a]
sequenceA [] = pure []
sequenceA (x:xs) = pure (:) <*> x <*> sequenceA xs
这个函数把一列应用动作转换成单个这样的动作，后者返回结果值列表，并捕获了应用函子编程中的一个常见模式。例如，函数 getChars 现在可以通过把基本动作 getChar 复制所需次数，并执行所得序列，以更简单的方式定义：
getChars :: Int -> IO String
getChars n = sequenceA (replicate n getChar)
应用函子律
除了提供函数 pure 和 <*>，应用函子还需要满足四个等式定律：
pure id <*> x = x
pure (g x) = pure g <*> pure x
x <*> pure y = pure (\g -> g y) <*> x
x <*> (y <*> z) = (pure (.) <*> x <*> y) <*> z
第一个等式说明 pure 保持恒等函数，也就是说，把 pure 应用于这个函数，会得到恒等函数的应用版本。第二个等式说明 pure 也保持函数应用，也就是说，它可以分配到普通函数应用上，得到应用式函数应用。第三个等式说明，当一个带效果函数应用到纯参数上时，求值这两个组成部分的顺序无关紧要。最后，第四个等式说明，在考虑相关类型的前提下，运算符 <*> 是结合的。推导这些定律中各变量的类型是一个有用练习。
应用函子律共同形式化了我们对函数 pure :: a -> f a 的直觉，也就是它把类型为 a 的值嵌入到类型为 f a 的带效果世界的纯片段中。这些定律还确保，任何使用函数 pure 和运算符 <*> 构建出来的类型正确表达式，都可以重写为应用风格，也就是下面形式：
pure g <*> x1 <*> x2 <*> ... <*> xn
特别地，第四条定律会把应用重新结合到左侧，第三条定律会把 pure 的出现移动到左侧，而剩余两条定律允许把零个或多个连续出现的 pure 合并为一个。
我们在示例小节中定义的所有应用函子都满足上述定律。此外，每个实例还满足等式 fmap g x = pure g <*> x，这展示了如何用两个应用函子原语定义 fmap。事实上，后一条定律是免费得到的，因为如 12.1 节末尾所述，对于任意给定参数化类型，只有一种方式可以把它做成函子，因此任何与 fmap 具有相同多态类型的函数都必须等于 fmap。
最后注意，Haskell 还提供了 fmap 的中缀版本，定义为 g <$> x = fmap g x。结合上面关于 fmap 的定律，可以得到应用风格的另一种表达形式：
g <$> x1 <*> x2 <*> ... <*> xn
这种写法稍微更简洁，但出于讲解目的，我们更倾向于显式使用 pure 的版本，以强调应用函子编程的核心是把纯函数应用到带效果参数上。不过，在实际应用中，经常会使用带 <$> 的版本。
12.3 单子（Monads）
本章最后一个新概念捕获了另一种带效果编程模式。举例来说，考虑下面的表达式类型，它由整数值和除法运算符构成：
data Expr = Val Int | Div Expr Expr
这类表达式可以如下求值：
eval :: Expr -> Int
eval (Val n) = n
eval (Div x y) = eval x `div` eval y
不过，这个函数没有考虑除以零的可能性，并且会在这种情况下产生错误：
> eval (Div (Val 1) (Val 0))
*** Exception: divide by zero
为了解决这个问题，可以使用 Maybe 类型定义一个安全版本的除法，当第二个参数为零时返回 Nothing：
safediv :: Int -> Int -> Maybe Int
safediv _ 0 = Nothing
safediv n m = Just (n `div` m)
然后修改求值器，在对两个参数表达式递归调用函数时显式处理失败可能性：
eval :: Expr -> Maybe Int
eval (Val n) = Just n
eval (Div x y) = case eval x of
Nothing -> Nothing
Just n -> case eval y of
Nothing -> Nothing
Just m -> safediv n m
现在，例如有：
> eval (Div (Val 1) (Val 0))
Nothing
这个新版 eval 解决了除以零的问题，但相当啰嗦。为了简化定义，我们可能会利用 Maybe 是应用函子这一事实，尝试用应用风格重新定义 eval：
eval :: Expr -> Maybe Int
eval (Val n) = pure n
eval (Div x y) = pure safediv <*> eval x <*> eval y
不过，这个定义类型不正确。特别是，函数 safediv 的类型为 Int -> Int -> Maybe Int，而在上面的上下文中，需要的是类型 Int -> Int -> Int 的函数。把 pure safediv 替换为自定义函数也无济于事，因为这个函数需要具有类型 Maybe (Int -> Int -> Int)，而这并不能提供任何手段来表示第二个整数参数为零时的失败。
结论是，函数 eval 并不符合应用函子捕获的带效果编程模式。应用风格限制我们只能把纯函数应用到带效果参数上；eval 不符合这个模式，因为用于处理结果值的函数 safediv 并不是纯函数，而是自身也可能失败。
那么，如何以更简单方式重写 eval :: Expr -> Maybe Int？关键是观察其定义中出现了两次的共同模式：对 Maybe 值做 case 分析，把 Nothing 映射到自身，把 Just x 映射到依赖于 x 的某个结果。抽象出这个模式，就得到一个新运算符 >>=，定义如下：
(>>=) :: Maybe a -> (a -> Maybe b) -> Maybe b
mx >>= f = case mx of
Nothing -> Nothing
Just x -> f x
也就是说，>>= 接收一个可能失败的类型为 a 的参数，以及一个类型为 a -> b 但结果可能失败的函数，并返回一个可能失败的类型为 b 的结果。如果参数失败，就传播失败；否则把函数应用到得到的值上。这样，>>= 把 Maybe 类型值的顺序执行和对其结果的处理整合起来。运算符 >>= 通常称为 bind，因为第二个参数会绑定第一个参数的结果。
使用 bind 运算符和 lambda 记法后，可以更紧凑地重新定义 eval：
eval :: Expr -> Maybe Int
eval (Val n) = Just n
eval (Div x y) = eval x >>= \n ->
eval y >>= \m ->
safediv n m
除法情形说明：先对 x 求值，并把结果值命名为 n；然后对 y 求值，并把结果值命名为 m；最后通过应用 safediv 组合这两个结果。这个分支也可以写成一行，但这里拆成多行，以强调其操作性读法。
从上面的例子推广开来，一个使用 >>= 运算符构建的典型表达式具有下面结构：
m1 >>= \x1 ->
m2 >>= \x2 ->
...
mn >>= \xn ->
f x1 x2 ... xn
也就是说，依次求值每个表达式 m1 ... mn，然后把函数 f 应用于它们的结果值 x1 ... xn，从而组合这些结果。>>= 运算符的定义确保这类表达式只有在序列中每个组成部分 mi 都成功时才成功。此外，用户不必关心序列中任意位置的失败可能性，因为这会由 >>= 运算符的定义自动处理。
Haskell 为上述形式的表达式提供了特殊记法，使其可以更简单地写成：
do x1 <- m1
x2 <- m2
...
xn <- mn
f x1 x2 ... xn
这与交互式编程中使用的是同一种记法。和那个场景一样，序列中的每一项必须从同一列开始；如果结果值 xi 不需要使用，则 xi <- mi 可以简写为 mi。使用这个记法后，eval 可以简单地重定义为：
eval :: Expr -> Maybe Int
eval (Val n) = Just n
eval (Div x y) = do n <- eval x
m <- eval y
safediv n m
更一般地说，do 记法并不特定于类型 IO 和 Maybe，而是可以用于任何构成单子的应用类型。在 Haskell 中，单子的概念由下面的内置声明捕获：
class Applicative m => Monad m where
return :: a -> m a
(>>=) :: m a -> (a -> m b) -> m b
return = pure
也就是说，单子是一个应用类型 m，支持指定类型的 return 和 >>= 函数。默认定义 return = pure 意味着 return 通常只是应用函数 pure 的另一个名字，但如果需要，也可以在实例声明中覆盖。
函数 return 出现在 Monad 类中是出于历史原因，也是为了确保与既有代码、文章和教材向后兼容，因为它们假定类声明同时包含 return 和 >>= 函数。不过，在未来某个时候，return 可能会从 Monad 类中移除，改为一个具有下面定义的库函数：
return :: Applicative f => a -> f a
return = pure
如果这个改变被实现，那么将不再可能在实例声明中定义 return，但我们的多数例子不会受到影响，因为通常只是使用默认定义 return = pure。任何所需调整都会在本书网站上说明。
示例
在标准 Prelude 中，Maybe 类型的 bind 运算符为了简单起见使用模式匹配定义，而不是 case 分析：
instance Monad Maybe where
-- (>>=) :: Maybe a -> (a -> Maybe b) -> Maybe b
Nothing >>= _ = Nothing
(Just x) >>= f = f x
正是由于这个声明，do 记法才可以用于 Maybe 值编程，例如上一节中的函数 eval。接着，列表可以如下做成单子类型：
instance Monad [] where
-- (>>=) :: [a] -> (a -> [b]) -> [b]
xs >>= f = [y | x <- xs, y <- f x]
也就是说，xs >>= f 会把函数 f 应用于列表 xs 中的每个结果，并把所有所得值收集到一个列表中。这样，列表的 bind 运算符提供了一种把可能产生多个结果的表达式顺序执行的手段。例如，现在可以用 do 记法定义一个函数，返回从两个列表中配对元素的所有可能方式：
pairs :: [a] -> [b] -> [(a,b)]
pairs xs ys = do x <- xs
y <- ys
return (x,y)
例如：
> pairs [1,2] [3,4]
[(1,3),(1,4),(2,3),(2,4)]
注意，由于默认定义 return = pure，pairs 的最后一行也可以写成 pure (x,y)，但在单子编程中，约定上使用函数 return。它与下面使用推导式记法的定义相似，这一点也很有意思：
pairs :: [a] -> [b] -> [(a,b)]
pairs xs ys = [(x,y) | x <- xs, y <- ys]
不过，推导式记法特定于列表类型，而 do 记法可以用于任意单子。
Prelude 还包含 IO 类型的实例，它支持在交互式编程中使用 do 记法。与上面的其他例子不同，这种情况下 return 和 >>= 的定义内置于语言中，而不是在 Haskell 自身内部定义：
instance Monad IO where
-- return :: a -> IO a
return x = ...
-- (>>=) :: IO a -> (a -> IO b) -> IO b
mx >>= f = ...
状态单子
现在考虑编写那些操作某种随时间变化状态的函数。为简单起见，假设状态只是一个整数值，但也可以按需修改：
type State = Int
这种类型上最基本形式的函数是状态转换器，简写为 ST。它接收输入状态作为参数，并产生输出状态作为结果，其中输出状态反映了该函数执行期间对状态所作的任何更新：
type ST = State -> State
不过，一般而言，除了更新状态外，我们可能还希望返回一个结果值。例如，如果状态表示一个计数器，那么用于递增计数器的函数可能还希望返回其当前值。为此，我们把状态转换器类型推广为也返回一个结果值，而这种值的类型成为 ST 类型的参数：
type ST a = State -> (a,State)
这种函数可以形象地理解为：给定输入状态 s，产生输出状态 s' 和结果值 v。反过来，状态转换器也可能希望接收参数值。不过，没有必要进一步推广 ST 类型来说明这一点，因为这种行为已经可以通过柯里化实现。例如，一个接收字符并返回整数的状态转换器，其类型为 Char -> ST Int，这是柯里化函数类型 Char -> State -> (Int,State) 的简写。
既然 ST 是一个参数化类型，自然会想把它做成单子，这样就可以用 do 记法编写有状态程序。不过，使用 type 机制声明的类型不能做成类实例。因此，我们先使用 newtype 机制重新定义 ST，这需要引入一个哑构造子，这里称为 S：
newtype ST a = S (State -> (a,State))
同时，为这个类型定义一个专用应用函数也很方便，它只是移除哑构造子：
app :: ST a -> State -> (a,State)
app (S st) x = st x
作为把参数化类型 ST 做成单子的第一步，很容易先把它做成函子：
instance Functor ST where
-- fmap :: (a -> b) -> ST a -> ST b
fmap g st = S (\s -> let (x,s') = app st s in (g x, s'))
也就是说，fmap 允许我们把一个函数应用到状态转换器的结果值上。这个 let 机制类似 where 机制，但它允许在表达式层面而不是函数定义层面进行局部定义。接着，类型 ST 可以做成应用函子：
instance Applicative ST where
-- pure :: a -> ST a
pure x = S (\s -> (x,s))
-- (<*>) :: ST (a -> b) -> ST a -> ST b
stf <*> stx = S (\s ->
let (f,s') = app stf s
(x,s'') = app stx s' in (f x, s''))
在这个例子中，函数 pure 把一个值转换为一个状态转换器，后者只是返回这个值而不修改状态。运算符 <*> 则把一个返回函数的状态转换器应用到一个返回参数的状态转换器上，得到一个返回函数应用结果的状态转换器。符号 $ 表示普通函数应用，定义为 f $ x = f x。
最后，ST 的单子实例声明如下：
instance Monad ST where
-- (>>=) :: ST a -> (a -> ST b) -> ST b
st >>= f = S (\s -> let (x,s') = app st s in app (f x) s')
也就是说，st >>= f 会把状态转换器 st 应用到初始状态 s，然后把函数 f 应用于得到的值 x，产生一个新状态转换器 f x，后者再应用到新状态 s'，得到最终结果。这样，状态单子的 bind 运算符把状态转换器的顺序执行与其结果值的处理整合起来。注意，在 >>= 的定义中，我们产生了一个新的状态转换器 f x，其行为可以依赖第一个参数的结果值 x；而使用 <*> 时，我们受限于使用显式提供为参数的状态转换器。因此，使用 >>= 运算符提供了额外的灵活性。
重新标记树
作为有状态编程的例子，我们开发一个树的重新标记函数，为此使用下面的类型：
data Tree a = Leaf a | Node (Tree a) (Tree a)
deriving Show
例如，可以定义：
tree :: Tree Char
tree = Node (Node (Leaf 'a') (Leaf 'b')) (Leaf 'c')
现在考虑定义一个函数，用唯一或新鲜的整数重新标记这类树中的每个叶子。对于像 Haskell 这样的纯语言，可以通过把下一个新鲜整数作为额外参数，并把下一个新鲜整数作为额外结果来实现：
rlabel :: Tree a -> Int -> (Tree Int, Int)
rlabel (Leaf _) n = (Leaf n, n+1)
rlabel (Node l r) n = (Node l' r', n'')
where
(l',n') = rlabel l n
(r',n'') = rlabel r n'
例如：
> fst (rlabel tree 0)
Node (Node (Leaf 0) (Leaf 1)) (Leaf 2)
不过，rlabel 的定义因为需要显式地把整数状态穿过计算而变得复杂。为了得到更简单的定义，首先注意到类型 Tree a -> Int -> (Tree Int, Int) 可以用状态转换器类型重写为 Tree a -> ST (Tree Int)，其中状态是下一个新鲜整数。下一个这样的整数可以通过定义一个状态转换器生成，它只是把当前状态作为结果返回，并把下一个整数作为新状态：
fresh :: ST Int
fresh = S (\n -> (n, n+1))
利用 ST 是应用函子这一事实，现在可以定义一个以应用风格写成的新版重新标记函数：
alabel :: Tree a -> ST (Tree Int)
alabel (Leaf _) = Leaf <$> fresh
alabel (Node l r) = Node <$> alabel l <*> alabel r
回忆一下，g <$> x 的行为与 pure g <*> x 相同。这个新版本给出与之前相同的结果：
> fst (app (alabel tree) 0)
Node (Node (Leaf 0) (Leaf 1)) (Leaf 2)
不过，它的定义要简单得多。在基本情形中，现在只是把 Leaf 构造子应用到下一个新鲜整数上；而在递归情形中，把 Node 构造子应用到标记两个子树的结果上。特别是，程序员不再需要操心把整数状态穿过计算这种繁琐且容易出错的任务，因为这会由应用函子机制自动处理。
利用 ST 也是单子这一事实，可以用 do 记法定义一个等价的单子版本重新标记函数：
mlabel :: Tree a -> ST (Tree Int)
mlabel (Leaf _) = do n <- fresh
return (Leaf n)
mlabel (Node l r) = do l' <- mlabel l
r' <- mlabel r
return (Node l' r')
这个定义类似应用函子版本，只是现在需要为中间结果命名。当一个非泛型函数（如 rlabel）既可以用应用风格定义，也可以用单子风格定义时，选择哪一种大多是品味问题。
通用函数
抽象出单子概念的一个重要好处，是可以定义适用于任意单子的通用函数。库 Control.Monad 提供了许多这样的函数。例如，列表上 map 函数的单子版本可以定义如下：
mapM :: Monad m => (a -> m b) -> [a] -> m [b]
mapM f [] = return []
mapM f (x:xs) = do y <- f x
ys <- mapM f xs
return (y:ys)
注意，mapM 的类型与 map 相同，只是参数函数和该函数本身现在都具有单子返回类型。为了说明它的用法，考虑一个函数，它把数字字符转换为其数值，前提是该字符确实是数字：
conv :: Char -> Maybe Int
conv c | isDigit c = Just (digitToInt c)
| otherwise = Nothing
函数 isDigit 和 digitToInt 由 Data.Char 提供。把 mapM 应用于函数 conv 后，就得到一种把数字字符串转换成相应数值列表的方法：如果字符串中每个字符都是数字则成功，否则失败：
> mapM conv "1234"
Just [1,2,3,4]
> mapM conv "123a"
Nothing
接着，列表上 filter 函数的单子版本可以用类似 mapM 的方式泛化其类型和定义：
filterM :: Monad m => (a -> m Bool) -> [a] -> m [a]
filterM p [] = return []
filterM p (x:xs) = do b <- p x
ys <- filterM p xs
return (if b then x:ys else ys)
例如，在列表单子的情形中，使用 filterM 提供了一种特别简洁的方式来计算列表的幂集。幂集由包含或排除列表中每个元素的所有可能方式给出：
> filterM (\x -> [True,False]) [1,2,3]
[[1,2,3],[1,2],[1,3],[1],[2,3],[2],[3],[]]
最后一个例子是，Prelude 中列表上的函数 concat :: [[a]] -> [a] 可以如下泛化到任意单子：
join :: Monad m => m (m a) -> m a
join mmx = do mx <- mmx
x <- mx
return x
这个函数会把嵌套的单子值展平成普通单子值。对于列表单子，它的行为与 concat 相同；而对于 Maybe 单子，只有外层和内层值都成功时才成功：
> join [[1,2],[3,4],[5,6]]
[1,2,3,4,5,6]
> join (Just (Just 1))
Just 1
> join (Just Nothing)
Nothing
> join Nothing
Nothing
单子律
类似函子和应用函子，两个单子原语也需要满足一些等式定律：
return x >>= f = f x
mx >>= return = mx
(mx >>= f) >>= g = mx >>= (\x -> (f x >>= g))
前两个等式涉及 return 和 >>= 之间的联系。第一个等式说明，如果我们返回一个值，然后把它馈入一个单子函数，这应该与直接把函数应用到该值上得到相同结果。对偶地，第二个等式说明，如果我们把一个单子计算的结果馈入函数 return，这应该与直接执行这个计算得到相同结果。结合来看，除去 >>= 的第二个参数涉及绑定操作这一点，这两个等式说明 return 是运算符 >>= 的恒等元。
第三个等式涉及 >>= 与自身之间的联系，并表达了 >>= 是结合的，同样要忽略绑定带来的细节。注意，不能简单地把这个等式右边写作 mx >>= (f >>= g)，因为这并不是类型正确的。我们见过的所有单子都满足上述定律。
12.4 章注（Chapter remarks）
函子和单子来自范畴论 [17]，这是研究代数结构的一种数学方法。在 Haskell 中，参数化类型最多只有一种方式可以做成函子，这一说法假设我们没有使用会强制求值的特殊语言特性，例如 seq 和 $!。函数式编程中对单子的使用由 Wadler [18] 发展而来，而应用函子由文献 [19] 引入。文献 [15] 对 IO 单子进行了更深入探索，树重新标记示例来自文献 [20]。
12.5 练习（Exercises）
- 为下面这种二叉树类型定义
Functor类实例，其中节点包含数据：
data Tree a = Leaf | Node (Tree a) a (Tree a)
deriving Show
- 完成下面的实例声明，把部分应用的函数类型
(a ->)做成函子：
instance Functor ((->) a) where
...
提示：先写出 fmap 的类型，然后思考是否已经知道某个具有该类型的库函数。
- 为类型
(a ->)定义Applicative类实例。如果熟悉组合子逻辑，你可能会认出这个类型上的pure和<*>正是著名的 K 和 S 组合子。 - 把一个参数化类型做成应用函子的方法可能不止一种。例如，库
Control.Applicative为列表提供了一个替代的“zippy”实例，其中函数pure会创建一个由参数副本组成的无限列表，而运算符<*>会把每个参数函数应用到同一位置的对应参数值上。完成下面实现这一想法的声明：
newtype ZipList a = Z [a] deriving Show
instance Functor ZipList where
-- fmap :: (a -> b) -> ZipList a -> ZipList b
fmap g (Z xs) = ...
instance Applicative ZipList where
-- pure :: a -> ZipList a
pure x = ...
-- <*> :: ZipList (a -> b) -> ZipList a -> ZipList b
(Z gs) <*> (Z xs) = ...
列表类型外面的 ZipList 包装器是必需的，因为每个类型对给定类最多只能有一个实例声明。
- 推导四条应用函子律中各变量的类型。
- 为类型
(a ->)定义Monad类实例。 - 给定下面的表达式类型：
data Expr a = Var a | Val Int | Add (Expr a) (Expr a)
deriving Show
其中包含某种类型 a 的变量。说明如何把这个类型做成 Functor、Applicative 和 Monad 类的实例。借助一个例子，解释这个类型上的 >>= 运算符做了什么。
- 在实践中，与其按照
Functor、Applicative、Monad的顺序把一个参数化类型做成这些类的实例，有时更简单的做法是，根据单子实例定义函子和应用函子实例，并利用 Haskell 中声明顺序并不重要这一事实。使用do记法补全下面ST类型声明中的缺失部分。
instance Functor ST where
-- fmap :: (a -> b) -> ST a -> ST b
fmap g st = do ...
instance Applicative ST where
-- pure :: a -> ST a
pure x = S (\s -> (x,s))
-- (<*>) :: ST (a -> b) -> ST a -> ST b
stf <*> stx = do ...
instance Monad ST where
-- (>>=) :: ST a -> (a -> ST b) -> ST b
st >>= f = S (\s ->
let (x,s') = app st s in app (f x) s')
练习 1-4 的解答见附录 A。