泛函编程（21）－泛函数据类型－Monoid
泛函编程（21）－泛函数据类型－Monoid
Monoid是数学范畴理论（category theory）中的一个特殊范畴（category）。不过我并没有打算花时间从范畴理论的角度去介绍Monoid，而是希望从一个程序员的角度去分析Monoid以及它在泛函编程里的作用。从这个思路出发我们很自然得出Monoid就是一种数据类型，或者是一种在泛函编程过程中经常会遇到的数据类型：当我们针对List或者loop进行一个数值的积累操作时我们就会使用到Monoid。实际上Monoid就是List[A] => A的抽象模型。好了，我们就不要越描越黑了吧，还是看看Monoid的定义吧：
Monoid由以下条件组成：
1、一个抽象类型A
2、一个二元结合性函数（binary associative function），对传入的两个A类参数进行操作后产生一个A类型结果
3、一个恒等值（identity）
由于Monoid是一个数学类型，它的二元操作函数必须遵循一些定律：
1、结合性（associativity）：op(a,op(b,c)) = op(op(a,b),c)：这个定律是函数组合（function composition）不可缺的条件
2、二元函数参数中如果有一个是恒等值时操作结果为另一个参数：op(identity,v) = v
我们可以用编程语言来描述Monoid:
1 trait Monoid[A] { //被封装的类型A
2 def op(a1: A, a2: A): A //二元函数
3 val zero: A //恒等值identity
4 }我们用scala的特质（trait）描述了Monoid。它就是一个抽象的数据类型。
既然Monoid trait是个抽象类型，那么我们可以试着创建几个基础类型的Monoid实例：
1 val stringConcatMonoid = new Monoid[String] {
2 def op(s1: String, s2: String) = s1 + s2
3 val zero = "" // op(zero,s2) = "" + s2 = s2 恒等值定律
4 } //> stringConcatMonoid : ch10.ex1.Monoid[String] = ch10.ex1$$anonfun$main$1$$an
5 //| on$1@3581c5f3
6 val intAdditionMonoid = new Monoid[Int] {
7 def op(i1: Int, i2: Int) = i1 + i2
8 val zero = 0
9 } //> intAdditionMonoid : ch10.ex1.Monoid[Int] = ch10.ex1$$anonfun$main$1$$anon$4
10 //| @340f438e
11 val intMultiplicationMonoid = new Monoid[Int] {
12 def op(i1: Int, i2: Int) = i1 * i2
13 val zero = 1
14 } //> intMultiplicationMonoid : ch10.ex1.Monoid[Int] = ch10.ex1$$anonfun$main$1$$
15 //| anon$5@30c7da1e可以看出，这几个Monoid实例都符合Monoid定律。那我们可以先试着用用。上面提到Monoid最适合一串值的累加操作List[A] => A，我们可以对List[A]进行操作示范：
1 def reduce[A](as: List[A])(m: Monoid[A]): A = {
2 as match {
3 case Nil => m.zero
4 case h::t => m.op(h, reduce(t)(m))
5 }
6 } //> reduce: [A](as: List[A])(m: ch10.ex1.Monoid[A])AMonoid m是个抽象类型，m.zero和m.op()的具体意义要看Monoid的实例了:
1 reduce(List(1,2,3))(intAdditionMonoid) //> res3: Int = 6
2 reduce(List("this is ","the string", " monoid"))(stringConcatMonoid)
3 //> res4: String = this is the string monoid对List[A]的具体累加处理是按照intAdditionMonoid和stringConcatMonoid的二元函数功能进行的。看来Monoid特别适用于List类型的循环操作。可以把reduce函数的参数拓展开来看看：
1 reduce[A](as: List[A])(zero: A)(op: (A,A) => A) : A这个类型款式跟折叠算法的类型款式非常相似：
1 def foldRight[A,B](as: List[A])(z: B)(f: (A,B) => B): B
2 如果类型B=类型A
3 def foldRight[A](as: List[A])(z: A)(f: (A,A) => A): A实际上我们可以直接用上面的Monoid实例运算折叠算法：
1 List(1,2,3).foldRight(intAdditionMonoid.zero)(intAdditionMonoid.op)
2 //> res3: Int = 6
3 List("this is ","the string", " monoid").foldLeft(stringConcatMonoid.zero)(stringConcatMonoid.op)
4 //> res4: String = this is the string monoid左右折叠算法都可以。Monoid的结合性定律（associativity law）可以使List元素运算左右路径相等。
下面我们再试着增加几个Monoid实例：
1 def optionMonoid[A] = new Monoid[Option[A]] {
2 def op(o1: Option[A], o2: Option[A]): Option[A] = o1 orElse o2
3 val zero = None // op(zero, o1)= None orElse o2 = o2
4 } //> optionMonoid: [A]=> ch10.ex1.Monoid[Option[A]]{val zero: None.type}
5 def listConcatMonoid[A] = new Monoid[List[A]] {
6 def op(l1: List[A], l2: List[A]) = l1 ++ l2
7 val zero = Nil
8 } //> listConcatMonoid: [A]=> ch10.ex1.Monoid[List[A]]{val zero: scala.collection.
9 //| immutable.Nil.type}
10 val booleanOrMonoid = new Monoid[Boolean] {
11 def op(b1: Boolean, b2: Boolean) = b1 || b2
12 val zero = false
13 } //> booleanOrMonoid : ch10.ex1.Monoid[Boolean] = ch10.ex1$$anonfun$main$1$$anon
14 //| $6@5b464ce8
15 val booleanAndMonoid = new Monoid[Boolean] {
16 def op(b1: Boolean, b2: Boolean) = b1 && b2
17 val zero = true
18 } //> booleanAndMonoid : ch10.ex1.Monoid[Boolean] = ch10.ex1$$anonfun$main$1$$an
19 //| on$7@57829d67
20 def endoComposeMonoid[A] = new Monoid[A => A] {
21 def op(f: A => A, g: A => A) = f compose g
22 val zero = (a: A) => a // op(zero, g: A => A) = zero compose g = g
23 } //> endoComposeMonoid: [A]=> ch10.ex1.Monoid[A => A]
24 def endoAndThenMonoid[A] = new Monoid[A => A] {
25 def op(f: A => A, g: A => A) = f andThen g
26 val zero = (a: A) => a // op(zero, g: A => A) = zero andThen g = g
27 } //> endoAndThenMonoid: [A]=> ch10.ex1.Monoid[A => A]
28 //计算m的镜像Monoid
29 def dual[A](m: Monoid[A]) = new Monoid[A] {
30 def op(x: A, y: A) = m.op(y,x) //镜像op即时二元参数位置互换
31 val zero = m.zero
32 } //> dual: [A](m: ch10.ex1.Monoid[A])ch10.ex1.Monoid[A]
33 def firstOfDualOptionMonoid[A] = optionMonoid[A]
34 //> firstOfDualOptionMonoid: [A]=> ch10.ex1.Monoid[Option[A]]{val zero: None.ty
35 //| pe}
36 def secondOfDualOptionMonoid[A] = dual(firstOfDualOptionMonoid[A])
37 //> secondOfDualOptionMonoid: [A]=> ch10.ex1.Monoid[Option[A]]以上几个增加的Monoid实例中endoComposeMonoid和endoAndThenMonoid可能比较陌生。它们是针对函数组合的Monoid。
还是回到对List[A]的累加操作。下面这个函数用Monoid对List[A]元素A进行累加操作：
1 def concatenate[A](l: List[A], m: Monoid[A]): A = {
2 l.foldRight(m.zero){(a,b) => m.op(a,b)}
3 } //> concatenate: [A](l: List[A], m: ch10.ex1.Monoid[A])A
4 concatenate[Int](List(1,2,3),intAdditionMonoid) //> res0: Int = 6那么如果没有List[A]元素A类型Monoid实例怎么办？我们可以加一个函数：
1 def foldMap[A,B](as: List[A])(m: Monoid[B])(f: A => B): B如果我们有一个函数可以把A类转成B类 A => B，那我们就可以使用Monoid[B]了：
1 def foldMap[A,B](as: List[A])(m: Monoid[B])(f: A => B): B = {
2 as.foldRight(m.zero)((a,b) => m.op(f(a),b))
3 }说明一下：foldRight的类型款式：foldRight[A,B](as: List[A])(z: B)(g: (A,B) => B): B。其中(A,B) => B >>> (f(A),B) => B >>> (B,B) => B 就可以使用 Monoid[B].op(B,B)=B了。我们也可以用foldLeft来实现foldMap。实际上我们同样可以用foldMap来实现foldRight和foldLeft:
1 def foldRight[A,B](la: List[A])(z: B)(f: (A,B) => B): B
2 def foldLeft[A,B](la: List[A])(z: B)(f: (A,B) => B): B
3 def foldMap[A,B](as: List[A])(m: Monoid[B])(f: A => B): BfoldRight和foldLeft的f函数是(A,B) => B，如果用curry表达：A => (B => B)，如果能把 A => ? 转成 B => B，那么我们就可以使用endoComposeMonoid[B].op(f: B => B, g: B => B): B。
1 def foldRight[A,B](as: List[A])(z: B)(f: (A,B) => B): B = {
2 foldMap(as)(endoComposeMonoid[B])(a => b => f(a,b))(z)
3 }说明：foldMap需要f: A => B, foldRight有 (A,B) => B >>> A => B => B >>> f(a)(b) => b >>> f(a,b)(z) >>> f(b)(b)
foldLeft是从左边开始折叠，只需要采用endoComposeMonoid的镜像Monoid把op参数位置调换就行了：
1 def foldLeft[A,B](as: List[A])(z: B)(f: (A,B) => B): B = {
2 foldMap(as)(dual(endoComposeMonoid[B]))(a => b => f(a,b))(z)
3 }在这节我们简单的介绍了Monoid及它的一些初级类型的实例使用方式。我们也把Monoid代数模型的一面：函数的互通转换及组合稍微示范了一下。在下一节我们将会把Monoid在实际编程中的应用以及Monoid的深度抽象做些讨论。