Monoid_Haskell 筆記 9

一、幺元

數學世界裡，0 是加法單位元，1 是乘法單位元（identity element），例如：

> 0 + 3
3
> 3 + 0
3
> 1 * 3
3
> 3 * 1
3

二者的共同點是參與運算，但不改變另一個操作數：

In mathematics, an identity element or neutral element is a special type of element of a set with respect to a binary operation on that set, which leaves other elements unchanged when combined with them.

（摘自 Identity element）

單位元定義在集合裡的二元運算上，與單位元結合做運算時，其它元素不變（運算結果仍是該元素）。細分為左單位元（e * a = a）和右單位元（a * e = a），如果同時滿足就稱之為單位元，也稱為幺元（離散數學有學過這個東西）

Haskell 裡，也有類似的東西（被稱為 Monoid），比如 ++ 運算遇到 []：

> [] ++ "abc"
"abc"
> "abc" ++ []
"abc"

++ 是定義在 List 上的二元運算，並且 [] 符合幺元性質

二、Monoid

In abstract algebra, a branch of mathematics, a monoid is an algebraic structure with a single associative binary operation and an identity element.

（摘自 Monoid）

幺半群（monoid），抽象代數中的概念，指的是一個帶有可結合二元運算和幺元的代數結構。正規（嚴謹）描述如下：

幺半群是一個帶有二元運算 *: M × M → M 的集合 M，符合下列公理： 結合律：對任何在 M 內的 a、b、c，(a*b)*c = a*(b*c) 幺元：存在一在 M 內的元素 e，使得任一於 M 內的 a 都會符合 a*e = e*a = a

（摘自 幺半群）

要有個遵守結合律的二元函數，還要有個作為該函數幺元的值，二者構成 Monoid

Monoid typeclass

位於 Data.Monoid 模塊：

class Semigroup a => Monoid a where
    mempty  :: a
    mappend :: a -> a -> a
    mappend = (<>)
    mconcat :: [a] -> a
    mconcat = foldr mappend mempty

（摘自 GHC.Base）

P.S. 注意，(<>) 是 Semigroup 類定義的，mappend = (<>) 聲明了 mappend 與 <> 是完全等價的

要求 Monoid（幺半群）必須先是 Semigroup（半群，具體見最後一部分），其中 mempty 是幺元，mappend 是那個二元函數

mappend 就是幺半群定義中要求的那個遵守結合律的二元函數，名字不很合適（雖然含有 append，但並不是說必須要實現類似 append 的動作），它接受兩個 monoid 值，並返回另一個 monoid 值

mconcat 接受一列 monoid 值，再通過 mappend 折疊（fold，或者叫 reduce 規約）成一個 monoid 值，給了默認實現，一般不需要自己實現，除非有更合適的實現方式（比如效率更高的方式）

Monoid laws

Monoid 類也要遵守一些規則，如下：

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

前兩條保證 mempty 是幺元，第三條說明二元函數 mappend 滿足結合律

三、Monoid instances

List

instance Semigroup [a] where
  (<>) = (++)

instance Monoid [a] where
  mempty  = []
  mconcat xss = [x | xs <- xss, x <- xs]

（摘自 GHC.Base）

如我們所想，List 以及定義在 List 上的 ++ 運算與空 List 幺元，構成幺半群

用 Monoid laws 驗證一下：

> mempty `mappend` "hoho"
"hoho"
> "hoho" `mappend` mempty
"hoho"
> "a" `mappend` "b" `mappend` "c"
"abc"
> "a" `mappend` ("b" `mappend` "c")
"abc"

mempty 是幺元，mappend 也滿足結合律，所以 List 是合格的 Monoid 實例

P.S. 想知道 mempty 具體是什麼的話，這樣做：

> mempty :: [a]
[]
> mempty :: Ordering
EQ
> mempty :: ()
()

注意，需要給 mempty 指定一個具體類型（比如 [a] 或者 [Int] :: *，而不是 [] :: * -> *）

Product 與 Sum

開頭幺元部分提到過加法單位元和乘法單位元，同時它們也滿足結合律，所以，數值運算存在兩個幺半群，分別是加法與幺元 0，以及乘法與幺元 1

換句話說，Num 可以有兩種不同的 Monoid 實現，分別是二元函數 + 與幺元 0，以及二元函數 * 與幺元 1。又面臨這種場景了，所以像創造 ZipList 一樣，我們創造出了 Sum 和 Product 類（位於 Data.Monoid）：

newtype Product a = Product { getProduct :: a }
  deriving (Eq, Ord, Read, Show, Bounded, Generic, Generic1, Num)
newtype Sum a = Sum { getSum :: a }
    deriving (Eq, Ord, Read, Show, Bounded, Generic, Generic1, Num)

P.S. 關於 ZipList 與 newtype 的過往，見 [newtype_Haskell 筆記 8](/articles/newtype-haskell 筆記 8/)

Product 的 Monoid 實現如下：

instance Num a => Semigroup (Product a) where
  (<>) = coerce ((*) :: a -> a -> a)

instance Num a => Monoid (Product a) where
  mempty = Product 1

幺元是 Product 1，二元函數是 coerce ((*) :: a -> a -> a)，其中 coerce 用於類型轉換（具體見 Data.Coerce），相當於：

Product x `mappend` Product y = Product (x * y)

定義在 Num 上，所以幺元的值與具體類型有關：

> getProduct (mempty :: (Product Int))
1
> getProduct (mempty :: (Product Double))
1.0

Sum 的實現與 Product 類似：

instance Num a => Semigroup (Sum a) where
  (<>) = coerce ((+) :: a -> a -> a)

instance Num a => Monoid (Sum a) where
  mempty = Sum 0

試玩一下：

> getSum $ Sum 3 `mappend` (mconcat $ map Sum [1, 2, 3])
9

Any 與 All

與 Num 類似，Bool 值也存在兩個幺半群：|| 運算與幺元 False，&& 運算與幺元 True：

-- || 運算與幺元 False
newtype Any = Any { getAny :: Bool }
  deriving (Eq, Ord, Read, Show, Bounded, Generic)

instance Semigroup Any where
  (<>) = coerce (||)

instance Monoid Any where
  mempty = Any False

-- && 運算與幺元 True
newtype All = All { getAll :: Bool }
  deriving (Eq, Ord, Read, Show, Bounded, Generic)

instance Semigroup All where
  (<>) = coerce (&&)

instance Monoid All where
  mempty = All True

Any 與 All 同樣位於 Data.Monoid

Ordering

Ordering 類型定義相當簡單：

data Ordering = LT | EQ | GT

對應的 Monoid 實現如下：

instance Semigroup Ordering where
  LT <> _ = LT
  EQ <> y = y
  GT <> _ = GT

instance Monoid Ordering where
  mempty             = EQ

P.S. 與前面提到的其它 Monoid instances 不同，這裡的 mappend 是現做的，而不是直接用的現有函數（之前都是拿現有函數驗證一下，看有沒有幺半群特性）

這個函數的行為是，運算結果取左邊的操作數，除非左邊是 EQ（此時取右邊的）。看起來有些奇怪，可以理解成字符串（按字典序）比較，比如 compare "ab" "am" 的比較結果是 LT，LT <> _ = LT 就是說如果當前比較結果是 LT 的話，接著往後比結果仍是 LT，例如 compare "absolute" "america"。類似的，EQ <> y = y 表示當前結果是 EQ 的話，剩餘部分的比較結果就是最終結果，GT <> _ = GT 表示當前結果是 GT 的話，後面是什麼都不重要，最終結果一定是 GT

Maybe

instance Semigroup a => Semigroup (Maybe a) where
  Nothing <> b       = b
  a       <> Nothing = a
  Just a  <> Just b  = Just (a <> b)

instance Semigroup a => Monoid (Maybe a) where
  mempty = Nothing

P.S. 注意這裡的類型約束，要求 a 是個 Semigroup，用來保證 Just a <> Just b = Just (a <> b) 可以正常運算

所以，Maybe 的幺元是 Nothing，運算也是現做的，但比較取巧，兩個 Just a 的運算結果是對內容做運算，再裝進 Just，所以要求內容也支持這種運算（<>），例如：

> Just (Sum 2) `mappend` Just (Sum 3)
Just (Sum {getSum = 5})
> Just [1, 2] `mappend` Just [3, 4]
Just [1,2,3,4]

如果內容不支持 <> 運算，就無法進行 Maybe 的運算：

> Just 2 `mappend` Just (3 :: Int)

<interactive>:195:1: error:
    ? No instance for (Monoid Int) arising from a use of 'mappend'

四、Foldable 與 Monoid

Monoid 實例都支持 mappend 行為，可以理解為"疊加"，把兩個 Monoid 實例通過運算變成一個 Monoid 實例，此外，還支持"折疊"（mconcat），能把一組 Monoid 實例從頭到尾"疊加"起來，從而"折疊"成一個 Monoid 實例

一組東西能被"折疊"起來形成一個東西，這個東西就是"可折疊的"，即 Foldable：

class Foldable t where
  {-# MINIMAL foldMap | foldr #-}
  foldMap :: Monoid m => (a -> m) -> t a -> m
  foldr :: (a -> b -> b) -> b -> t a -> b

（摘自 Data.Foldable）

P.S. Foldable 位於 Data.Foldable 模塊，函數名與 Prelude 中的 List 函數名有衝突，所以一般通過別名引入，例如：

import qualified Data.Foldable as Foldable

根據 class 定義，只需要實現 foldMap 或 foldr 即可成為 Foldable 實例，從類型聲明來看，foldMap 顯然是面向 Monoid 的，而 foldr 則是更一般的 fold 接口

具體來看，foldMap 所做的事情就是用函數 a -> m 對 Foldable 結構（t a）做映射，得到內容是一組 Monoid 組成的 Foldable 結構，再通過 mconcat（或者說是 mappend）把這一組 Monoid 折疊成一個 Monoid 並返回

實際應用

實現 Foldable 有什麼實際意義呢？看個示例：

module BTree
( Tree(..)
, singleton
, add
, fromList
) where

import Data.Monoid
import Data.Foldable

data Tree a = EmptyTree | Node a (Tree a) (Tree a) deriving (Show, Read, Eq)

singleton x = Node x EmptyTree EmptyTree

add x EmptyTree = singleton x
add x (Node a left right)
  | x == a = Node a left right
  | x > a = Node a left (add x right)
  | x < a = Node a (add x left) right

fromList xs = foldr add EmptyTree xs

這是個自定義的二叉樹類型（實際上是個二叉搜索樹，最簡單粗暴的那種，姑且當二叉樹用吧），具有基本的二叉樹構造功能（singleton、add 與 fromList），給它實現個 Monoid 接口：

instance Monoid a =>  Monoid (Tree a) where
  mempty = EmptyTree
  a `mappend` EmptyTree = a
  EmptyTree `mappend` b = b
  (Node x xl xr) `mappend` (Node y yl yr) = Node (x `mappend` y) (xl `mappend` yl) (xr `mappend` yr)

注意，我們要求 Tree a 的 a 也是個 Monoid 實例，因為需要對 Node 的內容做 mappend。這與前面提到 Maybe 的 Monoid 實現類似

試一下 Monoid laws：

> let nodeA = Node (Sum 1) (singleton (Sum 2)) EmptyTree
> let nodeB = Node 5 (Node 3 (singleton 1) (singleton 6)) (Node 9 (singleton 8) (singleton 10))
> let nodeC = singleton (Sum 6)
> nodeA `mappend` nodeB `mappend` nodeC
Node (Sum {getSum = 12}) (Node (Sum {getSum = 5}) (Node (Sum {getSum = 1}) EmptyTree EmptyTree) (Node (Sum {getSum = 6}) EmptyTree EmptyTree)) (Node (Sum {getSum = 9}) (Node (Sum {getSum = 8}) EmptyTree EmptyTree) (Node (Sum {getSum = 10}) EmptyTree EmptyTree))
> nodeA `mappend` (nodeB `mappend` nodeC)
Node (Sum {getSum = 12}) (Node (Sum {getSum = 5}) (Node (Sum {getSum = 1}) EmptyTree EmptyTree) (Node (Sum {getSum = 6}) EmptyTree EmptyTree)) (Node (Sum {getSum = 9}) (Node (Sum {getSum = 8}) EmptyTree EmptyTree) (Node (Sum {getSum = 10}) EmptyTree EmptyTree))

3 棵樹結構如下：

-- nodeA
1
  2
  空
-- nodeB
5
  3
    1
    6
  9
    8
    10
-- nodeC
6

mappend 結果為：

12
  5
    1
    6
  9
    8
    10

實際上就是對應位置求和，空節點充當 0 的角色。回想一下，我們是如何表達"求和"這個意圖的？

"求和"是通過 Sum 這個 Monoid 實例來表達的，而 Tree 僅僅是一個結構，數值先被 Sum 包一層，添上求和的語義，再填進 Tree 裡，擁有樹的結構含義。好像，是有那麼點意思了

繼續，實現 Foldable 接口，還記得 Foldable 與 Monoid 關係親密，所以很容易讓一類 Monoid 實例變得 foldable：

instance Foldable.Foldable Tree where
  foldMap f EmptyTree = mempty
  foldMap f (Node x l r) = Foldable.foldMap f l `mappend`
                              f x `mappend`
                              Foldable.foldMap f r

大招蓄力完成了，先來個起手式：

let tree = fromList [7, 3, 1, 2, 6, 9, 8, 5]
> getAny $ Foldable.foldMap (\x -> Any $ x == 3) tree
True

造了一棵這樣的樹：

-- tree
5
  2
    1
    3
  8
    6
      空
      7
    9

一句話完成了包含性判斷：getAny $ Foldable.foldMap (\x -> Any $ x == 3) tree。出招太快沒看清？慢動作分解一下：

0. 映射函數 (\x -> Any $ x == 3) 把輸入值與 3 比較相等性，把比較結果裝入 Any

1. 自底向上遍歷 tree，用映射函數轉換每個節點上的數值，遇到空節點就包成 mempty，形成一棵 Monoid 樹（Any 樹）

2. 折疊 Any 樹，具體做法是自底向上進行 左 mappend 中 mappend 右 運算，Any 的 mappend 就是對值做或運算（||），遇到 mempty 就對應成 Any False，走到樹根時，���算結果就是 Any True

3. getAny 取出折疊結果 True

P.S. 注意，生成 Any 樹與遍歷折疊是在一次遍歷中同時進行的，並不是遍歷兩遍（第一遍做映射，第二遍折疊），上面拆開看只是便於理解

起手式之後，大招來了：

> Foldable.foldMap (\x -> [x]) tree
[1,2,3,5,6,7,8,9]

等等，發生了什麼？

一句話把樹轉數組，而且，還偷偷排了個序。好吧，是有點誇張了，排序是二叉搜索樹做的（fromList 的時候 add 建樹），所以只是把樹轉數組，具體如下：

0. 映射函數 (\x -> [x]) 把輸入的值裝進 List（收集起來）

1. 自底向上遍歷 tree，用映射函數轉換每個節點上的數值，遇到空節點就包成 mempty，形成一棵 List 樹

2. 折疊 List 樹，具體做法是自底向上進行 左 mappend 中 mappend 右 運算，List 的 mappend 就是連接（++），遇到 mempty 就對應成 []，走到樹根時，運算結果就是 [樹上所有元素]

3. 直接輸出折疊結果，就是 [樹上所有元素]

一句話完成包含性判斷，一句話完成樹上元素收集，相當驚艷的操作

P.S. 要對樹求和、求積、過濾元素呢？太容易了：

> getSum $ Foldable.foldMap Sum tree
41
> getProduct $ Foldable.foldMap Product tree
90720
> Foldable.foldMap (\x -> if x > 5 then [x] else []) tree
[6,7,8,9]

五、群、半群與幺半群

從數學含義上看，都是集合與二元運算形成的代數結構：

• 半群：集合 S 及其上的二元運算 ·:S×S→S。若 · 滿足結合律，即：∀x,y,z∈S，有 (x·y)·z=x·(y·z)，則稱有序對 (S,·) 為半群

• 幺半群：集合 M 及其上的二元運算 *: M × M → M，該運算滿足結合律，並且幺元也在集合裡

• 群：群是一個集合 G，連同一個運算 ·，它結合任何兩個元素 a 和 b 而形成另一個元素，記為 a·b，要求該運算滿足結合律和封閉性，集合裡要有幺元，並且每個元素都有逆元

P.S. 逆元是說，對於每個 G 中的 a，存在 G 中的一個元素 b 使得 a·b = b·a = e，這裡的 e 是單位元

簡單地講：

• 半群：特定集合以及定義在該集合上的二元運算，該運算滿足封閉性（二元運算結果仍在集合裡）和結合率（左結合結果等於右結合結果）

• 幺半群：含有幺元的半群

• 群：每個元素都有對應逆元的幺半群

從一般到特殊，幺半群介於半群和群之間，群最特殊（有點不符合直覺）。反過來看，半群是對幺半群的泛化（半群不要求有幺元），也是對群的泛化（半群不要求每個元素都有逆元）：

A semigroup generalizes a monoid in that there might not exist an identity element. It also (originally) generalized a group (a monoid with all inverses) to a type where every element did not have to have an inverse, thus the name semigroup.

從語法角度來看，三者關係如下：

class Semigroup a where
  -- 滿足結合律的運算（同時也滿足封閉性）
  (<>) :: a -> a -> a

class Semigroup a => Monoid a where
  -- 幺元
  mempty  :: a
  -- 滿足結合律的運算（同時也滿足封閉性）
  mappend :: a -> a -> a
  mappend = (<>)

class Monoid m => Group m where
  -- 求逆元的運算
  invert :: m -> m

Semigroup（半群）是個接口（typeclass），描述了特定集合，以及定義在該集合上的一種運算，該運算滿足結合律，所有 Semigroup 實例都具有這種行為特徵

Monoid（幺半群）也是個接口，描述了特定集合，以及定義在該集合上的一種滿足結合律的運算，並且幺元也在集合裡

Group（群）同樣是接口，描述了特定結合，以及定義在該集合上的一種滿足結合律的運算，不僅有幺元，而且每個元素都有逆元

P.S. 另外，幺半群與範疇論有一定關聯，見 和範疇論的關係

參考資料

• semigroups: Anything that associates