Monads是什么
知乎里有關(guān)于什么是Monad的問題討論，而在維基百科中也有關(guān)于Monad的釋義。作為初次接觸到Monads概念，難免會有些暈頭轉(zhuǎn)向，也難免會有些畏懼（因為Monads和數(shù)學(xué)中的范疇論有密切關(guān)系），但是Monads又是如此的重要，因為它在函數(shù)式編程中實在是應(yīng)用太廣泛了，并且在Scala的標(biāo)準(zhǔn)庫中又常常遇到，使得我們不得不好好研究一番。
Monoids
Monoids是一種元素的集合，它需要滿足結(jié)合律和幺元（Identity，也稱為單位元，這種元和其他元素結(jié)合時，不會改變那么元素）這些約束條件。
比如：
- 整數(shù)類型Int，其中0是Identity，其中的任何整數(shù)滿足結(jié)合律
- 列表類型List，任何兩個列表可以通過
:::連接起來，其中Nil或空列表[]是Identity - 字符串類型String，兩個字符串可以拼接，其中空字符串或""是Identity
Monoids在平常的編程之中無處不在，當(dāng)用到一個列表，連接字符串，通過一個循環(huán)得到一個累加結(jié)果，都在使用到Monoids。
條件和定律
- 一個抽象類型A
- 一個二元結(jié)合性函數(shù)（binary associative function），對傳入的兩個A類參數(shù)進行操作后產(chǎn)生一個A類型結(jié)果。op操作必須是結(jié)合性的，即op(x, y) == op(y, x)；op(a,op(b,c)) = op(op(a,b),c)：這個定律是函數(shù)組合（function composition）不可缺的條件
- 一個恒等值（identity）。二元函數(shù)參數(shù)中如果有一個是恒等值時操作結(jié)果為另一個參數(shù)，即滿足op(identity, x) == x
示例
Monoid可以用下面的代碼描述：
trait Monoid[T] {
def op(m1: T, m2: T): T
val identity: T
}
這個特質(zhì)可以被混入類型（classes）、對象（objects）或者其他特質(zhì)中。請看下面的舉例：
case class StringMonoid extends Monoid[String] {
def op(s1: String, s2: String) = s1 + s2
val identity = ""
}
val stringMonoid = StringMonoid()
println(stringMonoid.op(stringMonoid.identity, "John"))
println(stringMonoid.op("John", "Hunt"))
// Output is
// John
// JohnHunt
object IntMonoid extends Monoid[Int] {
def op(x: Int, y: Int) = x + y
val identity = 0
}
println(IntMonoid.op(IntMonoid.identity, 1))
println(IntMonoid.op(1, 2))
println(IntMonoid.op(2, 1))
// Output is
// 1
// 3
// 3
Monoid和折疊
如果有一個Monoid結(jié)構(gòu)和一組數(shù)據(jù)?？梢酝ㄟ^對每個元素進行Monoid的op操作來將集合縮減為一個值，比如將一個整數(shù)列表通過元素累加的方式得到所有整數(shù)的和。
Monoid和List有著密切的聯(lián)系。在List的foldLeft操作中，用一個初始元素從列表的左邊元素開始操作，一直到對所有元素都操作完。如List("A", "B", "C").foldLeft("")(_ + _)這個對字符串列表實現(xiàn)累加功能，foldLeft傳入的兩個參數(shù)分別是空字符串和二元操作運算，這正好符合Monoid的定義，可以輕松利用StringMonoid代替，List("A", "B", "C").foldLeft(StringMonoid.identity)(StringMonoid.op)。
結(jié)合性與并行化
Monoid的結(jié)合性意味著我們在對類似List的數(shù)據(jù)結(jié)構(gòu)進行折疊的時候有很大的靈活性。我們已經(jīng)知道可以使用foldLeft和foldRight對一個列表進行順序的規(guī)則（reduce）操作。但是我們同樣可以將數(shù)據(jù)分成多份，并行的進行折疊，然后利用monoid將各個部分合并起來。
左折疊操作是op(op(op(a, b), c), d)
右折疊操作是op(a, op(b, op(c, d)))
并行算法為op(op(a, b), op(c, d))，其中op(a, b)和op(c, d)是同時運算的。
如果我們對一個超大文件進行文字?jǐn)?shù)統(tǒng)計或者尋找最大值什么的，我們可以把這個大文件分成若干小文件然后同時計算后再合計將節(jié)省很多計算時間。
Monoid模式的優(yōu)缺點
優(yōu)點：
- Monoid模式提供了一種在特定場景下將元素合并的標(biāo)準(zhǔn)方法
- 結(jié)合性的保證可以用來定義函數(shù)之間組合
缺點：
- 并不是所有集合都可以很容易的應(yīng)用Monoid模式。比如String Monoid，不同順序的字符串進行連接可能會得到不同的結(jié)果。
從范疇論到計算機編程
從Monoid到Monad，這些概念都是從范疇論中衍生出來的。
理解范疇論的一個好方法是把它理解為應(yīng)用到函數(shù)式編程領(lǐng)域的設(shè)計模式。范疇論定義了一些非常底層的概念抽象，這些概念可以直接用Scala這樣的支持函數(shù)式編程的語言表達(dá)。在設(shè)計軟件的時候，如果一個特定實體符合其中一個概念，那么立刻就有一整組操作可用，而且包含推理其用法的方法。
范疇是由元素對象和態(tài)射箭頭組成的，這個箭頭開始端是一個元素對象，目的地也是一個元素對象。這里態(tài)射箭頭有兩種，不同元素對象比如a和b之間的態(tài)射箭頭稱為組合箭頭，而指向自己的箭頭稱為元箭頭，或者單元，幺元。
范疇的元素對象和箭頭態(tài)射的規(guī)則如下：
- 對于箭頭f:a -> b和箭頭g:b -> c，如果有一個箭頭h: a -> c，那么就稱為它們的組合，寫法是：h=g·f
- 對于每個元素對象，都有一個單元箭頭：id:a -> a。對于任何f: a -> b，滿足f·id = f；對于任何g: c -> a，滿足id·g = g
- 組合符合結(jié)合律：f·(g·h) = (f·g)·h
態(tài)射箭頭有兩種，一種是標(biāo)號1的組合箭頭，還有一種是標(biāo)號2的單元箭頭。
我們將一個范疇有元素對象和態(tài)射箭頭，態(tài)射箭頭有組合和幺元兩種，且滿足結(jié)合律，這種范疇稱為Monoid。
對于某非空集合S，若存在S上的二元運算"*"使得對于任意的a,b∈S,有a*b∈S（運算封閉），則稱{S,*}為廣群?！V群只是定義一個集合，集合中有元素和操作，操作結(jié)果也屬于這個集合，這樣泛泛的集合稱為廣群?！∪绻麖V群再加上結(jié)合律約束，就會得到半群，因此半群是廣群的子集，要求更苛刻些，而半群如果再加上幺元（identity element）就是幺半群，也就是結(jié)合律+幺元=幺半群，所以，Monid對應(yīng)的中文是幺半群。
參考資料
Functional Programming in Scala
Scala Design Patterns: Patterns for Practical Reuse and Design
什么是Monoid？
我所理解的monad(2)：fold與monoid
轉(zhuǎn)載請注明作者Jason Ding及其出處
Github博客主頁(http://jasonding1354.github.io/)
GitCafe博客主頁(http://jasonding1354.gitcafe.io/)
CSDN博客(http://blog.csdn.net/jasonding1354)
簡書主頁(http://www.itdecent.cn/users/2bd9b48f6ea8/latest_articles)
Google搜索jasonding1354進入我的博客主頁
