Monoid

我們先來看一下幾個 expression

(4 * 2) * 1
4 * (2 * 1)

([1] ++ [2,3]) ++ []
[] ++ ([1] ++ [2,3])

可以發現我們在做乘法運算時只要 x * 1 (或者1 * x) 我們都會得到我們傳入的數值， x ++ [] ([] ++ x) 也是一樣的道理。

我們可以歸納出幾個相同的點 ++ , *

1. 同樣是接受兩個參數
2. 參數跟回傳值是一樣的型別
3. 在某些情況下回傳值會是跟參數一樣
4. 遵守結合律

如果某個東西具有這些特性我們就可以說他是 monoid，一個 monoid 就是有一個遵守結合律的二元函數及在某些情況回傳值會跟參數一樣（其實就是 identity ），像是 1 之於 * 是的 identity 。當然不止 ++ 或者 * 是具有 monoid 的特性，所以 Haskell 提供了一個 typeclass Monoid 。

class Monoid m where  
    mempty :: m  
    mappend :: m -> m -> m  
    mconcat :: [m] -> m  

1. mempty 有點像是一個常數，它會回傳 type 為 m 的值
2. mappend 將兩個 m 丟進一個二元函數並回傳 m
3. mconcat 接收一個 m list ，然後回傳一個 m （可以想成 fold）

但除了實作出 Monoid 的 instance 以外還有一些規則 （monoid law）遵守才能算是 monoid

(x `mappend` y) `mappend` z == x `mappend` (y `mappend` z)
x `mappend` mempty == x
mempty `mappend` x == x

第一個就是要遵守結合律不論mappend 的順序如何結果都應該要一致，後面兩個就是 mempty 之於 mappend 要是 identity，

List

正如 ++ 跟 [] ，list 是一種 monoid ，在 Haskell 中是這麼定義的

instance Monoid [a] where
      mempty  = []
      mappend = (++)

可以看到 mempty 就是空 list [] ，mappend 是 (++) ，意思是 list 在做 (++) 運算時是會遵守結合律，以及 [] 之於 (++) 是具有 identity 的。

[1,2] `mappend` [3,4] -- [1,2,3,4]

[1]  `mappend` [2] `mappend` [3] `mappend` [4] -- [1,2,3,4]
([1]  `mappend` [2]) `mappend` [3] `mappend` [4] -- [1,2,3,4]
[1]  `mappend` ([2] `mappend` [3]) `mappend` [4] -- [1,2,3,4]
[1]  `mappend`( [2] `mappend` [3] `mappend` [4]) -- [1,2,3,4]

[1,2] `mappend` [3,4] `mappend` mempty  -- [1,2,3,4]
mempty `mappend` [1,2] `mappend` [3,4]  -- [1,2,3,4]

因為我們已經定義 mappend= (++) 所以我們這邊就會用 mappend infix 的形式來呼叫，就這幾個 expression 的結果，相信各位都能明顯地看出來不論我 mappend 的執行順序如何最後結果都會是一樣的，以及不管是 mappend` mempty` 或是 `mempty `mappend 只要其餘參數一樣結果都會是一樣的。

額外提醒 monoid law 並沒有特別說明 mappend 要遵守交換律，所以 [1,2] mappend [3,4] 跟 [3,4] mappend [1,2] 是可以不一樣的，但如果是 mempty mappend xs 跟 xs mappend mempty 當然就是會遵守交換律了。

加法及乘法

既然有稍微提到結合律那一定會想到加法及乘法。

1 + 0 
0 + 1

(1 + 2) + 3
1 + (2 + 3)

2 * 1
1 * 2

(1 * 2) * 3
1 * (2 * 3)

這些相信各位應該是熟到不能再熟了，所以其實我們一樣可以說 0 之於 (+) 是 identity ，1 之餘 (*) 是 identity 。

在 Data.Monoid 這個 module 有export 兩個 type Product 跟 Sum ，其中 Product 在實作 Monoid 的 instance 是這麼寫的

instance Num a => Monoid (Product a) where  
    mempty = Product 1  
    Product x `mappend` Product y = Product (x * y)

所以我一樣可以來試試看它是否遵守 monoid law

getProduct $ Product 1 `mappend` Product 2  `mappend` Product 3
getProduct $ Product 1 `mappend` (Product 2  `mappend` Product 3)
getProduct $ Product 2 `mappend` mempty
getProduct $  mempty `mappend` Product 2

簡單理解的話 getProduct 是 Product 這個 newtype 來定義的取值方式

會看到跟我們想的都一樣，都遵守了結合律以及如果與 mempty 進行運算回傳值就會等於參數。

monoid 是一個有點抽象的數學概念，但我覺得只要先以他是一個 typeclass 只是在規範這類東西都具有這些特性及行為就好，明天我們將會繼續討論在 Haskell 中其他具有 monoid 特性的東西。