Monoid_Haskell笔记9
一.幺元
数学世界里,0是加法单位元,1是乘法单位元(identity element),例如:
> 0 + 33> 3 + 03> 1 * 33> 3 * 13
二者的共同点是参与运算,但不改变另一个操作数:
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 = xx `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 :: OrderingEQ> 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:
-- ||运算与幺元Falsenewtype Any = Any { getAny :: Bool } deriving (Eq, Ord, Read, Show, Bounded, Generic)instance Semigroup Any where (<>) = coerce (||)instance Monoid Any where mempty = Any False-- &&运算与幺元Truenewtype All = All { getAll :: Bool } deriving (Eq, Ord, Read, Show, Bounded, Generic)instance Semigroup All where (<>) = coerce (&&)instance Monoid All where mempty = All TrueAny与All同样位于Data.Monoid
Ordering
Ordering类型定义相当简单:
data Ordering = LT | EQ | GT
对应的Monoid实现如下:
instance Semigroup Ordering where LT <> _ = LT EQ <> y = y GT <> _ = GTinstance 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
Maybeinstance 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) whereimport Data.Monoidimport Data.Foldabledata Tree a = EmptyTree | Node a (Tree a) (Tree a) deriving (Show, Read, Eq)singleton x = Node x EmptyTree EmptyTreeadd x EmptyTree = singleton xadd 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) rightfromList 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` nodeCNode (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棵树结构如下:
-- nodeA1 2 空-- nodeB5 3 1 6 9 8 10-- nodeC6
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) treeTrue
造了一棵这样的树:
-- tree5 2 1 3 8 6 空 7 9
一句话完成了包含性判: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 tree41> getProduct $ Foldable.foldMap Product tree90720> 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 -> aclass 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
更多相关文章
- 为什么推荐使用for-each而不是for循环遍历元素?
- 函数式编程中如何处理副作用?
- 帆软报表自定义函数-取json数据
- 函数和递归
- java的getClass()函数
- 函数的学习
- java多线程(3)Thread构造函数解析
- Selenium3自动化测试【12】元素定位认知
- JavaScript 测试教程–part 3:测试 props,挂载函数和快照测试[每日