我所理解的monad(3):半群(semigroup)与并行运算

上文,因为半群里的“结合律”特性,使得我们可以对一些任务拆分采用并行处理,只要这些任务的结果类型符合“结合律”(即没有先后依赖)。让我们看一个单词统计的例子,阿里中间件团队前几个月有过一次编程比赛就是统计单词频度,参考:Coding4Fun第三期活动总结

编程比赛主要是考察技巧,现在我们看看现实世界中用scala怎么解决这个问题,如果数据是巨大的,无疑要采用map-reduce的思路,如果我们不依赖hadoop之类的系统来解决,最简单的方式就是actor处理,最后再汇总结果。这篇blog不讨论数据的统计处理,看看最后如何把这些结果合并

type Result = Map[String,Int]

object combiner extends SemiGroup[Result] {

    def append(x: Result, y: Result): Result = {
        val x0 = x.withDefaultValue(0)
        val y0 = y.withDefaultValue(0)
        val keys = x.keys.toSet.union(y.keys.toSet)
        keys.map{ k => (k -> (x0(k) + y0(k))) }.toMap
    } //不考虑效率
}

现在假设不同的actor分别返回r1,r2

val r1 = Map("hello" -> 1, "world" -> 2)
val r2 = Map("hello" -> 2, "ok" -> 5)

val counts = combiner.append(r1, r2)

如果有其他actor再返回结果的话,只要继续合并下去:

combiner.append(r3, counts)

twitter开源的algebird,就是基于semigroup/monoid的。不过我们不必沿着这条路深入下去,monad并不是为了并发而发明的,只是它正好是一个半群(幺半群),半群的结合律符合并行运算(由半群演化出来的迹幺半群和历史幺半群是进程演算和并行计算的基础)。这是另一个方向,不继续涉及下去,我们后续回到monad的其他特征上。

我所理解的monad(2):fold与monoid

在Scala中的核心数据结构List中,定义了fold操作,实际上这些方法是定义在scala集合库的最顶层特质GenTraversableOnce中的:

List中的左折叠(借用wiki上的图):

def foldLeft[B](z: B)(op: (B, A) => B): B

从图中可以看到,左折叠是用一个初始元素z从List的左边第一个元素开始操作,一直到对所有的元素都操作完。

现在我们对一个List进行累加操作:

scala> List("A","B","C").foldLeft("")(_+_)
res5: String = ABC

上面foldLeft传入的两个参数空字符串,以及二元操作函数 _+_ 不正好符合字符串monoid的定义吗?

object StringMonoid extends Monoid[String] {
    def append(a: String, b: String) = a + b
    def zero = ""
}

StringMonoid来代入:

scala> List("A","B","C").foldLeft(StringMonoid.zero)(StringMonoid.append)
res7: String = ABC

现在我们对List定义一个累加其元素的方法:

scala> def acc[T](list: List[T], m: Monoid[T]) = {
    list.foldLeft(m.zero)(m.append)
}

再进一步,把第二个参数改为隐式参数

scala> def acc[T](list: List[T])(implicit m: Monoid[T]) = { 
    list.foldLeft(m.zero)(m.append) 
}

现在Monoid成了一个type class,我们还可以再简化写法,用上下文绑定:

scala> def acc[T: Monoid](list: List[T]) = {
    val m = implicitly[Monoid[T]]
    list.foldLeft(m.zero)(m.append) 
}

如果我们在上下文提供了对应隐式值,就等于对List有了这种累加的能力:

scala> implicit val intMonoid = new Monoid[Int] { 
            def append(a: Int, b: Int) = a + b
            def zero = 0 
        }


scala> implicit val strMonoid = new Monoid[String] { 
            def append(a: String, b: String) = a + b
            def zero = ""
        }

scala> acc(List(1,2,3))
res10: Int = 6

scala> acc(List("A","B","C"))
res11: String = ABC

现在我们把Monoid看成基于二元操作(且提供单位元)的计算能力的抽象,不过仅仅是fold操作的话,还看不出它有什么威力。Monoid/SemiGroup中的结合律(associativity)特性才是它的威力所在,这个特性使得并行运算变得容易。

我所理解的monad(1):半群(semigroup)与幺半群(monoid)

google到数学里定义的群(group): G为非空集合,如果在G上定义的二元运算 *,满足

(1)封闭性(Closure):对于任意a,b∈G,有a*b∈G
(2)结合律(Associativity):对于任意a,b,c∈G,有(a*b)*c=a*(b*c)
(3)幺元 (Identity):存在幺元e,使得对于任意a∈G,e*a=a*e=a
(4)逆元:对于任意a∈G,存在逆元a^-1,使得a^-1*a=a*a^-1=e

则称(G,*)是群,简称G是群。

如果仅满足封闭性和结合律,则称G是一个半群(Semigroup);如果仅满足封闭性、结合律并且有幺元,则称G是一个含幺半群(Monoid)。

相比公式还是用代码表达更容易理解,下面表示一个半群(semigroup):

trait SemiGroup[T] {
    def append(a: T, b: T): T
}

特质SemiGroup,定义了一个二元操作的方法append,可以对半群内的任意2个元素结合,且返回值仍属于该半群。

我们看具体的实现,一个Int类型的半群实例:

object IntSemiGroup extends SemiGroup[Int] {
    def append(a: Int, b: Int) = a + b
}

// 对2个元素结合
val r = IntSemiGroup.append(1, 2)

现在在半群的基础上,再增加一个幺元(Identity,也翻译为单位元),吐槽一下,幺元这个中文不知道最早谁起的,Identity能表达的意义(同一、恒等)翻译到中文后完全消失了。

trait Monoid[T] extends SemiGroup[T] {
    // 定义单位元
    def zero: T
}

上面定义了一个幺半群,继承自半群,增加了一个单位元方法,为了容易理解,我们用zero表示,半群里的任何元素a与zero结合,结果仍是a本身。

构造一个Int类型的幺半群实例:

object IntMonoid extends Monoid[Int] {
    // 二元操作
    def append(a: Int, b: Int) = a + b
    // 单位元
    def zero = 0
}

构造一个String类型的幺半群实例:

object StringMonoid extends Monoid[String] {
    def append(a: String, b: String) = a + b
    def zero = ""
}

再构造一个复杂点的 List[T] 的幺半群工厂方法:

def listMonoid[T] = {
    new Monoid[List[T]] { 
        def zero = Nil
        def append(a: List[T], b: List[T]) = a ++ b 
    }
}

OK,现在我们已经了解了幺半群是什么样了,但它有什么用?

我所理解的monad(0)

以前在别人的一篇blog里看到过有这样一句话,大意是:关于monad,几乎每个在学习函数式编程中接触到这个模式的,都会写一篇博客描述他的理解。而且不同的人对monad的理解有所不同(暗讽monad的复杂)。

我也不例外,大约是3年前刚接触scala时,无意搜到了james的《monads are elephants》,一下子把我给难住了。scala在刚开始学习时,如果只把它当作java的替代者来用,继续用OO的范式的话,并不难。但在继续深入它的类型和函数式特征之后,发现有一篇广袤的世界是之前不曾看到的,可以以一种新的视角来思考编程的本质。而scala在OO与”新世界”之间架起一座桥(Bridge to Terabithia),通过这座桥的一个代价是,抛弃原先认为编程理所当然应该这样的观念。

在新的世界同样有设计模式,不过它们抽象的角度不同。理解起来有些困难,最大的原因是缺乏对这个新世界的认识,具体的说scala里最显著困难是它的类型系统,当类型的抽象度变高之后(犹如从二维世界到三维世界),它的含义和使用场景也会复杂很多。而monad正是基于高阶类型做的抽象。所以在了解monad前一定先要了解scala中高阶类型的概念,这块可以参考我blog中的scala类型系统系列。

通常monad也是一个标识,判断程序员对函数式世界的了解程度,它背后隐藏着很多的概念,并且很多来自数论(范畴领域),对于非科班出身的我来说,总是心存敬畏而避而远之,但我们如果去掉这些理论描述,仅从程序的实现来看,还是比较容易的,只要把这些概念一点点分解开的话。

在james的这篇 A Brief, Incomplete, and Mostly Wrong History of Programming Languages,(译文参考这里:程序语言简史(伪) ),有段关于monad的描述很有意思:

Haskell由于使用了Monad这种较费解的概念来控制副作用而遭到了一些批评意见。Wadler试图平息这些质疑,他解释说:“一个单子(Monad)说白了不过就是自函子范畴上的一个幺半群而已,这有什么难以理解的?”

我们就从这句话说起,先理解是“幺半群”,别被这个字面术语吓到,其实用程序表达起来很简单。