又要工作了……

Monoid

Monoid 在 Haskell 中有很多應(yīng)用，且和折疊操作比較相關(guān)，值得學習。

幺半群 Monoid，或者說半群 with 幺元，那首先得了解半群和幺元是什么玩意。

半群 Semigroup 是這樣一種數(shù)學結(jié)構(gòu)，對非空集合 S，對 S 上的二元運算·: S x S -> S，其滿足結(jié)合律（即對集合 S 上的元素 a，b，c，有a · (b · c) = (a · b) · c），則二元組(S, ·)為半群；幺半群則在半群的基礎(chǔ)上添加了一個幺元 identity element——任何元素對其作運算·仍舊得到它自身，這是說假如令幺元為 e，則對 S 上任意元素 a，有a · e = a = e · a，三元組(S, ·, e)為幺半群。

數(shù)學定義抽象且無聊，但幺半群的幾個實例是非常明顯的：

1. （Int，+, 0)是幺半群——結(jié)合律：1 + (2 + 3) = (1 + 2) + 3, 幺元：1 + 0 = 0 + 1 = 1

2. （Int，*, 1)是幺半群——結(jié)合律：1 * (2 * 3) = (1 * 2) * 3, 幺元：2 * 1 = 1 * 2 = 2

3. ([a], ++, [])是幺半群——結(jié)合律：[1,2] ++ ([3] ++ [4]) = ([1,2] ++ [3]) ++ [4]，幺元：[1,2] ++ [] = [] ++ [1,2] = [1,2]

4. （String，++, "")是幺半群，同上

結(jié)合律允許以任意順序去執(zhí)行這樣的運算，這允許對其去并行計算。

Haskell 中定義了相應(yīng)的 typeclass 用來表示幺半群：

實現(xiàn)其只需要指定二元運算（在半群實例中）和幺元即可，下面定義數(shù)字加法幺半群：

Monoid 的實例需要滿足下面的定律：

容易發(fā)現(xiàn)，(Bool, &&, True)和(Bool, ||, False)也是幺半群：

應(yīng)用

Monoid 的定義很簡單，但其的使用的地方還是很多的，下面列一些可能常用的：

0. 列表是 Monoid。

1. Data.Text 是更高性能的字符串，其也是 Monoid 的實例，其無法像[Char]一樣使用++去拼接，因此需要使用半群的<>去進行拼接：

2. Data.Monoid 包下定義了 newtype First 和 Last，用于將Maybe m視為 Monoid，二元運算為取第一個或最后一個 Just 值，取不到則為 Nothing（Nothing 為幺元）；其特別適用于“取變量 x，如果 x 為 null，取變量 y”的需求（更抽象地說，對于變量 a,b,c,d,e…，從前往后或從后往前取第一個非 null 的變量）：

注意，Data.Semigroup 包下也定義了 First 和 Last，但其行為和 Data.Monoid 包下的同名 newtype 不同，Semigroup 包下的 First 和 Last 僅是半群且和 Maybe 無關(guān)，二元運算為取前者或后者?。影?！

First 也可以直接用類型類Alternative中的<|>替代，這樣更清晰些：

順便，對于Maybe m，若類型變量 m 是 Semigroup，則Maybe m為 Monoid，二元運算行為是將包含的值進行拼接，其中 Nothing 為幺元：

3. Ordering 類型，即 compare 函數(shù)的返回值類型，也是 Monoid，其幺元是EQ，二元運算的行為類似 First，其非常適合這種需求——先比較 x，如果 x 相等，比較 y。比如這里寫一個函數(shù)比較兩個字符串的長度大小，其中規(guī)定若兩個字符串等長，則比較兩個字符串內(nèi)容：

同態(tài)

乘法有一個所謂的分配律，這是說對實數(shù) a，b，c，有 a * (b + c) = a * b + a * c，定義f(x) = a * x，有f(b + c) = f(b) + f(c)，又能看到，f(0) = 0，這時稱函數(shù) f 是一個加法幺半群到加法幺半群上的同態(tài) Homomorphism，抽象地說，對于 Monoid a 和 b，有：

如，length 是([a], ++, [])到(Int, +, 0)的同倫映射：

這玩意有什么用呢？簡單來說，若有變量 a，b 是一個幺半群的元素且二元運算為+，求f(a + b)的值，若 f 是同倫映射，就可以并行地計算f(a)和f(b)，然后使用對應(yīng)二元運算得到結(jié)果。

但或許更有趣的地方是，Monoid 和折疊操作相關(guān)。

Foldable，但是 foldMap

Foldable 是列表的折疊操作的一般化，從而使任意類型具有折疊的能力。要實現(xiàn) Foldable，需要實現(xiàn) foldr 或者 foldMap，foldr 是老朋友了，foldMap 是何方神圣？

foldMap 的類型簽名是foldMap :: (Foldable t, Monoid m) => (a -> m) -> t a -> m，這是說，對于可折疊類型 t，如果有將其中元素映射成為某 Monoid 類型 m 的映射，就能把 t 折疊成 m。how？

考慮foldr f z [a, b, c]，其可以表述為a `f` (b `f` (c `f` z))，若令f = (<>), z = mempty，就得到了a <> (b <> (c <> mempty))，這正好是 mconcat 的定義：


可以看到，對于一個幺半群的列表，總是有一種方式去對它進行折疊操作，即是使用幺元作為初始值，使用二元運算作為操作符；將這泛化一步——若某列表中的元素能映射成為特定幺半群，則這個列表可以使用這個幺半群的方式去折疊，這就是 foldMap——先映射成為特定幺半群，再折疊：

foldMap 有一些非常有趣的玩法，比如定義 sum，product，all，any 等：

因為 mconcat 可以由 foldr 定義（實際上對左折疊也行，因為半群的結(jié)合性，但二元運算可能需要flip一下——半群不要求二元運算滿足交換律），所以 foldMap 可以由 foldr 定義。這是對折疊操作的一種新的視角——先把列表元素類型映射成幺半群，再用二元運算去 concat 成一個值。

這里去使用 foldMap 去實現(xiàn)一個 reverse，同時也給出 foldr 的版本：

foldMap 的這種對折疊操作的看待方式相當有趣——每次進行列表或其它結(jié)構(gòu)的折疊操作的時候，實際上都是定義了一個新的幺半群，將結(jié)構(gòu)中的值映射到幺半群的類型，并使用幺半群的二元運算去做拼接。那么，是否有可能根據(jù) foldMap 去定義折疊操作？

觀察 foldr 的簽名：

考慮折疊操作a -> b -> b，為返回值加上括號得到 a -> (b -> b)……唔姆唔姆，從這個角度上看 foldr，我們就是把列表中的元素 a 映射成為b -> b，然后將其不斷地應(yīng)用在初始值 b 上，得到最終結(jié)果，于是，如何處理列表b -> b和初始值 b？

好玩的地方來了：函數(shù)本身也是幺半群，幺元是 id，二元運算是函數(shù)組合，所以，我們可以先把b -> b列表折疊成一個b -> b，再應(yīng)用它到初始值 b上，下面是定義：

這說明可以用 foldMap 去實現(xiàn) foldr，前面又用 foldr 去實現(xiàn) foldMap，它們可以互相實現(xiàn)；Haskell 中提供折疊操作的類型類是 Foldable，其允許僅定義 foldMap 或 foldr 去實例化它，這里給出列表的遞歸的 foldMap 實現(xiàn)：

Foldable 中還有許多有趣的玩意，比如用 foldr 去實現(xiàn) foldl，foldr1 等，以及轉(zhuǎn)換到列表，檢查是否為空，獲取容器長度，求最大最小值等：

toList 非常有趣，其證明任何可折疊的類型都可以轉(zhuǎn)換成為列表，這借用了列表是幺半群這個特性：

toList reflects the fact that lists are the free monoid for Haskell types. “Free” here means any value can be promoted to the monoid in a way which neither adds nor erases any information (we can convert values of type a to [a] lists with a single element and back through (\x->[x]) and head in a lossless way)

應(yīng)用

所以，在什么情況下 foldMap 會比 foldr 更香？

考慮二叉樹：

能對這個樹做什么操作呢？比如，對每個子樹都應(yīng)用相同操作，比如獲取它以及所有子樹的和，獲取它的最大深度……

后兩個操作顯然都是折疊操作，所以，樹是可以折疊的！那如何折疊呢？如果嘗試去編寫 foldr，那代碼會顯得比較（或者相當？）繁瑣，但若使用 foldMap 的話，則會很容易：

定義了 Foldable 的實例后，定義 sumTree 就很簡單了：

問題在于，maxDepth 無法使用這個 foldMap 去表述——從中無法抽象出合適的幺半群（是否真的如此？？）。為什么如此呢？天知道。解決方案是編寫一種樹專屬的折疊函數(shù)，其對每個值先做一次映射，再對每個子樹進行合并，參數(shù)帶上根結(jié)點和左右子樹的值：

Bonus

下面在 typescript 里利用 foldMap 去實現(xiàn)了 sum 和 groupBy，使用了 type class 模式，比較有趣：

參考資料

• https://en.wikibooks.org/wiki/Haskell/Monoids

• https://en.wikibooks.org/wiki/Haskell/Foldable

• 《Haskell 趣學指南》