新普金娱乐网址


偏函数

WP 数据绑定Visibility

泛函编程(21)-泛函数据类型-Monoid

  • 二月 06, 2019
  • 数学
  • 没有评论

   
Monoid是数学范畴理论(category
theory)中的一个例外范畴(category)。可是自己并没有打算花时间从规模理论的角度去介绍Monoid,而是愿意从一个程序员的角度去分析Monoid以及它在泛函编程里的功用。从那个思路出发大家很自然得出Monoid就是一种数据类型,或者是一种在泛函编程进度中时时会遇上的数据类型:当大家针对List或者loop进行一个数值的聚积操作时大家就会利用到Monoid。实际上Monoid就是List[A]
=>
A的虚幻模型。好了,我们就无须越描越黑了吗,仍旧看看Monoid的概念吧:

不止一遍在网上(包含简书)看到有同行发布意见,认为并不是享有写代码的都能被称作程序员。这么些只满足于完毕公司职责的只配称为码农;必须求协调心爱编程,业余自己切磋算法新技巧,写技术博客的,才是程序员。

Monoid由以下条件构成:

但本身认为,编程那回事,就和原先学校里学习数学一样。有的人由衷热爱数学,在达成课堂上学义务之余,喜欢自己看奥数攻克难点。有的人本身理科头脑好,也没看他在数学上花多少功夫不过考试就是拿高分。有的人成绩平平可是有上进心,想透过看奥数来培植自己的数学思维,争取下次考试战表能有所升高。也有些人自发就不是学数学的料,再怎么努力数学就是学不佳。

1、一个华而不实类型A

自我怀念着,那一个定出程序员与码农标准的人,并非真有多么热爱编程,而是因为现在互连网行业大热,程序员的武力越来越壮大,一些本来和编程毫无相关的人与会个培训班,也能找到工作。那样,程序员这一个职位的水平也就有所下滑了。“他们那何地算程序员,也就是一帮码农罢了。”作为软件工程专业出生的正规军会时有暴发那样的埋怨,也是创制的。

2、一个二元结合性函数(binary
associative
function),对传播的七个A类参数举办操作后发生一个A类型结果

咱俩集团的五个项目COO,胖项目老董爱好体育,常看足球篮球Snow克;瘦项目CEO爱玩赛车和空战那类真实系的模拟游戏;高项目高管爱网络随笔,是个老宅男。他们业余推测都很少会去看技术书籍,也不会去写什么技术博客。不过出于阅历的积淀,技术水平也丝毫不逊色,而且业余生活都很丰盛,各具特色。而自我上班摸鱼也每每逛技术论坛之类的地点,觉得那个有追求的程序员,都觉得自己有性灵,有情怀,结果却形成了一个分外标准化的领域。比如电脑要用mac;手机用诺基亚或者moto;看书得用kindle等等。若是一个世界外的人误入这一个论坛提到windows或者摩托罗拉,则会吸引一片反驳与讽刺。

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的深度抽象做些啄磨。

 

 

 

 

 

 

 

相关文章

No Comments, Be The First!
近期评论
    分类目录
    功能
    网站地图xml地图