什么是 Monad (Functional Programming)?

读过 en.wikipedia.org/wiki/M stackoverflow.com/quest 之后仍旧不能在头脑中建立起比较直觉化的对应模型, 也想不出除去范例中那几个之外的应用场景, 很痛苦,求解脱。
关注者
1109
被浏览
123427

23 个回答

感冒了,无所事事,脑子里莫名其妙写了一篇 monad 教程。我保证不提副作用,求各位不要批判地太厉害。

一个自函子范畴上的幺半群

程序语言中有一种常见的构造「函子」(functor)。Haskell 里的 Maybe 是个很好的例子:

data Maybe a = Just a | Nothing

Maybe 之所以是函子,是因为它可以通过 fmap(functor map)把所有的函数拎到「Maybe 空间」里。换而言之,令 f :: a -> b,fmap f :: Maybe a -> Maybe b。fmap 定义如下:

fmap :: (a -> b) -> (Maybe a -> Maybe b)
fmap f mbx = case mbx of
  Just x  -> Just (f x)
  Nothing -> Nothing

Maybe 可以方便地用来做错误处理。对于那些不支持 Maybe 作输入的函数,我们也可以通过 fmap 兼容之。但是,组合多个会产生 Maybe 的函数很麻烦。比如说这个除法函数:

safeDiv :: Int -> Int -> Maybe Int
  safeDiv _ 0 = Nothing
  safeDiv x y = Just (x / y)

考虑一下表达式:

case safeDiv a b of
  Nothing -> Nothing
  Just x  -> case safeDiv c x of
    Nothing -> Nothing
    Just y  -> case safeDiv d y of
      Nothing -> Nothing
      Just z  -> safeDiv e z

在 JavaScript 界,我们管这样的代码叫「callback hell」。不过这段代码总比下面这段好:

let x = safeDiv a b
    y = fmap (safeDiv c) x
    z = (fmap . fmap) (safeDiv d) y
    in (fmap . fmap . fmap) (safeDiv e) z

请读者计算此表达式的类型。(答案:Maybe (Maybe (Maybe (Maybe Int))))不管你喜不喜欢,我是要把中午吃的炒饭给吐出来了。所幸的是,连续两个 Maybe 可以被压缩成一个:

join :: Maybe (Maybe a) -> Maybe a
  join (Just x) = x
  join Nothing  = Nothing

(请读者思考为什么不可以写一个 Maybe a -> a 的函数)

Haskell 标准库里,有一个功能一样的运算符 >>=,定义如下:

(>>=) :: Maybe a -> (a -> Maybe b) -> Maybe b
  (>>=) mbx f = join (fmap f mbx)

(请读者用 >>= 来定义 join)

有了 >>=,我们可以把上面的表达式重写为:

safeDiv a b >>= (\x ->
safeDiv c x >>= (\y ->
safeDiv d y >>= (\z ->
  safeDiv e z)))

新的表达式的类型为 Maybe Int,清爽太多。Haskell 甚至提供了一种语法糖,即 do:

val = do
  x <- safeDiv a b
  y <- safeDiv c x
  z <- safeDiv d y
  safeDiv e z

这样一来,问题就解决了。

Haskell 相关

上面的 >>= 和 do,就是传说中的「单子」(monad)。Monad 是一个类型类(type class)。Monad 继承自 Applicative,后者继承自 Functor。也就是说,实现 Monad 之前,该类型必须先实现 Functor 和 Applicative。以下为类型类定义:

class Functor f where
  fmap :: (a -> b) -> (f a -> f b)
  
 -- | A useful operator
 <$> = fmap
 
class Functor f => Applicative f where
  -- | Lift a value.
  pure :: a -> f a

  -- | Sequential application.
  (<*>) :: f (a -> b) -> (f a -> f b)
  
 class Applicative m => Monad m where
  -- | Sequentially compose two actions, passing any value produced
  -- by the first as an argument to the second.
  (>>=) :: m a -> (a -> m b) -> m b

注意事项:

  • Haskell 的「$」运算符可以去掉很多括号,比如说 f (x + y) 可以写成 f $ x + y。「<$>」原理一致,即 fmap f (x + y) 与 f <$> x + y 等价。
  • 实现 Functor 的类型 f 只可以把一元函数 a -> b 拎为 f a -> f b。Applicative 可以拎任意元函数。令 x :: Maybe Int,y :: Maybe Int,二者相加可以写为 (+) <$> x <*> y,返回的是 Maybe Int。读者应自行检查多元情况,并尝试给出 <*> 的定义。
  • pure 则是将类型 t 的值拎到 f t。对于 Maybe,pure = Just。
  • Monad 类的 >>= 在本文第一部分已讨论完毕。

请读者自行谷歌其他 monad 教程来学习使用常用单子,如 Reader、Writer、State、List、Either、Cont。先理解它们作为函子的用法。

注意:感谢 @swordfeng 指出,我对 IO 单子的理解有误,故而删去原有描述。这不影响上文对单子通用结构的讨论。

Haskell 的惰性求值特性使求值顺序很难确定,而 IO 操作需要确定的顺序。因此,Haskell 需要标出所有有副作用的代码,并确保这些代码的顺序。

想标记有副作用的代码很简单,我们可以使用 IO a 来表示所有有副作用的类型 a 的值;只要不提供 IO a -> a,有副作用的值便无法擦去它身上的 IO 印记——除非使用 unsafePerformIO :: IO a -> a,顾名思义,一个不安全的函数。

另一方面,单子结构确定了函数结合的顺序。先考虑 Applicative 类型类。令 randomInteger :: IO Int 为一个随机生成整数的函数。因为任意一个 N 元函数都可以看成一个副作用为零的 IO 操作,IO 是一个自然的函子,也是一个自然的 Applicative。所以,如果我们想求两个随机数之和,可以写:

randomSum = (+) <$> randomInteger <*> randomInteger

由于加法满足交换律,这两个 randomInteger 的求值顺序可以随意调换,而 Applicative 的接口提供了这一自由。毕竟Applicative 是对多元函数调用的一个模仿,而纯函数的参数的计算顺序不重要。

单子结构恰恰相反,考虑:

randomSum = do
  x <- randomInteger
  y <- randomInteger
  pure (x + y)

如上所述,do 只是一个语法糖,使用 >>= 重新实现上述代码:

randomSum = randomInteger >>= (\x ->
            randomInteger >>= (\y ->
            pure (x + y)))

很显然,不计算第一个 randomInteger,我们没有办法计算第一个闭包(closure,lambda 表达式)的值,也就没有办法计算第二个 randomInteger,也就没有办法计算 pure (x + y)。所以,单子很适合对有副作用的代码进行建模,最后成为 Haskell 处理 IO 的标准解法。对 IO 单子背后的具体机制感兴趣的读者,可以先熟悉 State 单子,再去阅读相关资料。

数学相关

标题是对 Mac Lane 的著名作品、范畴论最早的参考书《Categories for the Working Mathematician》的引用。在恶搞文章 A Brief, Incomplete, and Mostly Wrong History of Programming Languages 里,作者假以 Philip Wadler 之名说出此话(或许后者真的在哪篇论文里引用过,我不确定,得问 @Canto Ostinato)。

我本试图用不严谨的语言解释一下这句话的数学含义,可感觉画蛇添足。Haskell 不推导类型学不好,数学不写证明也学不好。感兴趣的读者可自行阅读相关范畴论材料。对于没有数学背景的读者,我建议:

  1. 学习抽象代数。有这么几个好处:一、给范畴论提供许多例子;二、锻炼书写证明的能力;三、可重新理解许多常用工具,如线性代数。一般来说,学一点基础的群论、环论(可约性)、模就够了。
  2. 学习代数拓扑。代数拓扑是范畴论的发源地。人们发现,空间,比如说球面或者甜甜圈表面上的环和群存在关联。举个例子,绕着一个圆环的首尾相连的路径,可以根据绕圆环的圈数进行分类,后者与整数集同构。这就是一个由拓扑空间范畴到群范畴上的函子。这些函子可比 Maybe 有趣的多。
  3. 教材上,新教材用范畴论的语言比较多,代数我推荐 Algebra: Chapter 0。拓扑有一本标准教材,Hatcher 的 Algebraic Topology。
  4. 最后,不要学同调代数!不要学同调代数!不要学同调代数!
两篇paper就够了,先看Philip Wadler的Monads for functional programming,这篇更详细,然后看他的The essence of functional programming,后者提到了Monad和CPS之间的关系。

然后你还得写。。写几个用Monad的parser/interpreter就熟悉了。

Wadler的文章当然比网上满天飞的Monad教程靠谱得多。。话说我上Erik Meijer的Haskell公开课时,Functional parser那一节做练习前要签的EULA就是“我保证,不再在网上又发布一篇Monad教程”23333
为什么?