完整解释 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.of = value => Effect(() => value);

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

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

Effect(impureAddOne)
  .map(impureMultiplyByTwo)
  .runWith(2); // => add one!multiply by two! 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);

xFromWindowyFromWindow 返回的都是一个 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).runWith(); // => 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)

5. Monad (!!!)

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

// DOM 读取和控制台打印的行为放进 Effect
const $ = s => Effect(() => document.querySelector(s));
const log = s => Effect(() => console.log(s));

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

勉强能做到,但是这样子先 maprunWith 实在太繁琐了,我们可以再给 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(),
});

然后这样组合:

Effect.of(window)
  .map(win => win.userEl)
  .chain($)
  .map(e => e.innerHTML)
  .chain(log)
  .runWith();

线上 Demo 见这里

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.runWith(ctx)));

  const chain = f => {
    return Reader(ctx => {
      const a = computation(ctx);
      return f(a).runWith(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('张三');
// => 你好, 张三...再见, 张三

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

在学习 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 => State.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}

范畴论介绍

范畴论部分写的太烂就删除了,目前还没精力修正。以后再填这个坑吧。


参考: