Monad 模式

Question

Monad 不就是个自函子范畴上的幺半群，这有什么难理解的（A monad is just a monoid in the category of endofunctors）
—— Phillip Wadler

自函子 Endofunctor

什么是函数（Function）？

函数表达的映射关系在类型上体现在特定类型（proper type）之间的映射。

什么是自函数（Endofunction）？

identity :: Number -> Number

自函数就是把类型映射到自身类型。函数 identity 是一个自函数的特例，它接收什么参数就返回什么参数，所以入参和返回值不仅类型一致，而且值也相同。

接下来，回答什么是自函子（Endofunctor）之前，我们先弄清什么是函子（Functor）？

函子有别于函数，函数描述的是特定类型（proper type）之间的映射，而函子描述的是范畴（category）之间的映射。

那什么是范畴（category）？

我们把范畴看做一组类型及其关系态射（morphism）的集合。包括特定类型及其态射，比如 Int、String、Int -> String ；高阶类型及其态射，比如 List[Int]、List[String]、List[Int] -> List[String] 。

接下来看看函子是如何映射两个范畴的，范畴 C1 和范畴 C2 之间有映射关系，C1 中 Int 映射到 C2 中的 List[Int]，C1 中 String 映射到 C2 中的 List[String]。除此之外，C1 中的关系态射 Int -> String 也映射到 C2 中的关系 List[Int] -> List[String] 态射上。

换句话说，如果一个范畴内部的所有元素可以映射为另一个范畴的元素，且元素间的关系也可以映射为另一个范畴元素间关系，则认为这两个范畴之间存在映射。所谓函子就是表示两个范畴的映射。

澄清了函子的含义，那么如何在程序中表达它？

在 Haskell 中，函子是在其上可以 map over 的东西。稍微有一点函数式编程经验，一定会想到数组（Array)或者列表（List），确实如此。不过，在我们的例子中，List 并不是一个具体的类型，而是一个类型构造子。举个例子，构造 List[Int]，也就是把 Int 提升到 List[Int]，记作 Int -> List[Int] 。这表达了 一个范畴的元素可以映射为另一个范畴的元素。

List 具有 map 方法，不妨看看 map 的定义：

f :: A -> B
map :: f -> List[A] -> List[B]

具体到我们的例子当中，就有：

f :: Int -> String
map :: f -> List[Int] -> List[String]

展开来看：

map :: Int -> String -> List[Int] -> List[String]

map 的定义清晰地告诉我们： Int -> String 这种关系可以映射为 List[Int] -> List[String] 这种关系。这就表达了 元素间的关系也可以映射为另一个范畴元素间关系。

所以类型构造器 List[T]就是一个函子。

理解了函子的概念，接着继续探究什么是自函子。我们已经知道 自函数就是把类型映射到自身类型 ，那么自函子就是把范畴映射到自身范畴。

自函子是如何映射范畴的，一个将范畴映射到自身的自函子，而且还是一个特殊的 Identity 自函子。为什么这么说？从函子的定义出发，我们考察这个自函子，始终有 List[Int] -> List[Int] 以及 List[Int] -> List[String] -> List[Int] -> List[String] 这两种映射。

我们表述成：

类型 List[Int]映射到自己
态射 f :: List[Int] -> List[String]映射到自己

我们记作：

F(List[Int]) = List[Int]
F(f) = f
其中，F 是 Functor.

除了 Identity 的自函子，还有其它的自函子，省略号代表这些范畴可以无限地延伸下去。我们在这个大范畴所做的所有映射操作都是同一范畴内的映射，自然这样的范畴就是一个自函子的范畴。

我们记作：

List[Int] -> List[List[Int]]
List[Int] -> List[String] -> List[List[Int]] -> List[List[String]]
...

所以 List[Int]、List[List[Int]]、...、List[List[List[...]]] 及其之间的态射是一个自函子的范畴。

---

幺半群

[幺半群][1]是一个带有二元运算 : M × M → M 的集合 M ，其符合下列公理：
结合律：对任何在 M 内的 a、b、c， (a*b)*c = a (b*c) 。
单位元：存在一在 M 内的元素 e，使得任一于 M 内的 a 都会符合 a*e = e*a = a 。

接着我们看看在自函子的范畴上，怎么结合幺半群的定义得出 Monad 的。

假设我们有个 cube 函数，它的功能就是计算每个数的 3 次方，函数签名如下：

cube :: Number -> Number

现在我们想在其返回值上添加一些调试信息，所以返回一个元组（Tuple），第二个元素代表调试信息。函数签名如下：

f :: Number -> (Number,String)

结合前面所讲，我们很容易知道元组构造子(Number,String)是一个自函子。Number 所在的范畴并不同于元组(Number,String)所在的范畴。换句话说，f 的入参和返回值属于两个范畴。那么这会产生什么影响？我们看看幺半群的定义中规定的结合律。对于函数而言，结合律就是将函数以各种结合方式嵌套起来调用。我们将常用的 compose 函数看作此处的二元运算。

var compose = function(f, g) {
  return function(x) {
    return f(g(x));
  };
};
compose(f, f)

从函数签名可以很容易看出，右边的 f 运算的结果是元组，而左侧的 f 却是接收一个 Number 类型的函数，它们是彼此不兼容的。

有什么好办法能消除这种不兼容性？假如输入和输出都是元组，结果会如何呢？

F :: (Number,String) -> (Number,String)
compose(F, F)                 

这样是可行的！在验证满足结合律之前，我们引入一个 bind 函数来辅助将 f 提升成 F.

f :: Number -> (Number,String) => F :: (Number,String) -> (Number,String)
var bind = function(f) {
return function F(tuple) {
var x = tuple[0],
s = tuple[1],
fx = f(x),
y = fx[0],
t = fx[1];
return [y, s + t];
};
};​

我们来实现元组自函子范畴上的结合律：

var cube = function(x) {
  return [x * x * x, 'cube was called.'];
};
var sine = function(x) {
return [Math.sin(x), 'sine was called.'];
};
var f = compose(compose(bind(sine), bind(cube)), bind(cube));
f([3, ''])
var f1 = compose(bind(sine), compose(bind(cube), bind(cube)));
f1([3,''])
>>>
[0.956, 'cube was called.cube was called.sine was called.']
[0.956, 'cube was called.cube was called.sine was called.']

这里 f 和 f1 代表的调用顺序产生同样的结果，说明元组自函子范畴满足结合律。

那如何找到这样一个 e ，使得 a*e=e*a=a

// unit :: Number -> (Number,String)
var unit = function(x) { return [x, ''] };
var f = compose(bind(sine), bind(cube));
compose(f, bind(unit)) = compose(bind(unit), f) = f

这里的 bind(unit) 就是 e 了。

Monads for functional programming 一 书中介绍说 monad 是一个三元组 (M, unit, *) ，对应此处就是 (Tuple, unit, bind) 。

参考链接

1. Translation from Haskell to JavaScript of selected portions of the best introduction to monads I've ever read
2. 我所理解的 monad
3. Monads for functional programming