月度归档:2013年12月

我所理解的monad(6):从组合子(combinator)说起

从同事的反馈了解到前边几篇monad的介绍说的有些抽象。现在还没有提出monad,如果把monoid与endofunctor结合起来,恐怕更是抽象。还是回到用大家更能体会的场景来描述,等对monad有了基本的印象之后,最后再试图把monad在现实世界的表现与范畴论里的形式结合起来。

我想到一个比较好的方式是从行为的组合来说monad,因为这个层面的例子容易接受,最近在用的spray-routing框架,它的核心Directive(指令)就是一个行为组合子monad

最初知道组合子(combinator)这个单词是从《PIS》书中专门有一章讲“连接符解析”(combinator parsing),当时没有理解combinator的概念,那章也是偏重说parser的;后来在很多资料里看到把monad也当成combinator对待,一直没有悟清楚各种combinator是不是一回事,直到看到了ajoo的系列文章(推荐一下):

论面向组合子程序设计方法: 
http://www.blogjava.net/ajoo/category/6968.html

论面向组合子程序设计方法 之一 创世纪
论面向组合子程序设计方法 之二 失乐园
论面向组合子程序设计方法 之三 失乐园之补充
论面向组合子程序设计方法 之四 燃烧的荆棘
论面向组合子程序设计方法 之五 新约
论面向组合子程序设计方法 之六 oracle
论面向组合子程序设计方法 之七 重构
论面向组合子程序设计方法 之八 monad
论面向组合子程序设计方法 之九 南无阿弥陀佛
论面向组合子程序设计方法 之十 还是重构
论面向组合子程序设计方法 之十一 微步毂纹生

ajoo是个牛人,早期在javaeye有看到过他实现了一套基于jvm的haskell,取名“jaskell”。那也是好些年前了,在javaeye围观他与Trustno1等人对函数式编程的讨论,云里雾里。现在感觉稍微能跟这些大牛们有一些对话,却找不到这样的圈子了。引用ajoo的话:

组合子,英文叫combinator,是函数式编程里面的重要思想。如果说OO是归纳法(分析归纳需求,然后根据需求分解问题,解决问题),那么 “面向组合子”就是“演绎法”。通过定义最基本的原子操作,定义基本的组合规则,然后把这些原子以各种方法组合起来。

引用另外一位函数式领域的大师的说法:

A combinator is a function which builds program fragments from program fragments

这句话有一些“自相似性”,可以把combinator先当成一种“胶水”,更具体一些,把scala的集合库里提供的一些函数看成combinator:

map
foreach
filter
fold/reduce
zip/partition
flatten/flatMap

而monad正是一个通用的combinator,也是一种设计模式,但它有很多面,就我后续的举例来说,先把monad看成一个“行为”的组合子。体现在代码上:

class M[A](value: A) {  

    // 1) 把普通类型B构造为M[B]
    // 因为M定义为class并提供了构造方法,可以通过new关键字来构造,该工厂方法可以省略
    def unit[B] (value : B) = new M(value)  

    // 2) 不是必须的
    def map[B](f: A => B) : M[B] = flatMap {x => unit(f(x))}  

    // 3) 必须,核心方法
    def flatMap[B](f: A => M[B]) : M[B] = ...  
} 

一个monad内部除了一个工厂方法unit(注意,与Unit类型没有关系,unit这里表示“装箱”,源自haskell里的叫法),还包含了两个combinator方法,mapflatMap,这两个组合子中flatMap是不可少的,map可以通过flatMap来实现。

unit方法不一定会定义在monad类内部,很多情况下会在伴生对象中通过工厂方法来实现。

这里忽略了monad里的法则,重点先理解M封装了什么?以及内部的mapflatMap的含义是什么。

柯里化(currying)与构造器(Builder)模式

从某种意义上说,这两者的思路是相似的,都是把一个大的过程转换为若干个部分来逐步向目标靠近的。

一个构造器模式也可以实现为链式风格:

t.buildPart1(xxx).buildPart2(yyy).buildPart3(zzz)

对比一个柯里化的函数的链式调用:

scala> def build(p1: =>Int)(p2: =>Int)(p3: =>Int) = 
        new { val x:Int = p1; val y:Int = p2; val z:Int = p3 }

scala> build{
 | print("part1"); 100 } {
 | print("part2"); 200 } {
 | print("part3"); 300 }

上面相当于:

scala> build(100) (200) (300)

通常使用柯里化来实现部分应用函数,比如:

scala> val b = build _

当传入的参数不全的情况下,产出的仍是函数,相当于一个中间状态:

scala> b(100)(200)
res16: (=> Int) => AnyRef{val x: Int; val y: Int; val z: Int} = <function1>

scala里对普通函数可以很方便的转化为柯里化函数,所以在构造一个对象的时候也可以把构造方法(或工厂方法)柯里化,类似于Builder模式“一步一步”的方式来构造:

scala> case class Foo(a:A, b:B, c:C)

scala> val builder = (Foo.apply _).curried

scala> builder.apply(new A).apply(new B).apply(new C)

我所理解的monad(5):自函子(Endofunctor)是什么

经过前面一篇对函子(Functor)的铺垫,我们现在可以看看什么是自函子(Endofunctor)了,从范畴的定义看很简单:

自函子就是一个将范畴映射到自身的函子 (A functor that maps a category to itself)

这句话看起来简单,但有个问题,如何区分自函子与Identity函子?让我们先从简单的“自函数”来看。

自函数(Endofunction)

自函数是把一个类型映射到自身类型,比如Int=>Int, String=>String

注意自函数与Identity函数的差异,Identity函数是什么也不做,传入什么参数返回什么参数,它属于自函数的一种特例;自函数是入参和出参的类型一致,比如 (x:Int) => x * 2(x:Int) => x * 3 都属于自函数:

自函子(Endofunctor)

自函子映射的结果是自身,下图是一个简单的情况:

假设这个自函子为F,则对于 F[Int] 作用的结果仍是Int,对于函数f: Int=>String 映射的结果 F[f] 也仍是函数f,所以这个自函子实际是一个Identity函子(自函子的一种特例),即对范畴中的元素和关系不做任何改变。

那怎么描述出一个非Identity的自函子呢?在介绍范畴在程序上的用法的资料里通常都用haskell来举例,把haskell里的所有类型和函数都放到一个范畴里,取名叫Hask,那么对于这个Hask的范畴,它看上去像是这样的:

先来解释一下(画这个图的时候做了简化),A,B代表普通类型如String,Int,Boolean等,这些(有限的)普通类型是一组类型集合,还有一组类型集合是衍生类型(即由类型构造器与类型参数组成的),这是一个无限集合(可以无限衍生下去)。这样范畴Hask就涵盖了haskell中所有的类型。

对于范畴Hask来说,如果有一个函子F,对里面的元素映射后,其结果仍属于Hask,比如我们用List这个函子:

List[A], List[List[A]], List[List[List[A]]]...

发现这些映射的结果也是属于Hask范畴(子集),所以这是一个自函子,实际上在Hask范畴上的所有函子都是自函子。

我们仔细观察这个Hask范畴的结构,发现它实际是一个fractal结构,所谓fractal(分形),是个很神奇的结构,在自然界也大量存在:

如上面的这片叶子,它的每一簇分支,形状上与整体的形状是完全一样的,即局部与整体是一致的结构(并且局部可以再分解下去)

这种结构在函数式语言里也是很常用的,最典型的如List结构,由headtail 两部分组合而成,而每个tail也是一个List结构,可以递归的分解下去。

我所理解的monad(4):函子(functor)是什么

大致介绍了幺半群(monoid)后,我们重新回顾最初引用wadler(haskell委员会成员,把monad引入haskell的家伙)的那句话:

一个单子(Monad)说白了不过就是自函子范畴上的一个幺半群而已 

现在我们来解读这句话中包含的另一个概念:自函子(Endofunctor),不过我们先需要一些铺垫:

首先,什么是函子(Functor)?

乍一看名字,以为函子(functor)对函数(function)是一种封装,实际没有关系,尽管他们都是表示映射,但两者针对的目标不一样。

函数表达的映射关系在类型上体现在特定类型(proper type)之间的映射,举例来说:

// Int => String
scala> def foo(i:Int): String = i.toString

// List[Int] => List[String]
scala> def bar(l:List[Int]): List[String] = l.map(_.toString)

// List[T] => Set[T]
scala> def baz[T](l:List[T]): Set[T] = l.toSet

而函子,则是体现在高阶类型(确切的说是范畴,可把范畴简单的看成高阶类型)之间的映射(关于高阶类型参考: scala类型系统:24) 理解 higher-kinded-type),听上去还是不够直观,函子这个术语是来自群论(范畴论)里的概念,表示的是范畴之间的映射,那范畴又与类型之间是什么关系?

把范畴看做一组类型的集合

假设这里有两个范畴:范畴C1 里面有类型String 和类型 Int;范畴C2 里面有 List[String]List[Int]

函子表示范畴之间的映射

从上图例子来看,这两个范畴之间有映射关系,即在C1里的Int 对应在C2里的List[Int],C1里的String对应C2里的List[String],在C1里存在Int->String的关系态射(术语是morphism,我们可理解为函数),在C2里也存在List[Int]->List[String]的关系态射。

换句话说,如果一个范畴内部的所有元素可以映射为另一个范畴的元素,且元素间的关系也可以映射为另一个范畴元素间关系,则认为这两个范畴之间存在映射。所谓函子就是表示两个范畴的映射。

怎么用代码来描述函子?

从上图的例子,我们已经清楚了functor的含义,即它包含两个层面的映射:

1) 将C1中的类型 T 映射为 C2 中的 List[T] :  T => List[T]
2) 将C1中的函数 f 映射为 C2 中的 函数fm :  (A => B) => (List[A] => List[B])

要满足这两点,我们需要一个类型构造器

trait Functor[F[_]] {

    def typeMap[A]: F[A]

    def funcMap[A,B](f: A=>B): F[A]=>F[B] 
}

我们现在可以把这个定义再简化一些,类型的映射方法可以不用,并把它作为一个type class

trait Functor[F[_]] {
    def map[A,B](fa: F[A], f: A=>B): F[B]
}

现在我们自定义一个My[_]的类型构造器,测试一下这个type class:

scala> case class My[T](e:T)

scala> def testMap[A,B, M <: My[A]](m:M, f: A=>B)(implicit functor:Functor[My]) = {
 |          functor.map(m,f)
 |      }

scala> implicit object MyFunctor extends Functor[My] {
 |          def map[A,B](fa: My[A], f:A=>B) = My(f(fa.e))
 |      }

//对 My[Int], 应用函数 Int=>String 得到 My[String]
scala> testMap(My(200), (x:Int)=>x+"ok")
res9: My[String] = My(200ok)

不过大多数库中对functor的支持,都不是通过type class模式来做的,而是直接在类型构造器的定义中实现了map方法:

scala> case class My[A](e:A) {
     |     def map[B](f: A=>B): My[B] = My(f(e))
     | }

scala> My(200).map(_.toString)
res10: My[String] = My(200)

这样相当于显式的让My同时具备了对类型和函数的映射(A->My[A]A=>B -> My[A]=>My[B];在haskell里把这两个行为也叫提升(lift),相当于把类型和函数放到容器里),所以我们也可以说一个带有map方法的类型构造器,就是一个函子。

范畴与高阶类型

我们再来思考一下,如果忽略范畴中的关系(函数),范畴其实就是对特定类型的抽象,即高阶类型(first-order-type或higher-kinded-type,也就是类型构造器),那么对于上面例子中的”范畴C2″,它的所有类型都是List[T]的特定类型,这个范畴就可以抽象为List高阶类型。那对于”范畴C1″呢?它又怎么抽象?其实,”范畴C1″的抽象类型可以看做是一个Identity类型构造器,它与任何参数类型作用构造出的类型就是参数类型:

scala> type Id[T] = T

是不是很像单位元的概念?在shapeless里已经提起过

这么看的话,如果范畴也可以用类型(高阶)来表达,那岂不是只用普通函数就可以描述它们之间的映射了?别急,先试试,方法里是不支持类型构造器做参数的:

scala> def foo(cat: Id) = print(cat)
    <console>:18: error: type Id takes type parameters

方法中只能使用特定类型(proper type)做参数。

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

我所理解的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)说白了不过就是自函子范畴上的一个幺半群而已,这有什么难以理解的?”

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