泛函编程(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])A

Monoid 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): B

foldRight和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的深度抽象做些讨论。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏C语言及其他语言

[每日一题]山?水!

今天的题解让我们从一个一位老禅师和话引出: 青源惟信禅师讲到自己修佛悟道的历程时说:“老僧三十年前来参禅时,见山是山,见水是水;及至后来亲见知识,有个入处,见...

2698
来自专栏斑斓

编程实践 | Scala亮瞎Java的眼(一)

这是我在11月15日成都OpenParty分享的一个题目,确有标题党的嫌疑。Scala自然不是无所不能,Java也没有这么差劲,我只希望给Java程序员提供另外...

3195
来自专栏web前端教室

javascript 红皮高程(16)

位操作符的内容有些难度,并且也不常用。 从这几天的文章阅读量可以看出来,阅读的人比较少。 但学习这事,从来都是一件艰苦的事情,从来不轻松。 也许难懂,多看几遍就...

1726
来自专栏程序员叨叨叨

8.2 函数重载

Cg 语言支持函数重载(Functon Overlaoding),其方式和 C++基本一致,通过形参列表的个数和类型来进行函数区分。例如:

642
来自专栏Golang语言社区

第十节 Go语言函数方法(上)

干货来了!!!为了让更多的小伙伴喜欢Golang、加入Golang之中来,Golang语言社区发起人彬哥联合业界大牛共同推出了Go语言基础、进阶、提高课程,目前...

472
来自专栏青玉伏案

代码重构(六):代码重构完整案例

无论做什么事情呢,都要善始善终呢。前边连续发表了5篇关于重构的博客,其中分门别类的介绍了一些重构手法。今天的这篇博客就使用一个完整的示例来总结一下之前的重构规则...

2267
来自专栏编程

Python学习笔记1——斐波那契数列

这是一个高中同学问我的问题,本来是用C来写的,正好正在学Python,就用Python重写了一遍当作练习。 下面是题目要求: ? ? 一道很简单的题目,但有些细...

19010
来自专栏斑斓

作为Scala语法糖的设计模式

Scala算是一门博采众家之长的语言,兼具OO与FP的特性,若使用恰当,可以更好地将OO与FP的各自优势发挥到极致;然而问题也随之而来,倘若过分地夸大OO特性,...

3195
来自专栏web前端教室

今天-零基础课的教学事故及全过程

有什么说什么,有错了就要认。 “今天我有个地方讲错了”,“然后我还说提出问题的同学有点过于纠结”。出问题要说清楚,来,事情是这样的。。。 ? 截图一中,点击事件...

1636
来自专栏函数式编程语言及工具

泛函编程(22)-泛函数据类型-Monoid In Action

    在上一节我们讨论了Monoid的结合性和恒等值的作用以及Monoid如何与串类元素折叠算法相匹配。不过我们只示范了一下基础类型(primitive ty...

1776

扫码关注云+社区