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， (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).
参考链接：
