完整解释 Monad -- 程序员范畴论入门

如果你接触过函数式编程，你很可能遇到过 Monad 这个奇怪的名词。由于各种神奇的原因，Monad 成了一个很难懂的概念。Douglas Crockford 曾转述过这样一句话来形容 Monad:

Once you understand Monad, you lose the ability to explain it to someone else.

这篇文章中，我会从使用场景出发来一步步推演出 Monad。然后，我会进一步展示一些 Monad 的使用场景，并解释一些我从 Haskell 翻译成 JS 的 ADT (Algebraic Data Type)。最后，我会介绍 Monad 在范畴论中的意义，并简单介绍下范畴论。

函数组合

1. Monoid

假设你被一个奇怪的丛林部落抓住了，部落长老知道你是程序员，要你写个应用，写出来就放你走。作为一个资深码农，你暗自窃喜，心里想着老夫经历了这么多年产品经理各种变态需求的千锤百炼，没什么需求能难倒我！长老似乎看出了你的心思，加了一个要求：这个应用只能用纯函数写，不能有状态机，不能有副作用！然后你崩溃了……

再假设你不知道函数式编程，但你足够聪明，你可能会发明出一个函数来满足这个奇葩的要求。这个函数如此强大，你可能会叫它超级函数，但其实它无可避免就是一个 Monad。

接下来我们就来一步步推演出这个超级函数吧。

函数组合大家都应该非常熟悉。比如，Redux 里面在组合中间件的时候会用到一个 compose 函数 compose(middleware1, middleware2) 。函数组合的意思就是，在若干个函数中，依顺序把前一个函数执行的结果传个下一个函数，逐次执行完。 compose 函数的简单实现如下：

const compose = (...fns) => fns.reduce((f, g) => (...args) => f(g(...args)))
复制代码

函数组合是个很强大的思想。我们可以利用它把复杂问题拆解成简单问题，把这些简单问题逐个解决了之后，再把这些解决方案组合起来，就形成了最终的解决方案。

这里偷个懒再举一下我之前文章的例子吧：

// 在产品列表中找到相应产品，提取出价格，再把价格格式化
const formalizeData = compose(formatCurrency, pluckPrice, findProduct);

formalizeData(products)
复制代码

如果你理解了上面的代码，那么恭喜你，你已经懂了 Monoid!

所谓 Monoid 可以简单定义如下：

• 它是一个集合 S
• S 的元素之间有一个二元运算 x，运算的结果也属于 S：S a x S b --> S c
• 存在一个特殊元素 e，使得 S 中的任意元素与 e 运算，都返回此元素本身：S e x S m --> S m

同时，这个二元运算要满足这些条件：

• 结合律：(a x b) x c = a x (b x c), a，b，c 为 S 中元素
• 单元律：e x a = a x e = a，e 为特殊元素，a 为 S 中任意元素

注意，上面这个定义是集合论中的定义，这里还没涉及到范畴论。

函数要能组合，类型签名必须一致。如果前一个函数返回一个数字，后一个函数接受的是字符串，那么是没办法组合的。所以， compose 函数接受的函数都符合如下函数签名：fn :: a -> a 也就是说函数接受的参数和返回的值类型一样。满足这些类型签名的函数就组成了 Monoid，而这个 Monoid 中的特殊元素就是 identity 函数： const identity = x => x; 结合律和单元律的证明比较简单，我就不演示了。

2. Functor

上面演示的函数组合看起来很舒服，但是实际用处还不是很大。因为 compose 接受的函数都是纯函数，只适合用来计算。而现实世界没有那么纯洁，我们要处理 IO，逻辑分支，异常捕获，状态管理等等。单靠简单的纯函数组合是不行的。

先假设我们有两个纯函数：

const addOne = x => x + 1
const multiplyByTwo = x => 2 * x
复制代码

理想状态下是我们可以组合这两个函数：

compose(
  addOne,
  multiplyByTwo
)(2) // => 5
复制代码

但是我们出于各种原因要执行一些副作用。这里仅为了演示，就简单化了。假设上面两个函数在返回值之前还向控制台打印了内容：

const impureAddOne = x => {
  console.log('add one!')
  return x + 1
}

const impureMultiplyByTwo = x => {
  console.log('multiply by two!')
  return 2 * x
}
复制代码

现在这两个函数不再纯洁了，我们看不顺眼了。怎样让他们恢复纯洁？很简单，作弊偷个懒：

const lazyImpureAddOne = x => () => {
  console.log('add one!')
  return x + 1
}

// Java 代码看多了之后我也学会取长变量名了^_^
const lazyImpureMultiplyByTwo = x => () => {
  console.log('multiply by two!')
  return 2 * x
}
复制代码

修改之后的函数，提供同样的参数，每次执行他们都返回同样的函数，可以做到引用透明。这就叫纯洁啊！

然后我们可以这样组合这两个偷懒函数：

composeImpure = (f, g) => x => () => f(g(x)())()

const computation = composeImpure(lazyImpureAddOne, lazyImpureMultiplyByTwo)(8)

computation() // => 'multiply by two!''add one!' 17
复制代码

在执行 computation 之前，我们都在写纯函数。

我知道，我知道，上面的写法可读性很差。这样子写也不可维护。我们来写个 工具 函数方便我们组合这些不纯洁的函数：

const Effect = f => ({
  map: g => Effect(x => g(f(x))),
  runWith: x => f(x),
})
复制代码

这个 Effect 函数接受一个非纯函数 f 为参数，返回一个对象。这个对象里面的 map 方法把自身接受的非纯回调函数 g 和 Effect 的非纯回调函数组合后，将结果再塞回给 Effect 。由于 map 返回的也是对象，我们需要一个方法把最终的计算结果取出来，这就是 runWith 的作用。

用 Effect 重现我们上一步的计算如下：

Effect(impureAddOne)
  .map(impureMultiplyByTwo)
  .runWith(2) // => 'multiply by two!''add one!' 6
复制代码

现在我们就可以直接用非纯函数了，不用再用那么难读的函数调用了。在执行 runWith 之前，程序都是纯的，任你怎么组合和 map 。

如果你懂了上面的代码，那么恭喜你，你已经懂了 Functor！

同样，Functor 还要满足一些条件：

• 单元律：a.map(x => x) === a
• 保存原有数据结构（可组合）：a.map(x => f(g(x))) === a.map(g).map(f)
• 提供接口往里面塞值：Effect.of = value => Effect(() => value)

你可以把 Functor 理解成一个映射函数，它把一个类型里的值映射到同一个类型的其它值。比如数组操作 [1, 2, 3].map(String) // -> ['1', '2', '3'], 映射之后数据类型一样（还是数组），内部结构不变。我在之前的文章中说数组就是个 Functor，这种表述是有误的，应该是说数组满足 Functor 的返回值条件。

3. Applicative

上面的 Effect 函数把非纯操作都放进了一个容器里面，这样子做了之后，如果要对两个独立非纯操作的结果进行运算，就会很麻烦。

比如，我们在 window 全局读取两个值 x, y, 并将读取结果求和。我知道这个例子很简单，不用函数式编程很容易做到，我只是在举简单例子方便理解。

假设 window 对象已经存在两个值 {x: 1, y: 2, ...otherProps}。我们这样取：

const win = Effect.of(window)

const xFromWindow = win.map(g => g.x)

const yFromWindow = win.map(g => g.y)
复制代码

xFromWindow 和 yFromWindow 返回的都是一个 Effect 容器，我们需要给这个容器新添加一个方法，以便将两个容器里层的值进行计算。

const Effect = f => ({
  map: g => Effect(x => g(f(x))),
  runWith: x => f(x),
  ap: other => Effect(x => other.map(f(x)).runWith()),
})
复制代码

然后，我们提供一个相加函数 add：

const add = x => y => x + y
复制代码

接下来借助这个 ap 函数，我们可以进行计算了：

xFromWindow
  .map(add)
  .ap(yFromWindow)
  .runWith() // => 3
复制代码

由于这种先 map 再 ap 的操作很普遍，我们可以抽象出一个工具函数 liftA2：

const liftA2 = (f, m1, m2) => m1.map(f).ap(m2)
复制代码

然后可以简化点写了：

liftA2(add, xFromWindow, yFromWindow) // => 3;
复制代码

注意运算函数必须是柯里化函数。

新增 ap 方法之后的 Effect 函数除了是 Functor，还是 Applicative Functor。这部分完全看代码还不是很好懂。如果你不理解上面的代码，没有关系，它并不影响你理解 Monad。另外，不用纠结于本文代码里的具体实现。不同的 Applicative 的 ap 方法实现都不一样，可以多看几个。Applicative 是介于 Functor 和 Monad 之间的数据类型，不提它就不完整了。

Applicative 要满足下面这些条件：

• Identity: A.of(x => x).ap(v) === v
• Homomorphism: A.of(f).ap(A.of(x)) === A.of(f(x))
• Interchange: u.ap(A.of(y)) === A.of(f => f(y)).ap(u)

Monad (!!!)

假设我们要从 window 全局读取配置信息，此配置信息提供目标 DOM 节点的类名 userEl ；根据这个类名，我们定位到 DOM 节点，取出内容，然后打印到控制台。啊，读取全局对象，读取 DOM，控制台输出，全是作用，好可怕…… 我们先用之前定义的 Effect 试试看行不行：

// DOM 读取的行为放进 Effect
const $ = s => Effect(() => document.querySelector(s))

Effect.of(window)
  .map(win => win.userEl)
  .map($)
  .runWith() //由于上一个 map 里层也返回了 Effect，这里需要抹平一层
  .map(e => console.log(e.innerHTML))
  .runWith()
复制代码

勉强能做到，但是这样子先 map 再 runWith 实在太繁琐了，我们可以再给 Effect 新增一个方法 chain:

const Effect = f => ({
  map: g => Effect(x => g(f(x))),
  runWith: x => f(x),
  ap: other => Effect(x => other.map(f(x)).runWith()),
  chain: g =>
    Effect(f)
      .map(g)
      .runWith(),
})
复制代码

Voila! 我们发现了 Monad！

在写上面的代码的时候我还是觉得逐行解释代码比较繁琐。我们先不管代码具体实现，从函数签名开始看 Monad 是怎么回事。

让我们回到 Monoid。我们知道函数组合的前提条件是类型签名一致。fn :: a -> a. 但在写应用时，我们会让函数除了返回值之外还干其他事。这里不管具体干了哪些事，我们可以把这些行为扔到一个黑盒子里（比如刚刚写的 Effect），然后函数签名就成了 fn :: a -> m a。m 指的是黑盒子的类型，m a 意思是黑盒子里的 a. 这样操作之后，Monoid 接口不再满足，函数不能简单组合。

但我们还是要组合。

其实很简单，在组合之前把黑盒子里的值提升一层就行了。最终我们实现的组合其实是这样：fn :: m a -> (a -> m b) -> m b. 这个签名里，函数 fn 接受黑盒子里的 a 为参数，再接受一个函数为参数，这个函数的入参类型是 a，返回类型是黑盒子里的 b。最终，外层函数返回的类型是黑盒子里的 b。这个就是 chain 函数的类型签名。

fn :: a -> m a 签名里面的箭头叫 Kleisli Arrow，其实就是一种特殊的函数。Kleisli 箭头的组合叫 Kleisli Composition，这也是 Ramda 里面 composeK 函数的来源。这里先了解一下，等下还会用到这个概念。

Monad 要满足的一些定律如下：

• Left identity: M.of(a).chain(f) === f(a)
• Right identity: m.chain(M.of) === m
• Associativity: m.chain(f).chain(g) === m.chain(x => f(x).chain(g))

很多人误解 JS 里面的 Promise 就是个 Monad，我之前也有这样的误解，但后来想明白了。按照上面的定律来看检查 Promise：

Left identity：

Promise.resolve(a).then(f) === f(a)
复制代码

看起来满足。但是如果 a 是个 Promise 呢？要处理 Promise，那 f 应该符合符合这个函数的类型签名:

const f = p => p.then(n => n * 2)
复制代码

来试一下：

const a = Promise.resolve(1)
const output = Promise.resolve(a).then(f)
// output :: RejectedPromise TypeError: p.then is not a function
复制代码

报错的原因是，a 在传给 f 之前，就已经被 resolve 掉了。

Right identity：

p.then(x => Promise.resolve(x)) === p
复制代码

满足。

Associativity:

p.then(f).then(g) === p.then(x => f(x).then(g))
复制代码

和左单元律一样，只有当 f 和 g 接受的参数不为 Promise，上面才成立。

所以，Monad 的三个条件，Promise 只符合一条。

更多 ADT

上面演示的 Effect 函数，和我之前文章 《不完整解释 Monad 有什么用》 里面演示的 IO 函数是同一个 ADT，它是用来处理程序中的作用的。函数式编程中还有很多不同用处的 ADT，比如，处理异步的 Future，处理状态管理的 State，处理依赖注入的 Reader 等。关于为什么这个 Monad 是代数数据类型，Monad 和大家熟知的代数有什么关系，这里不展开了，有兴趣进一步了解的话可以参考 Category Theory for Programmers 这本书。

这里再展示两个 ADT，Reader 和 State，比较它们 chain 和 ap 的不同实现，对比 Monadic bind 函数类型签名 chain :: m a -> (a -> m b) -> m b，思考下它们是怎样实现 Monad 的。

1. Reader

const Reader = computation => {
  const map = f => Reader(ctx => f(computation(ctx)))

  const contramap = f => Reader(ctx => computation(f(ctx)))

  const ap = other => Reader(ctx => computation(ctx)(other.runReader(ctx)))

  const chain = f => {
    return Reader(ctx => {
      const a = computation(ctx)
      return f(a).runReader(ctx)
    })
  }

  const runWith = computation

  return Object.freeze({
    map,
    contramap,
    ap,
    chain,
    runWith,
  })
}

Reader.of = x => Reader(() => x)
复制代码

题外话补充下，上面这种叫“冰冻工厂”的工厂函数写法，是我个人偏好。这样写会有一定性能和内存消耗问题。用 Class 性能更好，看你选择。

程序中可能会遇到某个函数对外部环境有依赖。用纯函数的写法，我们可以把这个依赖同时传进函数。这样子，函数签名就是 fn :: (a, e) -> b。e 代表外部环境。这个签名不符合我们前面提到的 a -> m b. 我们到现在还只提到了一次函数柯里化，这个时候再一次要用柯里化了。柯里化后，有依赖的函数类型签名是 fn :: a -> (e, b), 你可能认出来了，中间那个箭头就是 Kleisli Arrow。

假设我们有一段程序的多个模块依赖了共同的外部环境。要做到引用透明，我们必须把这个环境传进函数。但是每一个模块如果都接受外部环境为多余参数，那这些模块是没办法组合的。Reader 帮我们解决这个问题。

来写个简单程序，执行这个程序时输出“你好，xx ... 再见，xx”。xx 由执行时的参数决定。

const concat = x => y => y.concat.call(y, x)

const greet = greeting => Reader(name => `${greeting}, ${name}`)

const addFarewell = farewell => str =>
  Reader(name => `${str}${farewell}, ${name}`)

const buildSentence = greet('你好')
  .map(concat('...'))
  .chain(addFarewell('再见'))

buildSentence.runWith('张三')
// => 你好, 张三...再见, 张三
复制代码

上面这个例子过于简单。输出一个字符串用一个函数就行，用不了解构和组合。但是，我们可以很容易扩展想象，如果 greet 和 addFarewell 是很复杂的模块，必须拆分，此时组合的价值就出现了。

在学习 Reader 时，我发现一篇很不错的文章。这篇文章大开脑洞，用 Reader 实现 React 里面的 Context。有兴趣可以了解下。 The Reader monad and read-only context

2. State

// 这个写法你可能不习惯。
// 这是 K Combinator，Ramda 里面对应函数是 always, Haskell 里面是 const
const K = x => y => x

const State = computation => {
  const map = f =>
    State(state => {
      const prev = computation(state)
      return { value: f(prev.value), state: prev.state }
    })

  const ap = other =>
    State(state => {
      const prev = computation(state)
      const fn = prev.value
      return other.map(fn).runWith(prev.state)
    })

  const chain = fn =>
    State(state => {
      const prev = computation(state)
      const next = fn(prev.value)
      return next.runWith(prev.state)
    })

  const runWith = computation

  const evalWith = initState => computation(initState).value

  const execWith = initState => computation(initState).state

  return Object.freeze({
    map,
    ap,
    chain,
    evalWith,
    runWith,
    execWith,
  })
}

const modify = f => State(state => ({ value: undefined, state: f(state) }))

State.get = (f = x => x) => State(state => ({ value: f(state), state }))

State.modify = modify

State.put = state => modify(K(state))

State.of = value => State(state => ({ value, state }))
复制代码

State 里层最终返回的值由对象构成，对象里面包含了此时计算结果，以及当前的应用状态。

再举个简单的例子。假设我们根据某状态数字进行计算，首先我们在这个初始状态上加某个数字，然后我们把状态 + 1, 再把新的状态和前一步的计算相乘，算出最终结果。同样，例子很简单，但已经包含了状态管理的核心。来看代码：

const add = x => y => x + y

const inc = add(1)

const addBy = n => State.get(add(n))

const multiplyBy = a => State.get(b => b * a)

const incState = n => modify(inc).map(K(n))

addBy(10)
  .chain(incState)
  .chain(multiplyBy)
  .runWith(2) // => {value: 36, state: 3}
复制代码

上面最后一步组合，每个函数类型签名一致，a -> m b, 构成 kleisli 组合，我们还可以用工具函数改进一下写法：

const composeK = (...fns) =>
  fns.reduce((f, g) => (...args) => g(...args).chain(f))

const calculate = composeK(
  multiplyBy,
  incState,
  addBy
)

calculate(10).runWith(2) // => {value: 36, state: 3}
复制代码

范畴论介绍

Monad 有一个“臭名昭著”的定义，是这样：

A monad is just a monoid in the category of endofunctors, what's the problem?

我见过这句话的中文翻译。但是这种“鬼话”不管翻不翻译都差不多的表达效果，我觉得还是不用翻译了。很多人看到这句话不去查出处和上下文，就以此为据来批评 FP 社区故弄玄虚，我感到很无奈。

这句话出自这篇文章 Brief, Incomplete and Mostly Wrong History of Programming Languages . 这篇文章用戏谑调侃的方式把所有主流编程语言黑了一个遍。上面那句话是用来黑 Haskell 的。本来是句玩笑，结果就以讹传讹了。

上面那句话的原始出处是范畴论的奠基之作 Categories for the Working Mathematician, one of the foundational texts of Category Theory 原话更拗口：

All told, a monad in X is just a monoid in the category of endofunctors of X, with product × replaced by composition of endofunctors and unit set by the identity endofunctor.

注意书名，那是给数学家看的，不是给 程序员 看的。你看不懂很正常，看不懂还要骂这些学术泰斗装逼就是你的不对了。

范畴论背景

首先，说明下我数学学得差，我接下来要讲的名词我知道是在研究什么，再深入细节我就不知道了。

大家知道数学有很多分支，比如集合论，逻辑学，类型论(有这个吗？Type Theory) 等等。后来，有些数学家发现，如果用足够抽象的概念工具去考察这些分支，其实他们都在讲同样的东西。桥接这些概念的工具是 isomorphism (同构)。isomorphic 就是在对象之间可以来回转换，每次转换没有信息丢失。比如，在逻辑学里面研究的某个问题，可能和类型论里面研究是同一个问题，只要两者之间能形成 isomorphism。

再后来，FP 祖师爷之一 Haskell Curry，和另一个数学家一起发现了 Curry–Howard Isomorphism。这个理论证明了 proofs as programs, 就是说写电脑程序（当然是函数式）和写逻辑证明是一回事，两者形成同构。再后来，这个理论被扩展了一下，成了 Curry–Howard-Lambek Isomorphism, 就是说逻辑学，程序函数，和范畴论，三者之间形成同构。

看了上面的理论背景，你应该明白了为什么函数式编程要从范畴论里面获取理论资源。

什么是范畴 (Category)

范畴其实是很简单的一个概念。范畴由一堆（这个量词好难翻译，我见过 a bunch, a collection, 但是不能说 a set）对象，以及对象之间的关系构成。我分两部分介绍。

对象 (Object): 范畴论里面的对象和编程里面的对象是两回事。范畴中的对象没有属性，没有结构，你可以把它理解为不可描述的点。

箭头 (arrow, morphism, 两个词说的是同一个东西, 我后面就用箭头了): 连接对象，表示对象之间的关系。同样，箭头也是一个没有结构没有属性的一种 primitive。它只说明了对象之间存在关系，并不能说明是什么关系。

对象和箭头要构成一个范畴，还要满足这两个条件：

• 单元律。每个对象至少有一个箭头能从自己出发回到自身。
• 结合律。如果对象 a 和 b 之间存在箭头 f，对象 b 和 c 之间存在箭头 g，则必然存在箭头 h 由 a 到 c，h 就是 f 和 g 的组合。

可以看出范畴论的起点真的非常简单。很难想象基于这么简单的概念能构建出一个完整的数学理论。

我一开始试着在范畴论中来解释 Monad，以失败告终。要介绍的拗口名词太多了，一篇文章根本讲不完。所以本文会折中一下，还是用集合论的视角来解释一下范畴论概念。（范畴论的单个对象可以对应成一个集合，但是范畴论禁止谈论集合元素，所有关于对象的知识都由箭头和组合推理出来，所以很头疼。）

还记得我们是用集合来定义 Monoid 的吧？Monoid 其实就是一个只有一个对象的范畴。对象和对象之间的映射叫 Functor。如果一个 Functor 把对象映射回自身，那么这个 Functor 就叫 Endofunctor。Functor 和 Functor 之间的映射叫 Natural Transformation. 函数式编程其实只处理一个对象，就是数据类型（Types）。所以，我们前面提到的 Functor 也是 Endofunctor。

回到前面 Monad 中 chain 的类型签名：

chain :: m a -> (a -> m b) -> m b

可以看出 Monad 是把一个类型映射回自身（m a -> m b），那么它就是一个 Endofunctor。

再看看 Monad 中所运用的 Natural Transformation。还是看 chain 的签名，前半部分 m a -> (a -> m b) 执行之后，类型签名是 m (m b), 然后再和后面的连起来，就是 m (m b) -> m b. 这其实就是把一个 functor (m (m b)) 映射到另一个 Functor (m b)。m (m b) -> m b 看起来是不是很眼熟？一个 Functor 和自己组合，形成同一个范畴里的 Functor，这就是 Monoid 啊！我们一开始定义的 Monoid 中的二元运算，在 Monad 中其实就是 Natural Transformation。

那么，再回到这一部分开始时的定义：

A monad is just a monoid in the category of endofunctors.

有没有好理解一点？

为什么要这样写程序

这篇文章的目的不是鼓励你在你的代码中消灭状态机，消灭副作用，我自己都做不到的。我司后端是用 Java 写的，如果我告诉后端同事 “Yo，你的程序里不能出现状态机哦……”，怕是会被哄出办公室的。那么，为什么要了解这些知识？

计算机科学中有两条截然相反的路径。一条是自下而上，从底层指令开始往上抽象（优先考虑性能），逐渐靠近数学。比如，一开始的 Unix 操作系统是用汇编写的，后来发现用汇编写程序太痛苦了，需要一些抽象，所以出现了高级语言 C，再后来由于各种编写应用的需求，出现了更高级的语言如 Python 和 JavaScript。另一条路径是自上而下的，直接从数学开始（Lambda 演算），不考虑性能和硬件状况，按需逐渐减少抽象。前一条路径明显占了主流，代表语言是 Fortran, C, C++, Pascal, 和 Java 等。后面一条路径不够实用，比较小众，代表语言是 Algo, LISP, Small Talk 和 Haskell 等。

这两个阵营肯定是由争论的。前者想劝后者从良：你别扔给我这么多函数，我没法不影响性能情况下处理那么多垃圾回收和函数调用！后者也想叫醒前者：不要过早深入硬件细节，你会把自己锁定在无法逆转的设计错误上！两者分道扬镳了 60 多年，这些年总算开始融合了。比如，新出现的程序语言如 Scala，Kotlin，甚至系统编程语言 Rust，都大量借鉴了函数式编程的思想。

学些高阶抽象还能帮助你更容易理解一些看起来很复杂的概念。转述一个例子。C++ 编程里面最高的抽象是模板元编程(Template Meta Programming)，据说很难懂。但是据 Bartosz Milewski 的解释，之所以这个概念难懂，是因为 C++ 的语言设计不适合表达这些抽象。如果你会 Haskell，就会发现其实一行代码就完成了。

参考:

• 1. Brian Beckman: Don't fear the Monad
• 2. What Does Haskell Have to Do with C++?
• 3. HOW TO DEAL WITH DIRTY SIDE EFFECTS IN YOUR PURE FUNCTIONAL JAVASCRIPT
• 4. Category Theory for Programmers