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

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

    Monoid的二元操作函数具有结合特性(associativity),与恒等值(identity)共同应用可以任意采用左折叠或右折叠算法处理串类元素(List element)而得到同等结果。所以使用Monoid op我们可以得出左折叠等于右折叠的结论:

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

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

但是,如果能够用并行算法的话就是:

并行算法:op(op(a,b),op(c,d)) 我们可以同时运算 op(a,b), op(c,d)

如果我们可以使用并行算法的话,肯定能提升计算效率。试想如果我们对一个超大文件进行文字数统计或者寻找最大值什么的,我们可以把这个大文件分成若干小文件然后同时计算后再合计将节省很多计算时间。在现代大数据时代,数据文件不但大而且是分布在许多服务器上的。那么Monoid的特殊定律就可以使数据处理并行运算,特别匹配大数据处理模式。

我们看看能不能实现像折叠算法似的并行算法:

1   def foldMapV[A,B](iseq: IndexedSeq[A])(m: Monoid[B])(f: A => B): B = {
2       if (iseq.isEmpty) m.zero
3       else if (iseq.length == 1) f(iseq(0))
4       else {
5           val (l, r) = iseq.splitAt(iseq.length / 2)
6           m.op(foldMapV(l)(m)(f), foldMapV(r)(m)(f))
7       }
8   }                                               //> foldMapV: [A, B](iseq: IndexedSeq[A])(m: ch10.ex2.Monoid[B])(f: A => B)B

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

结合前面对并行运算的讨论,我们用以下方式应该可以实现并行运算吧:

1   def foldMapV[A,B](iseq: IndexedSeq[A])(m: Monoid[B])(f: A => B): B = {
2       if (iseq.isEmpty) m.zero
3       else if (iseq.length == 1) f(iseq(0))
4       else {
5           val (l, r) = iseq.splitAt(iseq.length / 2)
6           m.op(async(foldMapV(l)(m)(f)), async(foldMapV(r)(m)(f)))
7       }
8   }                                               //> foldMapV: [A, B](iseq: IndexedSeq[A])(m: ch10.ex2.Monoid[B])(f: A => B)B

好,我们下面找个例子来示范高阶类型Monoid实例和并行运算应用:用Monoid来实现对字串(List[String])的文字数统计。由于我们打算采用并行计算,对字串进行分半时会可能会出现一字分成两半的情况,所以需要自定义复杂一点的数据类型:

 1   trait WC 
 2   case class Stub(chars: String) extends WC  //chars 记录了未完整文字的字符
 3   case class Part(lStub: String, words: Int, rStub: String) extends WC   //lStub=左边文字结尾, words=完整字数,rStub=右边文字开头
 4   
 5   def wcMonoid: Monoid[WC] = new Monoid[WC] {
 6       def op(wc1: WC, wc2: WC): WC = {
 7           (wc1, wc2) match {
 8               case (Stub(l),Stub(r)) => Stub(l + r)
 9               case (Stub(lb),Part(le,w,rb)) => Part(lb+le,w,rb)
10               case (Part(le,w,rb),Stub(re)) => Part(le,w,rb+re)
11               case (Part(le,w,rb),Part(lb,w2,re)) => Part(le, w + (if((rb+lb).isEmpty) 0 else 1) + w2, re)
12           }
13       }
14       val zero = Stub("")
15   }

Monoid[WC]是个WC类型的Monoid实例,op(wc1,wc2)=wc3则把两个WC值拼凑起来变成另一个WC值。下面让我们用wcMonoid来实现这个文字统计函数:

 1   def wordCount(ws: String): Int = {
 2     def wc(c: Char): WC = {
 3         if (c.isWhitespace) Part("",0,"")
 4         else Stub(c.toString)
 5     }
 6     def unstub(s: String) = s.length min 1
 7     
 8     foldMapV(ws.toIndexedSeq)(wcMonoid)(wc) match {
 9         case Stub(c) => 0
10         case Part(l,w,r) => unstub(l) + w + unstub(r)
11     }
12   }                                               //> wordCount: (ws: String)Int

用它来数个字数:

1   val words = "the brown fox     is running quickly."  //故意留点空格,标点符号什么的
2                                                   //> words  : String = the brown fox     is running quickly.
3   wordCount(words)                                //> res0: Int = 6 

没错!

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

 1   def seqIsOrdered(iseq: IndexedSeq[Int]): Boolean = {
 2       val stateMonoid = new Monoid[Option[(Int, Int, Boolean)]] {    //状态:Option[(最小值,最大值,是排序)]
 3          def op(s1: Option[(Int,Int,Boolean)], s2: Option[(Int,Int,Boolean)]): Option[(Int,Int,Boolean)] = {
 4            (s1,s2) match {
 5               case (None, b) => b
 6               case (b, None) => b
 7               case (Some((x1,y1,b1)),Some((x2,y2,b2))) => Some(x1 min x2,y1 max y2, b1 && b2 && x2 >= y1)
 8            }
 9          }
10          val zero = None
11       }
12       foldMapV(iseq)(stateMonoid)(i => Some(i,i,true)) map (_._3) getOrElse true
13   }
1   seqIsOrdered(List(1,2,5,9,33).toIndexedSeq)     //> res0: Boolean = true
2   seqIsOrdered(List(1,2,5,0    ,33).toIndexedSeq)    //> res1: Boolean = false

在这个例子里我们用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)。

值得注意的是以上两个例子foldMapV历遍无论如何是不会中途退出的。这个特点把foldMapV的使用局限在必须消耗整个数据源的计算应用,如求和、最大值等等。对于另外一些要求,如:A => Boolean这种要求,即使第一个值就已经得到答案也必须走完整串数据。

我们在之前的章节里曾经讨论了一些数据结构如List,Stream,Tree等。当我们需要处理这些结构中封装的元素时通常使用一些算法如折叠算法。这种算法能保存数据结构。而且它们有共通性:都可以使用折叠算法。既然有共性,肯定就会有深度抽象的空间,我们可以把它们抽象表达成一个Foldable[F[_]]:List,Stream,Tree等数据结构类型就是F[_];一个数据结构中封装了一些元素。这个Foldable类型可以包含各种历遍算法:

 1  def endoComposeMonoid[A] = new Monoid[A => A] {
 2       def op(f: A => A, g: A => A): A => A = f compose g
 3       val zero = (a: A) => a
 4   }
 5   def dual[A](m: Monoid[A]): Monoid[A] = new Monoid[A] {
 6       def op(a1: A, a2: A) = m.op(a2,a1)
 7       val zero = m.zero
 8   }
 9   trait Foldable[F[_]] {
10      def foldRight[A, B](as: F[A])(z: B)(f: (A, B) => B): B = {
11            foldMap(as)(endoComposeMonoid[B])(a => b => f(a,b))(z)
12      }
13      def foldLeft[A, B](as: F[A])(z: B)(f: (B, A) => B): B = {
14            foldMap(as)(dual(endoComposeMonoid[B]))(a => b => f(b,a))(z)
15      }
16      def foldMap[A, B](as: F[A])(mb: Monoid[B])(f: A => B): B = {
17            foldLeft(as)(mb.zero)((b,a) => mb.op(f(a),b))
18      }
19      def concatenate[A](as: F[A])(m: Monoid[A]): A = {
20         foldLeft(as)(m.zero)(m.op)
21      }
22   }

我们现在已经得到了个Foldable抽象数据结构,它包含了多种折叠历遍算法。我们可以试着创建一些Foldable实例看看:

 1   object listFoldable extends Foldable[List] {
 2      override def foldRight[A, B](as: List[A])(z: B)(f: (A, B) => B): B = {
 3            as.foldRight(z)(f)
 4      }
 5      override def foldLeft[A, B](as: List[A])(z: B)(f: (B, A) => B): B = {
 6            as.foldLeft(z)(f)
 7      }
 8      override def foldMap[A, B](as: List[A])(mb: Monoid[B])(f: A => B): B = {
 9            as.foldLeft(mb.zero)((b,a) => mb.op(f(a),b))
10      }
11      override def concatenate[A](as: List[A])(m: Monoid[A]): A = {
12         as.foldLeft(m.zero)(m.op)
13      }
14   }
15   object indexedSeqFoldable extends Foldable[IndexedSeq] {
16      override def foldRight[A, B](as: IndexedSeq[A])(z: B)(f: (A, B) => B): B = {
17            as.foldRight(z)(f)
18      }
19      override def foldLeft[A, B](as: IndexedSeq[A])(z: B)(f: (B, A) => B): B = {
20            as.foldLeft(z)(f)
21      }
22      override def foldMap[A, B](as: IndexedSeq[A])(mb: Monoid[B])(f: A => B): B = {
23            as.foldLeft(mb.zero)((b,a) => mb.op(f(a),b))
24      }
25      override def concatenate[A](as: IndexedSeq[A])(m: Monoid[A]): A = {
26         as.foldLeft(m.zero)(m.op)
27      }
28   }
29   object StreamFoldable extends Foldable[Stream] {
30      override def foldRight[A, B](as: Stream[A])(z: B)(f: (A, B) => B): B = {
31            as.foldRight(z)(f)
32      }
33      override def foldLeft[A, B](as: Stream[A])(z: B)(f: (B, A) => B): B = {
34            as.foldLeft(z)(f)
35      }
36   }

再看看Tree foldable 实例:

 1  trait Tree[+A] 
 2   case class Leaf[A](value: A) extends Tree[A]
 3   case class Branch[A](left: Tree[A], right: Tree[A]) extends Tree[A]
 4   object TreeFoldable extends Foldable[Tree] {
 5       override def foldMap[A, B](as: Tree[A])(mb: Monoid[B])(f: A => B): B = {
 6           as match {
 7               case Leaf(a) => f(a)
 8               case Branch(l,r) => mb.op(foldMap(l)(mb)(f),foldMap(r)(mb)(f))
 9           }
10       }
11       override def foldRight[A, B](as: Tree[A])(z: B)(f: (A, B) => B): B = {
12           as match {
13               case Leaf(a) => f(a,z)     //恒等值定律 
14               case Branch(l,r) => foldRight(l)(foldRight(r)(z)(f))(f)
15           }
16       }
17       override def foldLeft[A, B](as: Tree[A])(z: B)(f: (B,A) => B): B = {
18           as match {
19               case Leaf(a) => f(z,b)
20               case Branch(l,r) => foldLeft(r)(foldLeft(l)(z)(f))(f)
21           }
22       }
23   }

可以看出TreeFoldable的实现方式与List,Stream等串类数据类型有所不同。这是因为Tree类型没有现成的折叠算法。再就是Tree类型没有空值(只有Leaf, Branch)。这个特性暗示着有些类型的Monoid是没有恒等值的。我们统称这些类型为semigroup。

Option的foldable与TreeFoldable很像:

 1   object OptionFoldable extends Foldable[Option] {
 2        override def foldMap[A, B](opt: Option[A])(mb: Monoid[B])(f: A => B): B = {
 3            opt match {
 4                case None => mb.zero
 5                case Some(a) => f(a)
 6            }
 7        }
 8     override def foldRight[A, B](opt: Option[A])(z: B)(f: (A, B) => B): B = {
 9      opt match {
10          case None => z
11          case Some(a) => f(a,z)
12      }
13     }
14     override def foldLeft[A, B](opt: Option[A])(z: B)(f: (B,A) => B): B = {
15         opt match {
16             case None => z
17             case Some(a) => f(z,a)
18         }
19     }
20   }

实际上任何可折叠的数据类型都可以被转换成List类型,因为我们可以用折叠算法重组List:

 1  trait Foldable[F[_]] {
 2      def foldRight[A, B](as: F[A])(z: B)(f: (A, B) => B): B = {
 3            foldMap(as)(endoComposeMonoid[B])(a => b => f(a,b))(z)
 4      }
 5      def foldLeft[A, B](as: F[A])(z: B)(f: (B, A) => B): B = {
 6            foldMap(as)(dual(endoComposeMonoid[B]))(a => b => f(b,a))(z)
 7      }
 8      def foldMap[A, B](as: F[A])(mb: Monoid[B])(f: A => B): B = {
 9            foldLeft(as)(mb.zero)((b,a) => mb.op(f(a),b))
10      }
11      def concatenate[A](as: F[A])(m: Monoid[A]): A = {
12         foldLeft(as)(m.zero)(m.op)
13      }
14      def toList[A](as: F[A]): List[A] = {
15          foldRight(as)(Nil: List[A]){_ :: _}
16      }
17   }

Monoid的函数组合能力也挺有趣:如果我们有Monoid[A], Monoid[B],那我们就可以把它们组合成Monoid[(A,B)]:

1   def productMonoid[A,B](ma: Monoid[A], mb: Monoid[B]): Monoid[(A,B)] = new Monoid[(A,B)] {
2       def op(x: (A,B), y: (A,B)) = (ma.op(x._1, y._1), mb.op(x._2,y._2))
3       val zero = (ma.zero, mb.zero)
4   }                                               //> productMonoid: [A, B](ma: ch10.ex2.Monoid[A], mb: ch10.ex2.Monoid[B])ch10.e
5                                                   //| x2.Monoid[(A, B)]

我们可以用这个组合的Monoid在历遍一个List时同时计算List长度及和:

1  val pm = productMonoid(intAdditionMonoid,intAdditionMonoid)
2                                                   //> pm  : ch10.ex2.Monoid[(Int, Int)] = ch10.ex2$$anonfun$main$1$$anon$6@614c55
3                                                   //| 15
4   listFoldable.foldMap(List(1,2,3,4))(pm)(a => (1, a))
5                                                   //> res0: (Int, Int) = (4,10)

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

下面剩下的时间我们再讨论一些较复杂的Monoid:

如果一个函数的结果是Monoid,我们可以实现这个函数的Monoid实例:

1   def functionMonoid[A,B](mb: Monoid[B]): Monoid[A => B] = new Monoid[A => B] {
2       def op(f: A => B, g: A => B): A => B = a => mb.op(f(a),g(a))
3       val zero: A => B = a => mb.zero 
4   }

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

再来一个合并key-value Map的Monoid实例:如果我们有value类型的Monoid实例就可以实现:

1   def mapMergeMonoid[K,V](mv: Monoid[V]): Monoid[Map[K,V]] = new Monoid[Map[K,V]] {
2        val zero = Map()
3       def op(ma: Map[K,V], mb: Map[K,V]): Map[K,V] = {
4           ma.map {
5               case (k,v) => (k, mv.op(v, mb get(k) getOrElse mv.zero ))
6           }
7       }
8   }

有了这个Monoid实例,我们就可以处理Map的嵌入表达式了:

 1   val M: Monoid[Map[String, Map[String, Int]]] = mapMergeMonoid(mapMergeMonoid(intAdditionMonoid))
 2   M: Monoid[Map[String, Map[String, Int]]] = $anon$1@21dfac82
 3   
 4  val m1 = Map("o1" -> Map("i1" -> 1, "i2" -> 2))
 5  m1: Map[String,Map[String,Int]] = Map(o1 -> Map(i1 -> 1, i2 -> 2))
 6  
 7  val m2 = Map("o1" -> Map("i2" -> 3))
 8  m2: Map[String,Map[String,Int]] = Map(o1 -> Map(i2 -> 3))
 9  
10  val m3 = M.op(m1, m2)
11  m3: Map[String,Map[String,Int]] = Map(o1 -> Map(i1 -> 1, i2 -> 5))

最后,我们试着用mapMergeMonoid实例来实现frequencyMap:计算输入List里的文字发现次数。如果用一个例子来说明的话,看看下面这个一串文字转成key-value Map:

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

这不就是搜索引擎中的索引比重算法吗?我们用foldMapV和mapMergeMonoid可以并行运算整理索引,这算是Monoid的实际应用之一。

我们看看具体实现:

1 def frequencyMap[A](as: IndexedSeq[A]): Map[A, Int] =
2   foldMapV(as, mapMergeMonoid[A, Int](intAddition))((a: A) => Map(a -> 1))
1 frequencyMap(Vector("a rose", "is a", "rose is", "a rose"))
2 res0: Map[String,Int] = Map(a -> 3, rose -> 3, is -> 2)

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏WeaponZhi

使用Octave来学习Machine Learning(二)

前言 上一篇我们介绍了 Octave 的一些基本情况,大家对 Octave 应该已经有了一个基本的了解,我相信看这篇文章的朋友已经在自己的电脑中安装好 Ocat...

3196
来自专栏应兆康的专栏

贝叶斯分类器及Python实现

由于某些不可抗拒的原因,LaTeX公式无法正常显示. 点击这里查看PDF版本 Github: https://github.com/yingzk/MyML 博 ...

3327
来自专栏章鱼的慢慢技术路

《算法图解》第八章_贪婪算法_集合覆盖问题

1696
来自专栏应兆康的专栏

贝叶斯分类器及Python实现

贝叶斯分类是一类分类算法的总称,这类算法均以贝叶斯定理为基础,故统称为贝叶斯分类。本文由本人学习贝叶斯分类器过程中的笔记,再加上使用Python进行文本分类实战...

57922
来自专栏利炳根的专栏

学习笔记DL004:标量、向量、矩阵、张量,矩阵、向量相乘,单位矩阵、逆矩阵

线性代数,面向连续数学,非离散数学。《The Matrix Cookbook》,Petersen and Pedersen,2006。Shilov(1977)。

3010
来自专栏大学生计算机视觉学习DeepLearning

深度学习(六)keras常用函数学习 2018最新win10 安装tensorflow1.4(GPU/CPU)+cuda8.0+cudnn8.0-v6 + keras 安装CUDA失败 导入ten

原文链接:https://www.cnblogs.com/DOMLX/p/9769301.html

431
来自专栏人工智能LeadAI

讨厌算法的程序员 | 第七章 归并排序的时间复杂度分析

上一篇归并排序基于分治思想通过递归的调用自身完成了排序,本篇是关于归并排序的最后一部分——分析其时间复杂度。 这个过程中会解释清楚在各种时间复杂度中经常看到的一...

34511
来自专栏深度学习计算机视觉

打印字符图形(蓝桥杯基础题 Java版)

问题描述 利用字母可以组成一些美丽的图形,下面给出了一个例子: ABCDEFG BABCDEF CBABCDE DCBABCD EDCBABC 这...

3596
来自专栏数说工作室

函数玩一玩 | 【SAS Says·扩展篇】IML:2.函数

【SAS Says·扩展篇】IML 分6集,回复【SASIML】查看全部: 入门 | SAS里的平行世界 函数 | 函数玩一玩 编程 | IML的条件与循环 模...

3119
来自专栏有趣的Python

玩转算法面试:(二)面试中的复杂度分析

面试中的时间复杂度分析 到底什么是大O n表示数据规模 O(f(n)) fn是关于n的一个函数。表示运行算法所需要执行的指令数,和f(n)成正比。 ? 常见...

4755

扫码关注云+社区