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

  • 时间:
  • 浏览:2

大伙儿在过后的章节里原来讨论了或多或少数据底部形态如List,Stream,Tree等。当大伙儿不到处里那此底部形态中封装的元素时通常使用或多或少算法如折叠算法。这名 算法能保存数据底部形态。否则它们有共通性:都都能否使用折叠算法。既然有共性,肯定就会有层厚抽象的空间,大伙儿都能否把它们抽象表达成有3个多 多Foldable[F[_]]:List,Stream,Tree等数据底部形态类型什么都有F[_];有3个多 多数据底部形态中封装了或多或少元素。这名 Foldable类型都能否所含各种历遍算法:

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

并行算法:op(op(a,b),op(c,d)) 大伙儿都能否共同运算 op(a,b), op(c,d)

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

这不什么都有搜索引擎中的索引比重算法吗?大伙儿用foldMapV和mapMergeMonoid都能否并行运算分派索引,这否是Monoid的实际应用之一。

结合前面对并行运算的讨论,大伙儿用以下方法应该都能否实现并行运算吧:

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

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

    Monoid的二元操作函数具有结合底部形态(associativity),与恒等值(identity)共同应用都能否任意采用左折叠或右折叠算法处里串类元素(List element)而得到同等结果。什么都有使用Monoid op大伙儿都能否得出左折叠等于右折叠的结论:

值得注意的是以上有3个多 多例子foldMapV历遍无论要怎样是太少中途退出的。这名 特点把foldMapV的使用局限在不到消耗整个数据源的计算应用,如求和、最大值等等。对于另外或多或少要求,如:A => Boolean这名 要求,即使第有3个多 多值就可能性得到答案过后到走完整串数据。

大伙儿看看具体实现:

都能否看出TreeFoldable的实现方法与List,Stream等串类数据类型有所不同。这是可能性Tree类型没人 现成的折叠算法。再什么都有Tree类型没人 空值(不到Leaf, Branch)。这名 底部形态暗示着或多或少类型的Monoid是没人 恒等值的。大伙儿统称那此类型为semigroup。

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

否则,可能性都能否用并行算法一句话什么都有:

 Option的foldable与TreeFoldable很像:

下面剩下的时间大伙儿再讨论或多或少较复杂的Monoid:

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

啊,这名 foldMapV从外表,在类型款式上跟foldMap相同,不同的是内部人员具体实现方法;foldMapV循环把目标串进行分半。

可能性有3个多 多函数的结果是Monoid,大伙儿都能否实现这名 函数的Monoid实例:

没错!

在这名 例子里大伙儿用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里的文字发现次数。可能性用有3个多 多例子来说明一句话,看看下面这名 一串文字转成key-value Map:

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

可能性大伙儿都能否使用并行算法一句话,肯定能提升计算传输速度。试想可能性大伙儿对有3个多 多超大文件进行文字数统计可能性寻找最大值那此的,大伙儿都能否把这名 大文件分成若干小文件否则共同计算后再合计将节省什么都有计算时间。在现代大数据时代,数据文件不但大否则是分布在或多或少服务器上的。没人 Monoid的特殊定律就都能否使数据处里并行运算,特别匹配大数据处里模式。

再来有3个多 多合并key-value Map的Monoid实例:可能性大伙儿有value类型的Monoid实例就都能否实现: