泛函程式設計（22）－泛函資料類型－Monoid In Action

 在上一節我們讨論了monoid的結合性和恒等值的作用以及monoid如何與串類元素折疊算法相比對。不過我們隻示範了一下基礎類型（primitive type）monoid執行個體的應用，是以上一節的讨論目的是理論多于實踐。在這一節我們将把重點放在一些實用綜合類型（composite type）monoid執行個體及monoid的抽象表達及函數組合能力。

    monoid的二進制操作函數具有結合特性（associativity），與恒等值（identity）共同應用可以任意采用左折疊或右折疊算法處理串類元素（list element）而得到同等結果。是以使用monoid op我們可以得出左折疊等于右折疊的結論：

左折疊：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)

如果我們可以使用并行算法的話，肯定能提升計算效率。試想如果我們對一個超大檔案進行文字數統計或者尋找最大值什麼的，我們可以把這個大檔案分成若幹小檔案然後同時計算後再合計将節省很多計算時間。在現代大資料時代，資料檔案不但大而且是分布在許多伺服器上的。那麼monoid的特殊定律就可以使資料處理并行運算，特别比對大資料處理模式。

我們看看能不能實作像折疊算法似的并行算法：

啊，這個foldmapv從外表，在類型款式上跟foldmap相同，不同的是内部具體實作方式；foldmapv循環把目标串進行分半。

結合前面對并行運算的讨論，我們用以下方式應該可以實作并行運算吧：

好，我們下面找個例子來示範高階類型monoid執行個體和并行運算應用：用monoid來實作對字串（list[string]）的文字數統計。由于我們打算采用并行計算，對字串進行分半時會可能會出現一字分成兩半的情況，是以需要自定義複雜一點的資料類型：

 monoid[wc]是個wc類型的monoid執行個體，op(wc1,wc2)=wc3則把兩個wc值拼湊起來變成另一個wc值。下面讓我們用wcmonoid來實作這個文字統計函數：

用它來數個字數：

沒錯！

再來一個例子：檢查一串數字是否是有序的：

在這個例子裡我們用option[min,max,ordered］作為目前狀态并用statemonoid來處理這個狀态。foldmapv參數（i => some(i,i,true))就是标準的 a => b。還記得嗎，我們增加foldmap這個函數是的目的是如果元素a沒有monoid執行個體，那麼我們可以用monoid[b]然後用a =>b函數把a轉成b才能使用monoid[b]。這裡我們把 i轉成some(int,int,boolean)。

值得注意的是以上兩個例子foldmapv曆遍無論如何是不會中途退出的。這個特點把foldmapv的使用局限在必須消耗整個資料源的計算應用，如求和、最大值等等。對于另外一些要求，如：a => boolean這種要求，即使第一個值就已經得到答案也必須走完整串資料。

我們在之前的章節裡曾經讨論了一些資料結構如list,stream,tree等。當我們需要處理這些結構中封裝的元素時通常使用一些算法如折疊算法。這種算法能儲存資料結構。而且它們有共通性：都可以使用折疊算法。既然有共性，肯定就會有深度抽象的空間，我們可以把它們抽象表達成一個foldable[f[_]]：list,stream,tree等資料結構類型就是f[_]；一個資料結構中封裝了一些元素。這個foldable類型可以包含各種曆遍算法：

我們現在已經得到了個foldable抽象資料結構，它包含了多種折疊曆遍算法。我們可以試着建立一些foldable執行個體看看：

再看看tree foldable 執行個體：

可以看出treefoldable的實作方式與list,stream等串類資料類型有所不同。這是因為tree類型沒有現成的折疊算法。再就是tree類型沒有空值（隻有leaf, branch）。這個特性暗示着有些類型的monoid是沒有恒等值的。我們統稱這些類型為semigroup。

 option的foldable與treefoldable很像：

實際上任何可折疊的資料類型都可以被轉換成list類型，因為我們可以用折疊算法重組list:

monoid的函數組合能力也挺有趣：如果我們有monoid[a], monoid[b]，那我們就可以把它們組合成monoid[(a,b)]：

 我們可以用這個組合的monoid在曆遍一個list時同時計算list長度及和：

在曆遍過程中我們把list每個節點元素值轉成一對值 a => (1, a)，然後分别對每個成員實施intadditionmonoid的op操作。

下面剩下的時間我們再讨論一些較複雜的monoid:

如果一個函數的結果是monoid，我們可以實作這個函數的monoid執行個體：

實作這個monoid執行個體的應當盡量從類型比對入手：函數a => b的結果是b；我們有monoid[b]，monoid[b].op(b,b)=>b。

再來一個合并key-value map的monoid執行個體：如果我們有value類型的monoid執行個體就可以實作：

有了這個monoid執行個體，我們就可以處理map的嵌入表達式了：

最後，我們試着用mapmergemonoid執行個體來實作frequencymap：計算輸入list裡的文字發現次數。如果用一個例子來說明的話，看看下面這個一串文字轉成key-value map：

vector("a rose", "is a", "rose is", "a rose") >>> map(a -> 3, rose -> 3, is -> 2)

這不就是搜尋引擎中的索引比重算法嗎？我們用foldmapv和mapmergemonoid可以并行運算整理索引，這算是monoid的實際應用之一。

我們看看具體實作：