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内的abc(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一样,我们创造出了SumProduct类(位于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.关于ZipListnewtype的过往,见newtype_Haskell笔记8

ProductMonoid实现如下:

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

AnyAll同样位于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"的比较结果是LTLT <> _ = 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定义,只需要实现foldMapfoldr即可成为Foldable实例,从类型声明来看,foldMap显然是面向Monoid的,而foldr则是更一般的fold接口

具体来看,foldMap所做的事情就是用函数a -> mFoldable结构(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

这是个自定义的二叉树类型(实际上是个二叉搜索树,最简单粗暴的那种,姑且当二叉树用吧),具有基本的二叉树构造功能(singletonaddfromList),给它实现个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 aa也是个Monoid实例,因为需要对Node的内容做mappend。这与前面提到MaybeMonoid实现类似

试一下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接口,还记得FoldableMonoid关系亲密,所以很容易让一类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。出招太快没看清?慢动作分解一下:

  1. 映射函数(\x -> Any $ x == 3)把输入值与3比较相等性,把比较结果装入Any

  2. 自底向上遍历tree,用映射函数转换每个节点上的数值,遇到空节点就包成mempty,形成一棵Monoid树(Any树)

  3. 折叠Any树,具体做法是自底向上进行左 mappend 中 mappend 右运算,Anymappend就是对值做或运算(||),遇到mempty就对应成Any False,走到树根时,运算结果就是Any True

  4. getAny取出折叠结果True

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

起手式之后,大招来了:

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

等等,发生了什么?

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

  1. 映射函数(\x -> [x])把输入的值装进List(收集起来)

  2. 自底向上遍历tree,用映射函数转换每个节点上的数值,遇到空节点就包成mempty,形成一棵List树

  3. 折叠List树,具体做法是自底向上进行左 mappend 中 mappend 右运算,List的mappend就是连接(++),遇到mempty就对应成[],走到树根时,运算结果就是[树上所有元素]

  4. 直接输出折叠结果,就是[树上所有元素]

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

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,连同一个运算·,它结合任何两个元素ab而形成另一个元素,记为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.另外,幺半群与范畴论有一定关联,见和范畴论的关系

参考资料

发表评论

电子邮件地址不会被公开。 必填项已用*标注

*

code