另一篇 Monad 教程

Haskell 社区一直以来流传着一个笑话,每个 Haskell 程序员在学习 Haskell 的过程中,总是会写一两篇 monad 教程,当然我也不例外。既然已经知道有许多篇 monad 教程了,况且其中有些还不错,为什么我还要写再写一篇呢? 原因有两个:

  1. 与我所见过的大多数 monad 教程相比,我觉得我可以比更好地解释 monad 的某些方面;
  2. 我自己对 monad 的理解有了不小的提高,我想尽力将其传递下去。

前提条件

因为我会在例子中使用 Haskell 语言,所以如果你了解过 Haskell 以及多态类型和类型类的话,对理解会很有帮助,不然你可能会发现文章里的材料很难理解。网上和书上都有很多非常不错的 Haskell 入门教程,你可能需要在阅读其中的一篇文章之后,再回到本文章。

但我不会假设你了解与范畴论(category theory)相关的任何知识。范畴论是数学中一个非常抽象的分支,本文中 monad 的概念就起源于此。尽管了解范畴论也没有什么害处,但只是为了理解这里的材料是绝对不需要的。所以不要相信任何告诉你需要先了解范畴论,才能在编程语言中理解 monad 的人。但如果你确实了解范畴论,这当然对你会有好处,但你会意识到,我不会在这里费力使用范畴论的术语(除了 “monad”这个词)。

免责声明

我不会在本文中教你有关 monad 所有知识,原因有两个:一是这样花费的时间太长了,二是我也不知道有关 monad 所有知识,而且可能永远不会知道。相反,我想给你一个清晰的概念性的理解,即什么是 monad,它为什么有用,它的主要工作原理,以及一些最常用的 monad。在本文的最后,我会提供一些参考资料,以供进一步的研究。

我也不会给你大量实用的代码示例,让你可以立即用于日常编程工作中,这不是一个 cookbook!我相信在编程时你需要真正理解自己在做什么,而本文旨在使您对 monad 有细致的理解。弄懂了本文,你就可以再去阅读其他的 monad 教程(参见参考资料),来更好地了解如何使用 monad 解决实际的编程问题。但本文的目的是让你从整体上把握,并帮助你真正了解什么是 monad 以及它们是如何工作的。

最后,我事先警告你,我会一遍又一遍地反复重复要点,直到你基本上把它们都搞清楚,因为我真的希望你可以理解我要表达的。我希望它不会很无聊,但是它会不可避免的很长,因为 monad 很难用几句话来解释清楚。所以,请坐在舒服的椅子上,泡上一杯茶,这需要花费一些时间。

动机:为什么你应该关心 monad ?

据我所知,在 Eugenio Moggi 和 Philip Wadler (两位我不能望其项背的巨人)的作品的基础上,编程语言中在 Haskell 中首次使用了 monad。从那时起,它们就在其他的一些编程语言(特别是函数式语言)中出现了。但为什么你(我假定你是一个可能还没有尝试过函数式的程序员)应该关心 monad 呢?

函数式编程的主要思想之一是尽可能多地使用纯函数。一个纯函数是一个黑盒子:它接受输入参数,然后计算并返回一个值,仅此而已。它在这个过程中不会产生任何的副作用:不读写文件或套接字,不打印至终端,不读取或更改全局变量,不引发或捕获异常等。这样做的好处是纯函数表现良好:如果给纯函数一个特定的输入,它始终产生完全相同的输出。这使得纯函数非常易于测试,完全可预测,且不容易出错。相反,非纯函数(具有副作用的函数)在给定相同输入的情况下不一定会计算出相同的答案(例如,如果所使用的全局变量具有不同的值,或者从文件中读取的内容不同)。因此,非纯函数更难测试,更容易出错,且有更多导致失败的方式。因为这个原因(以及后面我们将会看到的其他原因),函数式编程语言强调尽可能多地使用纯函数。

但是,只使用纯函数进行编程太过局限了。在某些情况下,副作用使得某些程序更易于编写,尽管它们仍然可以只使用纯函数(痛苦地)编写。在另外一些情况下,你绝对需要副作用的能力,没有这个程序就无法编写。例如,将文件从目录结构的一部分复制到另一部分的程序必须与文件系统进行交互并进行更改;如果不允许您的函数读写文件(这是副作用),则它们将无法执行此操作。因此,即使在函数式语言中,我们也需要某种方式来进行副作用的计算。

函数式语言分为两类:纯的和非纯的。非纯函数式语言(例如 Scheme 或 Ocaml)基本上可以解决此问题:它们允许你编写具有副作用的函数,即使非纯语言的用户除非绝对必要,通常会避免这么做。纯函数式语言(例如 Haskell)则更加硬核:它们根本不允许你直接编写具有副作用的函数(你将在下面看到我为什么说“直接”)。因此,如你所想象的那样,想出一种用纯函数式语言编写副作用程序的方法是长期以来的一个主要研究课题。

Monad 成为了解决此问题的关键(更确切地说,它们只是一种关键方法;一些其他的函数式语言使用不同的方法,例如 Clean 的 uniqueness types)。Monad 使我们能够在纯函数式语言中进行我们想要的所有副作用计算,而又不破坏语言的纯度。有了 monad,我们可以使用类型系统将副作用计算与不具有副作用的计算干净利落地区分开,以使两种计算不会相互干扰。因此,我们为不产生副作用的代码(并且类型系统保证这些函数不会产生副作用)获得了函数式编程的所有好处,同时在必要时仍可以产生副作用,这是非常强大的。

Monad 还有很多其他的用途。实际上,它是一个非常通用的工具,用于以良好的方式构造各种计算,而且可以极大地简化多种不同类型的程序,而不仅仅与副作用有关。在很多情况下,monadic 的代码比等价的非 monadic 的代码要更短,更容易理解,在后面也会有一些示例。因此,monad 的用途远不止帮助我们处理函数式语言的副作用。

Monad 确实是编程语言中最令人惊叹的想法之一,非常值得学习。

内容提要:什么是 monad ?

“什么是monad?” 是一个我被问过很多次的问题。 我不想把 monad 比作某个“东西”,因为那样的信息不足,也会引起误解。 相反,我的总结是这样的:

Monad 是函数(functions),函数应用(function application)和函数复合(function composition)的泛化,以使它们能够处理比标准函数更为丰富的计算概念。

随着我们往下进行,我希望不仅能够向你解释什么是 monad,以及它们如何工作的,还可以向你解释为什么 monad 会让对它比较陌生的程序员感到非常困惑。 (提示:这不是因为他们不够聪明,也不是因为他们对范畴论不够了解)

计算概念

好,让我们从“计算概念”的含义开始,对我上面的总结进行分解。

最简单且表现最良好的“计算概念”是普通(纯)函数(即函数的数学定义)。简单起见,我只考虑将单个输入参数映射为单个输出的函数(可以通过称为 currying 的过程将多参数函数简化为单参数函数,下面我会详细说明,但就目前而言,只需要先记住这句话)。如上所述,纯函数只是一条规则,对于特定输入,它会始终生成完全相同的输出。在类似 Haskell 这样的强类型语言中,函数具有良好定义的类型签名,意味着存在类型 ab,函数将类型 a 的值映射到类型 b 的值。我们可以用 Haskell 表示如下:

f :: a -> b

其中 :: 表示“具有以下类型”。因此,函数 f 的函数类型为 a -> b,意味着它接受类型 a 的值并返回类型 b 的值。在实践中,ab 通常是特定实际类型的名称(例如 IntFloatString),但在某些情况下,无论参数的类型如何,Haskell 函数都同样可以工作。

纯函数是最简单的“计算概念”,除此之外还有什么其他的“计算概念”么?其中许多都是程序员所熟悉的,除了将输入映射到输出之外,它们还包括下面的计算,

  • 可能做文件/终端的输入/输出
  • 可能会引发异常
  • 可能会读写共享的状态(全局或局部)
  • 可能有时无法产生任何结果
  • 可能会同时产生多个结果

当然还有其他很多。注意:从现在开始,我会使用“输入/输出”(或简称为“I/O”)来指代文件或终端的输入/输出(aka. 具有副作用的输入/输出),不要和函数将输入值映射到特定输出值混淆。

认真思考一下,在 C 和 Java 之类的常规编程语言中,你会如何处理这些“其他的计算概念”?可能做 I/O ?没问题,使用 C 中的函数或 Java 中的方法都可以做 I/O 。可能引发异常?在 C 语言中有点麻烦,因为它没有内建的异常支持。你通常会做的是在发生故障的情况下返回错误代码,用它指定故障情况(或者你真的很硬核,可以使用 setjmp/longjmp)。在 Java 中你可以直接抛出一个异常就可以了(这个异常会在其他地方被捕获)。可能读写共享状态?没问题,C 和 Java 都允许你读写局部和全局变量,尽管细节部分有些不同。可能无法产生结果的?它可以看作是可以引发异常的函数的特化,因此也没有问题。可能产生多个结果?实际上,这并不是说要以单个对象的形式返回多个结果(例如在 C 结构或 Java 对象中);我的意思是可以“并行”返回多个单个结果的函数(也称为不确定性),还不清楚在 C 或 Java 中如何执行此操作。

需要注意的重点是:在每种情况下,我们处理的都不再是传统的函数概念,因为随着将输入映射到单个输出的通常函数效果,“其他的事情”也正在发生。进一步说,这些不同的计算概念代表了不同的“其他的事情”。但在我们编写程序时,通常对此不需要考虑太多,只需要知道我们正在编写的函数与函数的数学概念并不是“真正”相同的,因为它们可以执行I/O,引发异常,更改全局变量的状态等。全局变量的意外更改,异常的异常抛出,以及这些语言的非函数性的函数带来的其他问题经常会困扰着程序员们。因此,我们希望尽可能多地使用纯函数,此外在很多情况下(如同我上面提到的),我们确实不得不做一些“其他的事情”,即具有副作用的计算。

这样做的结果是:鱼和熊掌不可兼得。我们一方面希望尽可能多地用纯函数写程序,享受它带来的全部好处(易于调试和组合)。但另一方面我们也希望能够以一种受控制的方式,做那些必要的或有好处的“其他的事情”,这就是 monad 所带给我们的。

但是,上一段的关键词是“以一种受控制的方式”。 如果一切都可以按照 C 或 Java 中的方式工作,我们可以做到许多(但不是全部)非纯函数计算概念,但是我们会失去函数式编程的所有好处,因为我们将没有确保我们程序中任何函数都是纯函数(类型检查器也没办法帮我们做到)。因此,我们需要一种系统的方式来处理这些其他的计算概念,而不污染没有涉及到它们的代码(纯函数代码)。

在这时复习(纯)函数,(纯)函数应用和(纯)函数复合的基本概念是很有帮助的,因为我们可以将它们与做类似事情的 monadic 的方式进行对比。

函数,函数应用和函数复合

正如我之前所说,Haskell 中的函数使用一种特殊的符号来指定其输入和输出的类型。 对于具有输入类型 a和输出类型 b 的函数 f,其表示是:

f :: a -> b

因此,f 的类型是 a -> b(读作“a 箭头 b”或是“ab”)。 举一个更具体的例子,这里是一个将输入变为两倍的函数的定义:

f :: Int -> Int
f x = 2 * x

f 的类型是 Int -> Int,因为它接受一个整数,将其乘以 2,再返回另一个整数。

要对某个函数执行某些操作,我们必须将它应用于它的参数(假设函数是单参数的)。 通常,这可以通过简单地将函数名称与参数并置来完成:

f 2  --> 值为4

请注意 Haskell 不需要用括号将函数的参数括起来,和其他大多数计算机语言不一样。

柯里化(CURRYING)

在实践中,显然单参数函数不足以完成我们想做的许多事情。 如何定义两个参数的函数? 例如,如何定义一个接受两个整数参数并返回参数平方和的函数 q ? 很容易写出来这个函数的主体:

q x y = x * x + y * y

但是类型签名会很奇怪,你可能希望它看起来像这样:

q :: Int Int -> Int

或者这样:

q :: (Int, Int) -> Int

但实际上它是这样的:

q :: Int -> Int -> Int

-> 是右结合的,所以它实际上代表:

q :: Int -> (Int -> Int)

现在这变得更奇怪了。 在 Haskell 中,两个参数的函数(例如 q )表示为一个参数(在这个例子中是 x)的函数,该函数返回一个接受第二个参数(在这个例子中是 y)并返回结果值的单参数函数。 这是没问题的,因为在 Haskell 或者任何一种函数式语言中,将函数作为其他函数的返回值返回都是合法的(另一种说法是,在函数式语言中,函数只是另一种数据)。 这种将多个输入参数的函数表示为返回函数的单个参数的函数的方式(真绕口)称为“ 柯里化(currying)”(以逻辑学家 Haskell Curry 的名字命名,“Haskell”的名称也来自于此;这个也被一个名叫做 Schönfinkelkel 的人独立发现,如果你喜欢也可以称之为 Schönfinkeling)。 例如,具有四个参数 wxyz(都是整数),返回值为整数的函数 r 可以这样表示:

r :: Int -> Int -> Int -> Int -> Int
r w x y z = ...  -- w, x, y 和 z 的函数

因为 -> 是右结合的,所以它实际上代表:

r :: Int -> (Int -> (Int -> (Int -> Int)))
r w x y z = ...  -- w, x, y 和 z 的函数

所以在这里,r 是单个参数(一个 Int,在例子中是 w)的函数,它返回一个类型是 (Int -> (Int -> (Int -> Int))) 的函数。 这个函数应用于 Int(在例子中是 x)时,将返回一个类型是 (Int -> (Int -> Int)) 的函数。 这个函数应用于 Int 时(在例子中是 y)返回类型为 (Int -> Int) 的函数。这个函数应用于另一个 Int 时(在例子中是 z)返回一个 Int(r w x y z) 整个函数调用的结果,实际上是 ((((r w) x) y) z)。 这就是所谓的 currying,而 Haskell 中的函数会自动 curry 它的参数。 事实证明,使用currying 非常方便,因为你不需要一次应用所有参数,可以一次只应用一个参数,而这些部分应用的函数(partially-applied functions)经常会很有用。 它在概念上同样也是有用的,因为现在起我们在讨论中只需要考虑担心单参数函数,太棒了!

还有一个显式运算符 $,它是函数应用运算符,具有以下类型:

($) :: (a -> b) -> a -> b
[在Haskell中,符号中缀运算符和用括号括起来的同名函数是等效的,因此 f $ 2($) f 2 表示的含义是相同的。为了方便起见,在定义新的符号运算符时,我们用函数形式编写它们(如果想更多了解如何编写,请参见任意一篇 Haskell 入门教程,我们将在下面大量使用这个工具。]

这意味着,对于任何类型 ab,此运算符都接受一个从类型 a 转换为类型 b 的函数(它的第一个参数),将其应用于类型 a 的参数(第二个参数)并返回类型 b 的值。在函数式语言中,将函数作为参数传递给其他函数是合法的,所以这没什么问题。因此:

f 2      --> 值为 4
f $ 2    --> 值也为 4
($) f 2  --> 值也为 4

它们只是 “茴”字 f 2 的三种写法。

在函数应用中使用 $ 运算符在技术上其实是没有必要的,因为你可以通过将函数和它的参数并置来将函数应用于参数(因为 $ 涉及到运算符优先级,实际上会有一些常用的用法,但我们这里不会涉及)。 有趣的是,我们还可以定义一个类似于 $ 的“反向应用”运算符(用 >$> 表示),但它以相反的顺序接受参数:

(>$>) :: a -> (a -> b) -> b
x >$> f = f x  -- 也 = f $ x

这就有点意思了,因为我们可以把它读作“取一个值 x,将函数 f 应用于它,然后得到结果”。 如果你了解 unix,可能会注意到 unix shell 的管道(|)运算符就是以这种方式工作的——你生成了一些数据,然后对这些数据应用一个程序,来以某种方式进行转换。 任何时候,我们都可以使用对我们的目标来说更加方便的函数应用运算符,尽管通常情况下我们根本不使用运算符,而只是将它们并置。

既然我们已经讨论了函数应用,那么下一个重要的话题就是函数复合,它真的很重要。 假设我们有两个函数 fg 以及一个具有以下类型的值 x

x :: a
f :: a -> b
g :: b -> c

对于某些类型 abc。 您可能想对 xfg 做的一件事是取值 x,将其传递给函数 f(函数 f 将值 x(类型 a)转换为类型 b 的值),然后将这个值(类型 b)传递给函数 g(函数 g 将类型 b 的值转换为类型 c 的值)。 在Haskell中编写此代码的方式是:

g (f x)

注意这只在 fg 的类型兼容时才有效,即 f 的输出类型也是 g 的输入类型(这里是 b)。 从另一种不同的角度看是,我们实际上是将两个函数 fg(分别是类型 a -> bb -> c)组合为类型 a -> c 的函数,然后应用该函数到 x(类型 a)以得到类型 c 的值。 这种从两个函数生成第三个函数的想法称为函数复合,很容易定义函数复合的运算符(在 Haskell 中用 . 表示):

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

这里我们使用符号 \x -> … 表示一个单参数 xlambda 表达式(匿名函数)。 所以函数复合运算符  . 将两个函数作为参数,并返回一个函数。 同样,在函数式语言中这种函数是完全有效的,因为函数可以作为其他函数的参数或作为其他函数的返回值。

. 运算符有一个不好的地方,就是参数的排列顺序不是很显然。于是,我们可以编写一个“反向函数复合”运算符(我将表示为 >.>),如下所示:

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

我们还可以使用上面定义的 >$> 运算符将其定义为:

(>.>) :: (a -> b) -> (b -> c) -> (a -> c)
f >.> g = \x -> x >$> f >$> g

或者更简单的:

(>.>) :: (a -> b) -> (b -> c) -> (a -> c)
f >.> g = g . f

>$> 运算符具备一个可以使函数复合更加清晰的类型签名。 你可以用函数 fg 计算一个新函数(称为 h), 将 h 应用于值等价于先将 f 应用于值,然后将 g 应用于结果。 这就是函数复合的全部:一种从现有函数创建新函数的方法。

下面是一个例子:

f :: Int -> Int
f x = 2 * x

g :: Int -> Int
g y = 3 + y

h :: Int -> Int
h = g . f  -- 或者是等价的: f >.> g

这里的 h 做了什么?它接受一个整数 x,乘以 2,然后加 3。所以它也等价于:

h :: Int -> Int
h x = 3 + 2 * x

函数复合看起来没什么大不了的,但这是函数式编程的关键之一。 它使我们可以轻松地将现有的函数“绑定在一起”以形成更为复杂的函数,而不需要手动写下全部的参数。 因此,与其说实际上“h(x) 是先计算 f(x) 得到 y,再计算 g(y) 得到 z,最后再返回 z 的函数”,我们说“ h 是我们先应用 f 再应用 g 得到的函数”,不需要命名中间值使代码变得更加简洁高级。 试想如果你将十个函数一个接一个地复合在一起——如果你必须写出所有中间结果,它看起来会是这样(我们假设所有函数的类型均为 Int -> Int):

f11 x =
  let
    x2 = f1 x
    x3 = f2 x2
    x4 = f3 x3
    x5 = f4 x4
    x6 = f5 x5
    x7 = f6 x6
    x8 = f7 x7
    x9 = f8 x8
    x10 = f9 x9
    x11 = f10 x10
  in
    x11

非常冗长啰嗦是么?下面是我们使用函数复合得到的结果:

 f11 = f10 . f9 . f8 . f7 . f6 . f5 . f4 . f3 . f2 . f1

或者等价的:

f11 = f1 >.> f2 >.> f3 >.> f4 >.> f5 >.> f6 >.> f7 >.> f8 >.> f9 >.> f10

这不仅更短,而且更直观(“f11 是通过先应用 f1,再应用 f2,再应用 f3… 得到的”)。 实际上,这种使用复合方式编写函数而不指定函数作用值的方式称为“point-free 风格”(这个名字极具讽刺意味,因为 . (point) 运算符实际上在 point-free 代码中比在常规代码中用的更多——“point-free”中的“point”一词实际上意思是“参数”,也许“argument-free 风格”是一个更好的名称)。

本节应当记住的重点是:

  • 函数、函数应用和函数复合是函数式编程中的基本概念;
  • 我们可以为函数应用和函数复合编写运算符,而且它们可以按照我们想要的任意顺序接受参数。

Monadic 函数,monadic 值

目前为止,我讲的一切(但愿)都很简单。 现在,我们将讨论更复杂的内容。

[未完待续]

新增评论