Monad

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自函子范畴

图中表示的是一个将范畴映射到自身的自函子，而且还是一个特殊的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， (ab)c = a(bc) 。 单位元：存在一在 M 内的元素e，使得任一于 M 内的 a 都会符合 ae = e*a = a 。

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

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

cube :: Number -> Number

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

f :: Number -> (Number,String)

入参和出参不一致，这会产生什么影响？我们看看幺半群的定义中规定的结合律。对于函数而言，结合律就是将函数以各种结合方式嵌套起来调用。我们将常用的compose函数看作此处的二元运算。

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

compose(f, f)

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

有什么好办法能消除这种不兼容性？结合前面所讲，cube是一个自函数Number -> Number，而元组(Number,String)在Hask范畴是一个自函子，理由如下：

F Number = (Number,String) 
F Number -> Number = (Number,String) -> (Number,String)

假如输入和输出都是元组，结果会如何呢？

fn :: (Number,String) -> (Number,String)

compose(fn, fn)  

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

f :: Number -> (Number,String) => fn :: (Number,String) -> (Number,String)
注: 在Haskell中称为 liftM
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，此处的*是compose运算

// 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了。

到这里，思路逐步清晰了。在Haskell这类的强类型语言中，我们甚至可以组装自己的Tuple Monad。如下：

type Tuple(Number,String)
flatmap :: Tuple -> Number -> Tuple -> Tuple
unit :: Number -> Tuple
map :: Tuple >>= unit
    :: Tuple -> Number -> Number -> Tuple

//compose
// flatmap 即 bind，中缀表达式一般是 >>=
Tuple >>= (Number -> Tuple) >>= (Number -> Tuple)

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
4. Functor, Applicative, Monad