3:10 to Yuma

前几年看过的《决战犹马镇》是一部给我留有印象的电影,描述了一个很特别的强盗。当时是世界杯期间:

昨天晚上看了会儿日本对巴拉圭,场面不是很吸引我,切换到了中央六正在播放《决战犹马镇》。看完觉得有种说不清楚的感觉,是因为无法按照我的逻辑去理解那个强盗,是个亦邪亦正的,被电影刻画的带些艺术家气息的,有自我原则的强盗。对这个强盗最后想要成全这位为生计所迫的、不愿因自己的无能而承受妻子冷漠(更多是他自尊心作祟)的、落魄的、孤注一掷的、因受伤而退伍的军人,成为儿子和家人心中的英雄(因为他从未真正成为过,他参加的第一场战役就是一次撤退,一条腿也是被自己人所伤)的行为感到有些不解,或许是他们的惺惺相惜,说不清楚。没有看到开头,有些信息获取的不全。

今天在知乎里看到这个答案,终于明白了:http://www.zhihu.com/question/20407078

我所理解的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的其他特征上。

spray中的Magnet模式: typeclass的一种特定方式

Magnet是spray中对type class模式的使用方式,这篇blog主要来自spray作者的:http://spray.io/blog/2012-12-13-the-magnet-pattern/ ,原话中对 Magnet解释:

我们的意图并不是给“type classes”模式一个新名称,而是描述一种为特殊目的而使用的方式。

先看一下他举例在http请求结束(complete)时要做的事情,使用方法重载(method overload)遇到的问题:

1) 因为类型擦拭,会有方法冲突
2) No lifting into a function (of all overloads at the same time)
3) 对包对象中不可用(2.10之前)
4) Code duplication in case of many similar overloads
5) Limitations with regard to parameter defaults
6) Limitations with regard to type inference on arguments

Magnet模式可以解决上面除了最后2点的所有问题。

原先通过方法overload:

def complete[T :Marshaller](status: StatusCode, obj: T): Unit
def complete(future: Future[HttpResponse]): Int
def complete(future: Future[StatusCode]): Int

使用Magnet模式,变成一个方法:

def complete(magnet: CompletionMagnet): magnet.Result = magnet()

看到 magnet封装了行为,以及结果类型

sealed trait CompletionMagnet {
    type Result
    def apply(): Result
}

然后通过隐式转换,让一些类型具备Magnet的能力

object CompletionMagnet {
    implicit def fromStatusObject[T :Marshaller](tuple: (StatusCode, T)) =
        new CompletionMagnet {
            type Result = Unit
            def apply(): Result = ... // implementation using (StatusCode, T) tuple
    }
    implicit def fromHttpResponseFuture(future: Future[HttpResponse]) =
        new CompletionMagnet {
            type Result = Int
            def apply(): Result = ... // implementation using future
    }
    implicit def fromStatusCodeFuture(future: Future[StatusCode]) =
        new CompletionMagnet {
            type Result = Int
            def apply(): Result = ... // implementation using future
    }
}

调用时,会进行隐式转换,下面第一个方法参数是tuple

complete(StatusCodes.OK, "All fine") // returns Unit
complete(someHttpResponseFuture) // returns Int
complete(someStatusCodeFuture) // returns Int

回顾之前blog中介绍过的type class
scala类型系统:26) type classes模式
scala类型系统:27) 回顾常见的type classes

Magnet并没有在声明时使用泛型参数,而是在其内部定义了 type Result,是一个意思。然后对行为方法都命名为apply,方便在执行时以小括号方式调用。

我所理解的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)特性才是它的威力所在,这个特性使得并行运算变得容易。