泛函程式設計（24）－泛函資料類型－Monad, monadic programming

   在上一節我們介紹了monad。我們知道monad是一個高度概括的抽象模型。好像創造monad的目的是為了抽取各種資料類型的共性元件函數彙內建一套元件庫進而避免重複編碼。這些能對什麼是monad提供一個明确的答案嗎？我們先從上節設計的monad元件庫中的一些基本函數來加深一點對monad的了解：

我們分别用m[a]對應list[a],option[a]及par[a]來分析一下sequence函數的作用：

1. sequence >>> 用map2實作 >>> 用flatmap實作：

   對于list: sequence[a](lm: list[m[a]]): m[list[a]] >>> sequence[a](lm: list[list[a]]): list[list[a]] 

             >>> map2(list(list1),list(list2)){_ :: _} ,把封裝在list裡的list進行元素分拆交叉組合，

             例：(list(list(1,2),list(3,4)) >>> list[list[int]] = list(list(1, 3), list(1, 4), list(2, 3), list(2, 4)）

             sequence的作用展現在list.map2功能。而list.map2則是由list.flatmap實作的。是以sequence的行為還是依賴于list執行個體中flatmap的實 現方法

   對于option: sequence[a](lm: list[m[a]]): m[list[a]] >>> sequence[a](lm: list[option[a]]): list[option[a]] 

             >>> map2(list(opton1),list(option2)){_ :: _} ,把封裝在list裡的元素option值串成list，

             例：(list(some(1),some(2),some(3)) >>> option[list[int]] = some(list(1, 2, 3))

             由于sequence的行為還是依賴于執行個體中flatmap的實作，option 的特點：flatmap none = none 會産生如下效果：

             list(some(1),none,some(3)) >>> option[list[int]] = none

   對于par: sequence[a](lm: list[m[a]]): m[m[a]] >>> sequence[a](lm: list[par[a]]): list[par[a]] 

             >>> map2(list(par1),list(par2)){_ :: _} ,運作封裝在list裡的并行運算并把結果串成list，

             這裡par.flatmap的功能是運作par，run(par)。這項功能恰恰是并行運算par的核心行為。

從分析sequence不同的行為可以看出，monad的确是一個通用概括的抽象模型。它就是一個很多資料類型元件庫的軟體接口：使用統一的函數名稱來實作不同資料類型的不同功能效果。

  與前面讨論過的monoid一樣，monad同樣需要遵循一定的法則來規範作用、實作函數組合（composition）。monad同樣需要遵循結合性操作（associativity）及恒等（identity)。

monoid的結合性操作是這樣的：op(a,op(b,c)) == op(op(a,b),c)  對monad來說，用flatmap和map來表達結合性操作比較困難。但我們如果不從monadic值m[a]（monadic value)而是循monadic函數a=>m[b]（monadic function)來證明monad結合性操作就容易多了。

a=>[b]是瑞士數學家heinrich kleisli法則的箭頭（kleisli arrow）。我們可以用kleisli arrow來實作一個函數compose:

def compose[a,b,c](f: a=>[b], g: b=>m[c]): a=>m[c]。從函數款式看compose是一個monadic函數組合。我們從傳回值的類型a=>m[c]得出實作架構 a => ???；從傳入參數類型 b=>m[c]可以估計是flatmap(m[a])(b=>m[c]； 是以：

注意：compose的實作還是通過了flatmap這個主導monad執行個體行為的函數。有了compose我們就可以證明：

compose(f,compose(g,h)) == compose(compose(f,g),h)

flatmap和compose是互通的，可以互相轉換。我們可以用compose來實作flatmap：

我們可以用例子來證明它們的互通性：

至于monad恒等性，我們已經得到了unit這個monad恒等值：

def unit[a](a: a): m[a]。通過unit我們可以證明monad的左右恒等：

compose(f,unit) == f

compose(unit,f) == f

由于compose是通過flatmap實作的。compose + unit也可以成為monad最基本元件。實際上還有一組基本元件join + map + unit：

又是通過flatmap來實作的。

我們同樣可以用join來實作flatmap和compose:

仔細觀察函數款式（signature），推導并不難。map a=>m[b] >>> m[m[b]]，實際上join是個展平函數m[m[a]] >>> m[a]。

雖然有三種基本元件，我還是比較傾向于flatmap，因為隻要能flatmap就是monad。對我來說monadic programming就是flatmap programming，其中最重要的原因是scala的for-comprehension。for-comprehension是scala的特點，隻要是monad執行個體就可以用for-comprehension，也可以說隻要能flatmap就可以吃到for-comprehension這塊文法糖。我們用一個比較複雜但實用的資料類型來說明：

在前面我們曾經實作了state類型。而且我們也實作了state類型的map, flatmap這兩個函數：

既然實作了flatmap, 那麼state就可以是monad的了吧。我們試着建一個state monad執行個體：

state類定義是這樣的：case class state[s,+a](run: s => (a, s)) 

val statemonad = new monad[state[???， 糟糕，monad[m[_]]，m是個接受一個類參數的高階類型，而state[s,a]是個接受兩個類參數的高階類型，該怎麼辦呢？我們可以這樣解釋state：state[s,_]：實際上state[s,_]是一組不同s的state[a]，換句話說：state不隻有一個monad執行個體而是一類的monad執行個體。我們可以這樣表述這類的monad：

我們可以這樣使用以上的state monad：statemonad[list[int]].monad

在上面我們遇到的問題是由于state類型與monad m[_]類型不相容引起的。這個問題會被scala編譯器的類系統（type system）逮住，然後終止編譯過程。是不是能從解決類系統問題方面着手呢？我們可以用type lambda來糊弄一下類系統：

看，在monad類參數裡糊弄了類系統後，statemonad内部沿用了state正常表述，沒任何變化。type lambda在scalaz裡使用很普遍，主要還是解決了資料類型參數不比對問題。

實作了state monad後我們可以看個相關例子：

說明：foldleft(z:b)(f:(b,a)=>b)的z是個intstatemonad執行個體類型b，是以foldleft的操作函數就是：(intstatemonad,a)=>intstatemonad，我們可以使用for-comprehension。這個操作函數的傳回結果是個intstatemonad執行個體；是以我們可以用state類的run(0)來運算state轉換；state的狀态起始值是0。

以上的例子做了些什麼：它把list[string]轉成了list[(int,string)]，把list[string]中每一個字串進行了索引。在這個例子裡我們了解了monad的意義：

1、可以使用for-comprehension

2、支援泛函式的循序指令執行流程，即：在高階類結構内部執行操作流程。flatmap在這裡起了關鍵作用，它確定了流程環節間一個環節的輸出值成為另一個環境的輸入值

那麼我們可不可以說：monad就是泛函程式設計中支援泛函方式流程式指令執行的特别程式設計模式。