從reduce認識Monoid

程式設計的本質就是運算，而運算的本質呢？艾倫圖靈觀察人們從事的運算任務，從中逐一分解，探討運算的能力來源，建立了狀態機、下推機、圖靈機等數學模型，運算的本質就是數學！

如果開發者試著學習一門純函數式語言，例如Haskell，藉由觀察重複，可以抽取出像是Functor、Applicative、Monad等行為，然而隨著抽象程度不斷地提高，會發現抽象出來的概念，越來越朝著數學基礎定義的方向前進，不少開發者也就越難以理解這些定義的實質作用，例如Haskell的Monoid型態類別，規範了恆等值（identity）與結合律（Associativity），這是什麼呢？

恆等值與結合律？

現代有不少命令式語言，融入了許多函數式的概念，Functor、Applicative、Monad等行為，或多或少都找得到對應的API。

例如，list與map方法就像實現了Functor，list與flatMap就像實現了Monad，如果曾經試著將運算子作為函式傳入某個方法來運算兩個物件，就像實現了Applicative，那麼，Monoid型態類別呢？這看來就像純數學上的定義吧！

函數式設計的入門課題中，不是有filter/map/reduce嗎？

在reduce這部份，是個消減操作，例如，將1到5加總，可以看成是將1到5的list，以0開始與指定加法來消減得到，那麼，指定的0是什麼值？許多API文件都說是初值？

其實，嚴格來說，這個初值必須是加法的恆等值，而reduce可指定的運算，其實必須具有結合律，加法就是具有結合律的運算。

或許有人會認為這太小題大作，不過，比較嚴謹的API文件就會標明，例如Java的Stream API，其reduce方法說明就確實規範了，accumulator必須是具有結合律的二元函數，identity參數必須是accumulator恆等值。

通用的reduce行為

雖然不少程式庫的reduce實作多是針對list，然而，Java的Stream來源，不一定要是list，也可能是Set，而且就算reduce只針對list，開發者也可以自行轉換為list再進行reduce，也就是reduce的對象不用是特定的資料結構。

另一方面，就算只針對list，執行reduce時是由左往右還是由右往左呢？JavaScript陣列確實有明確規範reduce與reduceRight，不過，大多數的reduce沒有限定方向，例如Java的reduce就明確說明了，reduce時並不限於循序。

這麼一來，如果要實作通用的reduce，會需要哪些條件呢？

能接受的函式必須是二元函式，它要將兩個型態相同的運算元結合，成為一個相同型態的值。例如，加法函式可以將2與3結合為5，*可以將2與3結合為6，字串的串接函式，可以將"abc"與"def"結合為"abcdef"，而且，該二元函式必須具有結合律，例如，(1+2)+3會與1+(2+3)相同，因此，加法具有結合律。

這是因為事先無法預料可以折疊的資料型態會是什麼樣的結構，被丟進函式處理的兩個值，可能是從結構中任意處取得，如果函式不具備結合律，通用的reduce執行結果就可能不正確。

另外，指定的二元函式必須具有恆等值，函式套用恆等值與某值，結果還會是該值，例如，0對加法是個恆等值，因為任何數與0相加都會是原來的數，1加0還是1、2加0還是 2，類似地，1對乘法是個恆等值，因為任何數與1相乘，結果還是原數字，2乘1還是2，3乘1還是3。

這個考量同樣是因為，事先無法預料可以折疊的資料型態會是什麼樣的結構，因此，通用的reduce首次執行時，必須有個初始的恆等值才能作為開始。

Monoid規範積累行為

先前專欄〈掌握Haskell型態類別〉我曾提過，對於可折疊的行為，Haskell定義了Foldable型態類別，如果我們想要實現Foldable，可以實現foldr行為，這對於大部份開發者而言，沒有問題，另一個方式是實作foldMap，函式型態是Monoid m => (a -> m) -> t a -> m，這是什麼呢？

現代開發者應該對使用map轉換list的元素，後續進行reduce得到一個結果，滿熟悉的吧！

其實map目的之一，就是將list的元素轉換為具有Monoid行為的元素，之後再進行reduce，fold就是reduce，而foldMap就只是將map與fold結合起來，foldMap由右往左讀的意思，就是先map再fold，指定的a -> m就相當於指定給map的函式，該函式用於將t a的a轉換為m，後續將t m折疊為m，就結果而言，就是t a -> m。

記得Google提出的大數據架構MapReduce嗎？在分散式運算的架構下，各節點得到的資料彼此獨立，因此，Map階段要將資料轉換為具有Monoid行為的資料，才能在Reduce階段運算。

Monoid型態類別的mempty規範的就是恆等值，而mappend規範的就是有結合律的函式。其實還有個mconcat，規範了積累（accumulate）運算，積累是比折疊更為抽象的觀念，因為積累的方式並不限於折疊，只不過預設實作是透過右折疊foldr，如果沒特別要求，想實現Monoid時，只要實作mempty與mappend。

簡單來說，Monoid規範了資料該怎麼進行積累，像是一組字串如何積累為字串，一組list如何積累為一個list，一組數字如何積累為一個數字等。

有些開發者可能有疑問，方才談到數字的加法與乘法具有結合律，而且，有對應的恆等值，那麼，Haskell的數字是Monoid嗎？是的！不過，在此時，問題就來了，1 `mappend` 2要選哪個結合？加法還是乘法？

Haskell的Data.Monoid模組，以newtype定義了Sum與Product，對於具有加法及乘法概念的資料，可以透過Sum與Product來區分，例如以下同樣的r，面對Sum s，s會是加法的結果3，面對Product p，p會是乘法的結果2：

let r = 1 `mappend` 2
let (Sum s) = r
let (Product p) = r

Monoid的組合能力

Haskell的list、數字以外，還有許多的Monoid實現，例如Maybe，對兩個Maybe進行mappend，它會對內含的值做mappend（也就是內含值也要是Monoid），(Just "a") `mappend` (Just "b")可以得到Just "ab"，也就是說，只要是Monoid，就可以自由地結合。

這就是為什麼，在純函數式的世界中，隨著抽象程度不斷地提高，抽象出來的概念，越來越會朝著數學基礎定義方向前進的原因，只要越是將運算的本質定義出來，就越能基於這些本質進行組合，得到各種運算的可能性，圖靈機的探討是如此，lambda演算的探討也是如此！

沒想到吧！reduce的來源元素需要有Monoid規範的結合律與恆等值，Monoid更接近純粹數學上的概念，是為了讓程式有更多的組合性。

如果下次我們遇到更接近數學層面的型態類別，不妨從組合性的方向思考，或許就能瞭解到其行為之意義！