当前位置:必发365电子游戏 > 编程 > Monad正是泛函编程中最概括通用的数据模型,Monoid是数学范畴理论(category
Monad正是泛函编程中最概括通用的数据模型,Monoid是数学范畴理论(category
2019-12-19

    Monoid是数学范畴理论(category theory)中的二个新鲜范畴(category)。然则作者并不曾计划花时间从规模理论的角度去介绍Monoid,而是希望从一个程序猿的角度去剖判Monoid以至它在泛函编制程序里的法力。从这些思路出发我们很自然得出Monoid便是意气风发种数据类型,也许是风姿罗曼蒂克种在泛函编制程序进度中日常会碰着的数据类型:当大家本着List或然loop举行三个数值的堆集操作时大家就可以选择到Monoid。实际上Monoid正是List[A] => A的虚幻模型。好了,大家就无须越描越黑了呢,照旧看看Monoid的定义吧:

简易来讲:Monad正是泛函编制程序中最总结通用的数据模型。它不止含有了全部功底项目(primitive types)的泛函行为及操作,何况别的高阶类大概自定义类后生可畏旦有所Monad脾性就足以与其他类型的Monad实例相符在泛函编制程序中联手提供生龙活虎套通用的泛函编制程序方式。所以有人把泛函编制程序视作Monadic Programming也不为过之。那么,具体什么是Monad呢?

Monoid由以下原则构成:

在前方我们议论过Monoid,大家说过它是一个极度的框框,全体数据类型的Monoid实例都一齐具备生机勃勃套Monoid特有的操作及信守豆蔻梢头套Monoid行为定律。那样大家得以把Monoid视为一个架空数据模型,在泛函算法中使用极其的Monoid实例就足以直达预期的成效而无需修正算法。那么可以说Monad正是三个比Monoid更囊括、更抽象、覆盖面积更广的高阶数据类型了。

1、八个虚幻类型A

其实在规划泛函库组件(combinator)时,大家会尽量幸免重复编码,完毕情势就是把通用或共性的操作抽出出来造成一些新的高阶类型(higher types卡塔尔国,也正是新的虚幻类型(Abstraction)。这样大家能够在差别的构件库中对同类操作协同利用那一个通用的项目了。让我们先看看以下的八个架空进度:

2、二个二元结合性函数(binary associative function),对传播的三个A类参数进行操作后爆发叁个A类型结果

大家在眼下议论过局部数据类型。它们都有叁个一同的函数:map

3、四个恒等值(identity)

1   def map[A,B](la: List[A])(f: A => B): List[B]2   def map[A,B](oa: Option[A])(f: A => B): Option[B]3   def map[A,B](pa: Par[A])(f: A => B): Par[B]4   def map[A,B](sa: State[S,A])(f: A => B): State[S,B]

由于Monoid是一个数学类型,它的二元操作函数必得比照一些定律:

那多少个函数都独具莫大雷同的款式(signature),差别的是它们施用的求实数据类型。那么大家应该能够把那么些map抽象出来:通过增添二个高阶类型Functor,用它来回顾完结map:

1、结合性(associativity):op(a,op(b,c卡塔尔(英语:State of Qatar)卡塔尔国= op(op(a,b卡塔尔国,c卡塔尔(قطر‎:那一个定律是函数组合(function composition)不可缺的法则

1   trait Functor[F[_]] {2       def map[A,B](f: A => B): F[B]3   }

2、二元函数参数中黄金年代旦有一个是恒等值时操作结果为另二个参数:op(identity,v)= v

在意在上头的map例子里的选用类型都是高阶类型;List[A]、Option[A]、Par[A] ...都是F[A]这种样式。所以Functor的类参数是F[_],即: Functor[List], Functor[Option], Functor[Par] ...,这里面F[_]就是F[A],A能够是此外类型。大家得以设计一个List的Functor实例:

咱俩能够用编制程序语言来说述Monoid:

1   object ListFunctor extends Functor[List] {2       def map[A,B](la: List[A])(f: A => B): List[B] = la map f3   }
1   trait Monoid[A] {                //被封装的类型A
2       def op(a1: A, a2: A): A   //二元函数
3       val zero: A               //恒等值identity
4   }

把F换到List就足以了。此外类型的Functor实例:

作者们用scala的特质(trait)描述了Monoid。它就是七个硕大而无当的数据类型。

1  object OptionFunctor extends Functor[Option] {2       def map[A,B](oa: Option[A])(f: A => B): Option[B] = oa map f3   }4   object StreamFunctor extends Functor[Stream] {5       def map[A,B](sa: Stream[A])(f: A => B): Stream[B] = sa map f6   }

既然如此Monoid trait是个抽象类型,那么大家得以试着创建多少个底子项目标Monoid实例:

大家只需求对两样档期的顺序的操作使用相应的Functor实例就足以了:

 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
1 ListFunctor.map(List{_ + 10}             //> res0: List[Int] = List(11, 12, 13)2  OptionFunctor.map{_ + 10}               //> res1: Option[Int] = Some

能够见见,这多少个Monoid实例都切合Monoid定律。那大家得以先试着用用。上边提到Monoid最切合生龙活虎串值的拉长操作List[A] => A,我们得以对List[A]开展操作示范:

操作形式是相像相符的。不过讲实在话,上面包车型大巴这个实例都不要紧意思,因为使用的现实性项目笔者就扶持map。也正是说List,Option等自作者就是Functor。换句话讲正是:它们都可以map,所以都以Functor。看看上面怎么接纳Functor吧:

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
1   trait Functor[F[_]] {2       def map[A,B](f: A => B): F[B]3       def unzip[A,B](fab: F[: (F[A],F[B]) = {4         {a => a._1},map{a => a._2})5       }6   }

Monoid m是个抽象类型,m.zero和m.op(卡塔尔国的切实意思要看Monoid的实例了:

在此个例子中自己刻意把全体trait声明放了进来。这里的map依然抽象的,意味着还亟需在切实可行的品类实例里完结。大家在设计unzip时是针对F的。在trait Functor里大家得以肯定F[]支撑map,所以大家本事够达成unzip函数的兑现。那就是空虚的功用。当我们利用unzip时只要明确传入的参数fab是Functor就行了。那样unzip能够支撑全数封装的Functor:

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
1 ListFunctor.unzip(List,,    //> res0: (List[Int], List[Int]) = (List,List(10, 20, 30))2  OptionFunctor.unzip(Some                 //> res1: (Option[Int], Option[Int]) = ,Some

对List[A]的切实可行累计管理是依照intAdditionMonoid和stringConcatMonoid的二元函数效率进行的。看来Monoid特别适用于List类型的大循环操作。能够把reduce函数的参数实行开来寻访:

讲到这里,那些Functor跟Monad有哪些关联吧?但是这种肤浅的目标和情势或然跟Monad有如何关系呢?那么再往下推导:在事情未发生前的数据类型设计里大家曾想遭受比较多map2函数:

1   reduce[A](as: List[A])(zero: A)(op: (A,A) => A) : A
1  def map2[A,B,C](la: List[A], lb: List[B]) => C): List[C] = {2       la flatMap {a => lb map { b => f }}3   }4   def map2[A,B,C](oa: Option[A], ob: Option[B]) => C): Option[C] = {5       oa flatMap{a => ob map { b => f }}6   }7   def map2[A,B,C](pa: Par[A], pb: Par[B]) => C): Par[C] = {8       pa flatMap{a => pb map { b => f }}9   }

其黄金时代类型款式跟折叠算法的花色款式非常相近:

看看那个map2函数:不但款式相近,完结格局也是一模一样的。不一致的大概实际使用受体的数据类型。看来大家还是因为种种数据类型的两样而重复编写了map2组件。我们理应想方法三遍实现map2后让具备数据类型实例都得以行使,从而深透幸免重复编码。能够料定的是这一个艺术一定跟共性抽象有关。

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

在前边那个章节的座谈中大家直接针对少数数据类型的特征设计最大旨的操作函数或机件。因为各样数据类型的两样大家重新编写了map2组件。将来大家看见map2是足以用flatMap和map来完结的。那么flatMap和map正是最宗旨最通用的零器件了呢?事实上map能够用flatMap和unit来完毕:

实在我们得以一向用地点的Monoid实例运算折叠算法:

1   def map[A,B](pa: Par[A])(f: A => B): Par[B] = {2       flatMap { a => unit }3   }
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

那就是说大家就先采取unit + flatMap作为最中央组件。当然,早前面包车型地铁推理中大家得以吸收unit + flatMap基本组件比Functor更抽象,因为map能够用unit + flatMap来落成。我们称这些抽象模型为Monad,它三回九转了Functor的特点,是Functor,因为Monad能够map。我们得以先用trait来发布Monad:

反正折叠算法都得以。Monoid的结合性定律(associativity law)能够使List成分运算左右门路相等。

 1  trait Monad[M[_]] extends Functor[M] { 2       def unit[A]: M[A] 3       def flatMap[A,B](f: A => M[B]): M[B] 4       def map[A,B](f: A => B): M[B] = { 5           flatMap{a => unit} 6       } 7       def map2[A,B,C](ma: M[A], mb: M[B]) => C): M[C] = { 8           flatMap { a => map{ b => f }} 9       }10   }

上边我们再试着扩大多少个Monoid实例:

在此个trait里unit和flatMap是虚幻的。这表示各个型的Monad实例必需落到实处unit和flatMap,并且会自动获取map和map2几个零件。

 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]]
 1  val listMonad = new Monad[List] { 2      def unit[A] = List 3      def flatMap[A,B](la: List[A])(f: A => List[B]): List[B] = { 4           la flatMap f 5      } 6   }                                               //> listMonad  : ch11.monad.Monad[List] = ch11.monad$$anonfun$main$1$$anon$1@253 7                                                   //| 0c12 8    9   listMonad.map(List{_ + 10}              //> res0: List[Int] = List(11, 12, 13)10   listMonad.map2,List{ => List}11                                                   //> res1: List[List[Int]] = List(List, List, List, List12                                                   //| 

如上几个增添的Monoid实例中endoComposeMonoid和endoAndThenMonoid大概相比较目生。它们是指向性函数组合的Monoid。

真的大家从listMonad中自动获取了可用的map和map2.

要么回到对List[A]的充分操作。上面那些函数用Monoid对List[A]成分A实行增多操作:

optionMonad是那般的:

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
1  val optionMonad = new Monad[Option] {2       def unit[A] = Some3       def flatMap[A,B](oa: Option[A])(f: A => Option[B]): Option[B] = {4           oa flatMap f5       }6   }                                               //> optionMonad  : ch11.monad.Monad[Option]{def unit[A]: Some[A]} = ch11.m7                                                   //| onad$$anonfun$main$1$$anon$2@4e04a7658   optionMonad.map{a => a + 10}           //> res2: Option[Int] = Some9   optionMonad.map2,Some{_ + _}        //> res3: Option[Int] = Some

那么只要未有List[A]要素A类型Monoid实例怎么做?大家能够加二个函数:

现行反革命我们就像能够说其余能够flatMap(具有flatMap函数)的数据类型都以Monad。

1 def foldMap[A,B](as: List[A])(m: Monoid[B])(f: A => B): B

我们能够再加上一下现行反革命的Monad组件库,扩大加些共用组件,使Monad抽象模型能更满含实用些:

假定大家有多个函数能够把A类转成B类 A => B,那大家就足以应用Monoid[Monad正是泛函编程中最概括通用的数据模型,Monoid是数学范畴理论(category。B]了:

 1   trait Monad[M[_]] extends Functor[M] { 2       def unit[A]: M[A] 3       def flatMap[A,B](f: A => M[B]): M[B] 4       def map[A,B](f: A => B): M[B] = { 5           flatMap{a => unit} 6       } 7       def map2[A,B,C](ma: M[A], mb: M[B]) => C): M[C] = { 8           flatMap { a => map{ b => f }} 9       }10       def sequence[A](lm: List[M[A]]): M[List[A]] = {11           lm.foldRight(unit(Nil: List[A])){ => map2{_ :: _} }12       }13       def travers[A,B](la: List[A])(f: A => M[B]): M[List[B]] = {14           la.foldRight(unit(Nil: List[B])){ => map2{_ :: _}}15       }16       def replicateM[A](n: Int, ma: M[A]): M[List[A]] = {17           if (n == 0) unit18           else map2(ma,replicateM(n-1,ma)) {_ :: _}19       }20       def factor[A,B](ma: M[A], mb: M[B]): M[] = {21           map2{ => }22       }23       def cofactor[A,B](e: Either[M[A],M[B]]): M[Either[A,B]] = {24           e match {25               case Right => map{x => Right}26               case Left => map{x => Left}27           }28       }29   }
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   }

能够观看,大家新扩充的零器件都以以unit

证美素佳儿下: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的吃水抽象做些研究。