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

  • 时间:
  • 浏览:3
  • 来源:uu快3计划_uu快3官方_单双

 在上一节大伙 讨论了Monoid的结合性和恒等值的作用以及Monoid怎样与串类元素折叠算法相匹配。不过大伙 只示范了一下基础类型(primitive type)Monoid实例的应用,有些上一节的讨论目的是理论多于实践。在本身节大伙 将把重点放到有些实用综合类型(composite type)Monoid实例及Monoid的抽象表达及函数组合能力。

大伙 看看可不可否实现像折叠算法似的并行算法:

Vector("a rose", "is a", "rose is", "a rose") >>> Map(a -> 3, rose -> 3, is -> 2)

结合前面对并行运算的讨论,大伙 用以下最好的办法应该可不可否实现并行运算吧:

肯能大伙 可不可否使用并行算法励志的话 ,肯定能提升计算时延单位。试想肯能大伙 对另另一个超大文件进行文字数统计肯能寻找最大值哪此的,大伙 可不可否把本身大文件分成若干小文件而且 同去计算后再合计将节省有些计算时间。在现代大数据时代,数据文件不但大而且 是分布在有些服务器上的。也可不可否 Monoid的特殊定律就可不可否使数据处置并行运算,怪怪的匹配大数据处置模式。

大伙 在以前的章节里从前讨论了有些数据形态学 如List,Stream,Tree等。当大伙 前要处置哪此形态学 中封装的元素时通常使用有些算法如折叠算法。本身算法能保存数据形态学 。而且 它们有共通性:都可不可否使用折叠算法。既然有共性,肯定就会有层厚抽象的空间,大伙 可不可否把它们抽象表达成另另一个Foldable[F[_]]:List,Stream,Tree等数据形态学 类型而且F[_];另另一个数据形态学 中封装了有些元素。本身Foldable类型可不可否包含各种历遍算法:

实现本身Monoid实例的应当尽量从类型匹配入手:函数A => B的结果是B;大伙 有Monoid[B],Monoid[B].op(b,b)=>b。

右折叠:op(a,op(b,op(c,d)))

左折叠:op(op(op(a,b),c),d)

在本身例子里大伙 用Option[min,max,ordered]作为当前具体情况并用stateMonoid来处置本身具体情况。foldMapV参数(i => Some(i,i,true))而且标准的 A => B。还记得吗,大伙 增加foldMap本身函数是的目的是肯能元素A也可不可否 Monoid实例,也可不可否 大伙 可不可否用Monoid[B]而且 用A =>B函数把A转成B也能使用Monoid[B]。这里大伙 把 i转成Some(Int,Int,Boolean)。

最后,大伙 试着用mapMergeMonoid实例来实现frequencyMap:计算输入List里的文字发现次数。肯能用另另一个例子来说明励志的话 ,看看下面本身一串文字转成key-value Map:

大伙 看看具体实现:

 Option的foldable与TreeFoldable很像:

这不而且搜索引擎中的索引比重算法吗?大伙 用foldMapV和mapMergeMonoid可不可否并行运算分类整理索引,这否有Monoid的实际应用之一。

可不可否看出TreeFoldable的实现最好的办法与List,Stream等串类数据类型有所不同。这是肯能Tree类型也可不可否 现成的折叠算法。再而且Tree类型也可不可否 空值(也可不可否Leaf, Branch)。本身形态学 暗示着有些类型的Monoid是也可不可否 恒等值的。大伙 统称哪此类型为semigroup。

    Monoid的二元操作函数具有结合形态学 (associativity),与恒等值(identity)同去应用可不可否任意采用左折叠或右折叠算法处置串类元素(List element)而得到同等结果。有些使用Monoid op大伙 可不可否得出左折叠等于右折叠的结论:

啊,本身foldMapV从外表,在类型款式上跟foldMap相同,不同的是内控 具体实现最好的办法;foldMapV循环把目标串进行分半。

没错!

再来另另一个例子:检查一串数字否有有序的:

下面剩下的时间大伙 再讨论有些较僵化 的Monoid:

在历遍过程中大伙 把List每个节点元素值转成一对值 a => (1, a),而且 分别对每个成员实施intAdditionMonoid的op操作。

而且 ,肯可不可否够用并行算法励志的话 而且:

肯能另另一个函数的结果是Monoid,大伙 可不可否实现本身函数的Monoid实例:

值得注意的是以上另另一个例子foldMapV历遍无论怎样是不让中途退出的。本身特点把foldMapV的使用局限在前要消耗整个数据源的计算应用,如求和、最大值等等。对于另外有些要求,如:A => Boolean本身要求,即使第另另一个值就肯能得到答案也前要走全版串数据。

再来另另一个合并key-value Map的Monoid实例:肯能大伙 有value类型的Monoid实例就可不可否实现:

并行算法:op(op(a,b),op(c,d)) 大伙 可不可否同去运算 op(a,b), op(c,d)