Haskell/理解单子

关于单子，甚至关于 "单子" 这个词本身，都存在着某种神秘感。虽然我们这组章节的目标之一就是揭开围绕它们的神秘面纱，但要理解这种神秘感是怎样产生的并不难。单子在 Haskell 中非常有用，但这个概念起初往往很难理解。由于单子有如此多的应用，人们经常从特定的角度来解释它们，这可能会阻碍你全方位理解它们。

从历史上看，单子被引入 Haskell 用于执行输入和输出 - 也就是我们在 简单的输入和输出 章和 这部分的序章 中讨论的那种 I/O 操作。对于像读取和写入文件这样的操作，预定的执行顺序至关重要，而单子操作自然适合于这种顺序执行。但是，单子绝不局限于输入和输出。它们可以用来提供各种各样的功能，例如异常、状态、非确定性、延续、协程等等。事实上，由于单子的多功能性，这些构造并不需要作为语言内置于 Haskell 中；相反，它们是由标准库定义的。

在 序章 中，我们从一个例子开始，并用它逐步介绍了一些新的概念。在这里，我们将以相反的方式进行，从单子的定义开始，并以此建立起与我们已经了解的知识之间的联系。

定义

一个单子 由三部分组成

• 一个 类型构造器 m；
• 一个函数 return；
• 一个运算符 (>>=)，读作 "绑定"。

该函数和运算符是 Monad 类型类的成员，其类型分别为

return :: a -> m a
(>>=)  :: m a -> (a -> m b) -> m b

并且需要满足后面将解释的 三个定律。

举一个具体的例子，考虑 Maybe 单子。类型构造器为 m = Maybe，而 return 和 (>>=) 的定义如下

return :: a -> Maybe a
return x  = Just x

(>>=)  :: Maybe a -> (a -> Maybe b) -> Maybe b
m >>= g = case m of
             Nothing -> Nothing
             Just x  -> g x

Maybe 是单子，return 通过用 Just 包裹一个值来将其引入单子。至于 (>>=)，它接受一个 m :: Maybe a 值和一个 g :: a -> Maybe b 函数。如果 m 是 Nothing，则无需执行任何操作，结果为 Nothing。否则，在 Just x 的情况下，g 应用于 x（包裹在 Just 中的底层值），从而得到一个 Maybe b 结果。注意，该结果可能为 Nothing 也可能不为 Nothing，具体取决于 g 对 x 的处理。总而言之，如果 m 中存在一个类型为 a 的底层值，我们将其应用于 g，这将把底层值重新引入 Maybe 单子。

理解 return 和 (>>=) 如何工作的关键第一步是跟踪哪些值和参数是单子的，哪些不是。就像在许多其他情况下一样，类型签名是我们的指导。

动机：Maybe

为了了解 (>>=) 和 Maybe 单子的用处，请考虑以下示例：想象一个家庭数据库，它提供了两个函数

father :: Person -> Maybe Person
mother :: Person -> Maybe Person

这些函数用来查找某人的父亲或母亲的名字。如果我们的数据库缺少一些相关信息，Maybe 允许我们返回一个 Nothing 值来表示查找失败，而不是导致程序崩溃。

让我们将我们的函数组合起来，以查询不同的祖父母。例如，以下函数用来查找外祖父（母亲的父亲）

maternalGrandfather :: Person -> Maybe Person
maternalGrandfather p =
    case mother p of
        Nothing -> Nothing
        Just mom -> father mom

或者，考虑一个函数来检查两位外祖父是否都在数据库中

bothGrandfathers :: Person -> Maybe (Person, Person)
bothGrandfathers p =
    case father p of
        Nothing -> Nothing
        Just dad ->
            case father dad of
                Nothing -> Nothing
                Just gf1 ->                          -- found first grandfather
                    case mother p of
                        Nothing -> Nothing
                        Just mom ->
                            case father mom of
                                Nothing -> Nothing
                                Just gf2 ->          -- found second grandfather
                                    Just (gf1, gf2)

真是太麻烦了！每个查询都可能因为返回 Nothing 而失败，如果这种情况发生，整个函数也会因为返回 Nothing 而失败。

显然，必须有一种更好的方法来编写这段代码，而不是一遍又一遍地重复 Nothing 的情况！确实，这就是 Maybe 单子所要做的。例如，用于检索外祖父的函数与 (>>=) 运算符具有完全相同的结构，因此我们可以将其改写为

maternalGrandfather p = mother p >>= father

借助 lambda 表达式和 return，我们也可以改写两个外祖父的函数

bothGrandfathers p =
   father p >>=
       (\dad -> father dad >>=
           (\gf1 -> mother p >>=   -- gf1 is only used in the final return
               (\mom -> father mom >>=
                   (\gf2 -> return (gf1,gf2) ))))

虽然这些嵌套的 lambda 表达式可能看起来很令人困惑，但这里需要注意的是，(>>=) 使我们摆脱了列出所有 Nothing 的麻烦，将注意力重新转移到代码的有趣部分。

更准确地说：father p 的结果是一个单子值（在本例中，根据 p 的父亲是否在数据库中，结果要么是 Just dad，要么是 Nothing）。由于 father 函数接受一个普通（非单子）值，因此 (>>=) 将 p 的 dad 作为一个非单子 值传递给它。father dad 的结果再次成为单子，这个过程持续进行。

因此，(>>=) 帮助我们将非单子值传递给函数，而无需真正离开单子。在 Maybe 单子中，单子方面是指关于是否能找到值的不确定性。

类型类

在 Haskell 中，Monad 类型类用来实现单子。它由 Control.Monad 模块提供，并包含在 Prelude 中。该类具有以下成员方法

class Applicative m => Monad m where
    return :: a -> m a
    (>>=)  :: m a -> (a -> m b) -> m b

    (>>)   :: m a -> m b -> m b
    fail   :: String -> m a

除了 return 和 bind 之外，还有两个额外的成员方法，(>>) 和 fail。它们都有默认实现，因此在编写实例时不需要提供它们。

运算符 (>>)，读作 "然后"，只是一种方便的工具，其默认实现为

m >> n = m >>= \_ -> n

当第二个操作不涉及第一个操作的结果时，(>>) 用于对两个单子操作进行排序，这在 IO 等单子中是一种常见的情况。

printSomethingTwice :: String -> IO ()
printSomethingTwice str = putStrLn str >> putStrLn str

函数 fail 用于处理 do 符号 中的模式匹配失败。它是一个不幸的技术必需品，与单子本身没有直接关系。建议不要在代码中直接调用 fail。

Monad 和 Applicative

需要注意的是，Applicative 是 Monad 的超类。 这有几个值得强调的后果。首先，每个 Monad 也是一个 Functor 和 Applicative，因此 fmap、pure、(<*>) 都可以与单子一起使用。其次，实际编写 Monad 实例也需要提供 Functor 和 Applicative 实例。我们将在本章后面讨论如何做到这一点。第三，如果你已经学习了 序章，那么 return 和 (>>=) 的类型和作用应该看起来很熟悉...

(*>) :: Applicative f => f a -> f b -> f b
(>>) :: Monad m => m a -> m b -> m b

pure :: Applicative f => a -> f a
return :: Monad m => a -> m a

(*>) 和 (>>) 类型的唯一区别在于约束从 Applicative 变成了 Monad。实际上，这是这两种方法的唯一区别：如果你在处理 Monad，你总是可以替换 (*>) 和 (>>)，反之亦然。pure/return 也一样——事实上，如果 Applicative 实例中存在 pure 的独立定义，甚至不需要实现 return，因为 return = pure 是 return 的默认定义。

计算的概念

我们已经看到 (>>=) 和 return 如何方便地用于移除使用 Maybe 时出现的样板代码。然而，这还不足以证明为什么 monad 如此重要。我们下一步将以一种截然不同的风格重写两位祖父函数：使用 do 语法，并带有 显式花括号和分号。根据你对其他编程语言的经验，你可能会发现这很有启发性

bothGrandfathers p = do {
    dad <- father p;
    gf1 <- father dad;
    mom <- mother p;
    gf2 <- father mom;
    return (gf1, gf2);
  }

如果你觉得这看起来像一个命令式编程语言的代码片段，那是因为它是。特别是，这种命令式语言支持 *异常* ：father 和 mother 是可能无法产生结果的函数，而是会引发异常；当这种情况发生时，整个 do 块将 *失败*，即以异常终止（意味着在此评估为 Nothing）。

换句话说，表达式 father p 的类型是 Maybe Person，它被解释为命令式 *语言* 中的语句，该语句返回一个 Person 作为结果，或者失败。

对于所有 monad 来说都是如此：类型 M a 的值被解释为命令式语言 M 中的 *语句*，该语句返回类型 a 的值作为其结果；这种语言的语义由 monad M 决定。^[3]

在这种解释下， *then* 运算符 (>>) 只是分号的实现，而 (>>=) 则是分号和先前计算步骤结果的赋值（绑定）。就像 let 表达式可以写成函数应用一样，

   let x = foo in (x + 3)        corresponds to      foo  &  (\x -> id (x + 3))      -- v & f = f v 

赋值和分号可以用绑定运算符编写

   x <- foo; return (x + 3)      corresponds to      foo >>= (\x -> return (x + 3))

在函数的情况下，& 和 id 是微不足道的；在 monad 的情况下，>>= 和 return 则是实质性的。

& 运算符组合了两个纯粹的 *计算*，foo 和 id (x + 3)，同时为变量 x 创建一个新绑定来保存 foo 的 *值*，使 x 可用于第二个计算步骤，id (x + 3)。

绑定运算符 >>= 组合了两个 *计算* 步骤，foo 和 return (x + 3)，以 monad M 特定的方式，同时为变量 x 创建一个新绑定来保存 foo 的 *结果*，使 x 可用于下一个计算步骤，return (x + 3)。在 Maybe 的特定情况下，如果 foo 无法产生结果，则会跳过第二步，整个组合计算也会立即失败。

函数 return 将一个普通值 a 提升到 M a，也就是命令式语言 M 中的语句，当执行/运行时，该语句将在没有任何特定于 M 的额外效果的情况下产生值 a。这由 Monad Laws 保证，foo >>= return === foo 和 return x >>= k === k x；见下文。

注意

(>>=) 以及因此 Monad 位于 do 块中的左箭头背后的这一事实解释了为什么我们无法在 序言 中解释它们，当时我们只了解 Functor 和 Applicative。Applicative 足以提供 do 块的一些功能，但不是全部。

命令式语言的不同语义对应于不同的 monad。下表展示了每个 Haskell 程序员都应该知道的经典选择。如果你对 monad 的概念仍然不清楚，学习以下章节中的每个示例不仅会让你获得一个全面的工具箱，还能帮助你理解它们背后的共同抽象。

Monad	命令式语义	维基教科书章节
Maybe	异常（匿名）	Haskell/Understanding monads/Maybe
错误	异常（带错误描述）	Haskell/Understanding monads/Error
IO	输入/输出	Haskell/Understanding monads/IO
[] （列表）	非确定性	Haskell/Understanding monads/List
Reader	环境	Haskell/Understanding monads/Reader
Writer	记录器	Haskell/Understanding monads/Writer
State	全局状态	Haskell/Understanding monads/State

此外，这些不同的语义不需要孤立地发生。正如我们将在接下来的几章中看到，可以通过使用 monad 变换器 将多个 monad 的语义组合成单个 monad 来混合和匹配它们。

Monad Laws

在 Haskell 中，Monad 类型类 (以及因此所有绑定 (>>=) 和 return 的实现) 的每个实例都必须遵循以下三条定律

m >>= return     =  m                        -- right unit
return x >>= f   =  f x                      -- left unit

(m >>= f) >>= g  =  m >>= (\x -> f x >>= g)  -- associativity

Return 作为中性元素

return 的行为由左单位律和右单位律指定。它们指出 return 不执行任何计算，它只是收集值。例如，

maternalGrandfather p = do
        mom <- mother p
        gf  <- father mom
        return gf

与

maternalGrandfather p = do
        mom  <- mother p
        father mom

完全相同，这是由于右单位律。

绑定的结合律

结合律确保 (就像分号一样) 绑定运算符 (>>=) 只关心计算的顺序，而不关心它们的嵌套；例如，我们可以这样写 bothGrandfathers (与我们最早没有 do 的版本相比)

bothGrandfathers p =
   (father p >>= father) >>=
       (\gf1 -> (mother p >>= father) >>=
           (\gf2 -> return (gf1,gf2) ))

*then* 运算符 (>>) 的结合律是一个特例

(m >> n) >> o  =  m >> (n >> o)

Monadic 组合

通过将定律重铸为

(f >=> g) >=> h  =  f >=> (g >=> h)

更容易理解绑定的结合律，其中 (>=>) 是 *monad 组合运算符*，它是函数组合运算符 (.) 的近似模拟，只是参数反转了。它被定义为

(>=>) :: Monad m => (a -> m b) -> (b -> m c) -> a -> m c
f >=> g = \x -> f x >>= g

还有 (<=<)，它是 (>=>) 的反转版本。当使用它时，组合的顺序与 (.) 相匹配，因此在 (f <=< g) 中 g 首先出现。^[4]

Monad 和范畴论

Monad 最初来自数学中称为范畴论的一个分支。幸运的是，要理解和使用 Haskell 中的 monad，完全不需要理解范畴论。范畴论中对 monad 的定义实际上使用了略微不同的表示。翻译成 Haskell，这种表示给出了 monad 的一个替代但等效的定义，这可以让我们对 Monad 类有一些额外的见解。^[5]

到目前为止，我们已经用 (>>=) 和 return 来定义 monad。相反，替代定义将 monad 视为具有两个附加组合器的函子

fmap   :: (a -> b) -> M a -> M b  -- functor

return :: a -> M a
join   :: M (M a) -> M a

出于本文讨论的目的，我们将使用在 有关函子类的章节 中讨论的函子作为容器的隐喻。根据它，函子 M 可以被认为是容器，因此 M a "包含" 类型为 a 的值，并具有相应的映射函数，即 fmap，它允许将函数应用于容器内部的值。

在这种解释下，这些函数的行为如下

• fmap 将给定函数应用于容器中的每个元素
• return 将元素打包到容器中，
• join 获取容器的容器并将它扁平化为单个容器。

使用这些函数，绑定组合器可以定义如下

m >>= g = join (fmap g m)

同样，我们可以给出 fmap 和 join 的定义，它们用 (>>=) 和 return 表示

fmap f x = x >>= (return . f)
join x   = x >>= id

liftM 及其朋友

之前，我们指出每个 Monad 都是一个 Applicative，因此也是一个 Functor。其中一个结果是 return 和 (>>) 分别是 pure 和 (*>) 的 monad 版本。然而，这并非全部。首先，Control.Monad 定义了 liftM，它是一个具有奇怪熟悉的类型签名的函数...

liftM :: (Monad m) => (a1 -> r) -> m a1 -> m r

正如你可能猜到的那样，liftM 只是用 (>>=) 和 return 实现的 fmap，就像我们在上一节中做的那样。因此，liftM 和 fmap 是可以互换的。

另一个带有奇特类型的 Control.Monad 函数是 ap

ap :: Monad m => m (a -> b) -> m a -> m b

类似于其他情况，ap 是 (<*>) 的一个仅限于单子的版本。

在 Control.Monad 和其他基本库模块中，还有很多其他 Applicative 函数具有专门针对 Monad 的版本。它们的存在主要是因为历史原因：在 Haskell 中引入 Monad 和 Applicative 之间经过了几年，Applicative 成为 Monad 的超类更是花了几年的时间，因此使用专门的变体成为可选的。虽然原则上如今几乎不需要使用仅限于单子的版本，但实际上你会在其他人的代码中经常看到 return 和 (>>) - 现在，它们的使用已经很成熟，这得益于超过二十年的 Haskell 实践，而 Applicative 还没有成为 Monad 的超类。

注意

鉴于 Applicative 是 Monad 的超类，实现 Monad 最明显的方法是从编写 Functor 实例开始，然后沿着类层次结构向下移动。

instance Functor Foo where
    fmap = -- etc.

instance Applicative Foo where
    pure = -- etc.
    (<*>) = -- etc.

instance Monad Foo where
    (>>=) = -- etc.

在阅读接下来的几章时，你可能想要编写 Monad 的实例并尝试它们，无论是为了运行书中的示例还是为了进行你可能想到的其他实验。然而，以上面所示的方式编写实例需要实现 pure 和 (<*>)，这在本书的此时此刻并不是一个舒适的任务，因为我们还没有介绍 Applicative 法则（我们只会在 应用性函子章节 中介绍）。幸运的是，有一个变通方法：只实现 (>>=) 和 return，从而提供一个自包含的 Monad 实例，然后使用 liftM、ap 和 return 来填补其他实例。

instance Monad Foo where
    return = -- etc.
    (>>=) = -- etc.

instance Applicative Foo where
    pure = return
    (<*>) = ap

instance Functor Foo where
    fmap = liftM

关于单子的这一系列初始章节中的示例和练习不需要编写 Applicative 实例，因此你可以使用这种变通方法，直到我们详细讨论 Applicative。