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

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结果为：

实际上就是对应位置求和，空节点充当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

造了一棵这样的树：

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

映射函数(\x -> Any $ x == 3)把输入值与3比较相等性，把比较结果装入Any
自底向上遍历tree，用映射函数转换每个节点上的数值，遇到空节点就包成mempty，形成一棵Monoid树（Any树）
折叠Any树，具体做法是自底向上进行左 mappend 中 mappend 右运算，Any的mappend就是对值做或运算（||），遇到mempty就对应成Any False，走到树根时，运算结果就是Any True
getAny取出折叠结果True

P.S.注意，生成Any树与遍历折叠是在一次遍历中同时进行的，并不是遍历两遍（第一遍做映射，第二遍折叠），上面拆开看只是便于理解

起手式之后，大招来了：

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

等等，发生了什么？

一句话把树转数组，而且，还偷偷排了个序。好吧，是有点夸张了，排序是二叉搜索树做的（fromList的时候add建树），所以只是把树转数组，具体如下：

映射函数(\x -> [x])把输入的值装进List（收集起来）
自底向上遍历tree，用映射函数转换每个节点上的数值，遇到空节点就包成mempty，形成一棵List树
折叠List树，具体做法是自底向上进行左 mappend 中 mappend 右运算，List的mappend就是连接（++），遇到mempty就对应成[]，走到树根时，运算结果就是[树上所有元素]
直接输出折叠结果，就是[树上所有元素]

一句话完成包含性判断，一句话完成树上元素收集，相当惊艳的操作

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