Monad不就是個自函子范疇上的幺半群，這有什么難理解的（A monad is just a monoid in the category of endofunctors）
—— Phillip Wadler
自函子(Endofunctor)
什么是函數(shù)（Function）冰啃？
函數(shù)表達的映射關(guān)系在類型上體現(xiàn)在特定類型（proper type）之間的映射刘莹。
什么是自函數(shù)（Endofunction）？
identity :: Number -> Number
自函數(shù)就是把類型映射到自身類型点弯。函數(shù)identity是一個自函數(shù)的特例，它接收什么參數(shù)就返回什么參數(shù)狼钮，所以入?yún)⒑头祷刂挡粌H類型一致捡絮，而且值也相同。
接下來涎拉，回答什么是自函子（Endofunctor）之前的圆，我們先弄清什么是函子（Functor）？
函子有別于函數(shù)越妈，函數(shù)描述的是特定類型（proper type）之間的映射梅掠，而函子描述的是范疇（category）之間的映射。
那什么是范疇（category）瓤檐？
我們把范疇看做一組類型及其關(guān)系態(tài)射（morphism）的集合娱节。包括特定類型及其態(tài)射，比如Int谴古、String、Int -> String汇陆；高階類型及其態(tài)射带饱，比如List[Int]、List[String]勺疼、List[Int] -> List[String]。
接下來看看函子是如何映射兩個范疇的酪耕，見下圖：
圖中范疇C1和范疇C2之間有映射關(guān)系轨淌，C1中Int映射到C2中的List[Int]，C1中String映射到C2中的List[String]盟步。除此之外梳虽，C1中的關(guān)系態(tài)射Int -> String也映射到C2中的關(guān)系List[Int] -> List[String]態(tài)射上。
換句話說谷炸，如果一個范疇內(nèi)部的所有元素可以映射為另一個范疇的元素禀挫，且元素間的關(guān)系也可以映射為另一個范疇元素間關(guān)系，則認為這兩個范疇之間存在映射描孟。所謂函子就是表示兩個范疇的映射砰左。
澄清了函子的含義，那么如何在程序中表達它缠导？
在Haskell中，函子是在其上可以map over的東西憋他。稍微有一點函數(shù)式編程經(jīng)驗竹挡，一定會想到數(shù)組（Array)或者列表（List），確實如此梯码。不過耸序，在我們的例子中，List并不是一個具體的類型坎怪，而是一個類型構(gòu)造子。舉個例子嘁酿，構(gòu)造List[Int]男应，也就是把Int提升到List[Int]，記作Int -> List[Int]游桩。這表達了一個范疇的元素可以映射為另一個范疇的元素耐朴。
List具有map方法，不妨看看map的定義：
f :: A -> B
map :: f -> List[A] -> List[B]
具體到我們的例子當(dāng)中铐刘，就有：
f :: Int -> String
map :: f -> List[Int] -> List[String]
展開來看：
map :: Int -> String -> List[Int] -> List[String]
map的定義清晰地告訴我們：Int -> String這種關(guān)系可以映射為List[Int] -> List[String]這種關(guān)系影晓。這就表達了元素間的關(guān)系也可以映射為另一個范疇元素間關(guān)系。
所以類型構(gòu)造器List[T]就是一個函子疤祭。
理解了函子的概念饵婆，接著繼續(xù)探究什么是自函子。我們已經(jīng)知道自函數(shù)就是把類型映射到自身類型，那么自函子就是把范疇映射到自身范疇。
自函子是如何映射范疇的续挟，見下圖：
圖中表示的是一個將范疇映射到自身的自函子侥衬，而且還是一個特殊的Identity自函子。為什么這么說直颅？從函子的定義出發(fā)怀樟，我們考察這個自函子，始終有List[Int] -> List[Int]以及List[Int] -> List[String] -> List[Int] -> List[String]這兩種映射往堡。
我們表述成：
類型List[Int]映射到自己
態(tài)射f :: List[Int] -> List[String]映射到自己
我們記作：
F(List[Int]) = List[Int]
F(f) = f
其中虑灰，F(xiàn)是Functor.
除了Identity的自函子，還有其它的自函子穆咐，見下圖：
圖中的省略號代表這些范疇可以無限地延伸下去对湃。我們在這個大范疇所做的所有映射操作都是同一范疇內(nèi)的映射，自然這樣的范疇就是一個自函子的范疇熟尉。
我們記作：
List[Int] -> List[List[Int]]
List[Int] -> List[String] -> List[List[Int]] -> List[List[String]]
...
所以List[Int]斤儿、List[List[Int]]、...往果、List[List[List[...]]]及其之間的態(tài)射是一個自函子的范疇。
幺半群
[幺半群][1]是一個帶有二元運算 : M × M → M 的集合 M 堕油，其符合下列公理：
結(jié)合律：對任何在 M 內(nèi)的a、b卜录、c眶明， (ab)c = a(bc) 。
單位元：存在一在 M 內(nèi)的元素e搜囱，使得任一于 M 內(nèi)的 a 都會符合 ae = e*a = a 。
接著我們看看在自函子的范疇上绊汹，怎么結(jié)合幺半群的定義得出Monad的扮宠。
假設(shè)我們有個cube函數(shù)，它的功能就是計算每個數(shù)的3次方浴栽，函數(shù)簽名如下：
cube :: Number -> Number
現(xiàn)在我們想在其返回值上添加一些調(diào)試信息轿偎，所以返回一個元組（Tuple），第二個元素代表調(diào)試信息萝玷。函數(shù)簽名如下：
f :: Number -> (Number,String)
入?yún)⒑统鰠⒉灰恢吕バ觯@會產(chǎn)生什么影響？我們看看幺半群的定義中規(guī)定的結(jié)合律仓蛆。對于函數(shù)而言看疙，結(jié)合律就是將函數(shù)以各種結(jié)合方式嵌套起來調(diào)用。我們將常用的compose函數(shù)看作此處的二元運算能庆。
var compose = function(f, g) {
return function(x) {
return f(g(x));
};
};
compose(f, f)
從函數(shù)簽名可以很容易看出，右邊的f運算的結(jié)果是元組弥搞，而左側(cè)的f卻是接收一個Number類型的函數(shù)，它們是彼此不兼容的船逮。
有什么好辦法能消除這種不兼容性粤铭？結(jié)合前面所講，cube是一個自函數(shù)Number -> Number，而元組(Number,String)在Hask范疇是一個自函子伪煤，理由如下：
F Number = (Number,String)
F Number -> Number = (Number,String) -> (Number,String)
假如輸入和輸出都是元組，結(jié)果會如何呢职烧？
fn :: (Number,String) -> (Number,String)
compose(fn, fn)
這樣是可行的防泵！在驗證滿足結(jié)合律之前，我們引入一個bind函數(shù)來輔助將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];
};
};
我們來實現(xiàn)元組自函子范疇上的結(jié)合律：
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代表的調(diào)用順序產(chǎn)生同樣的結(jié)果足删，說明元組自函子范疇滿足結(jié)合律锁右。
那如何找到這樣一個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, *)，對應(yīng)此處就是(Tuple, unit, bind).
參考鏈接：
