starling和kestrel这两只鸟的来由

虽然SK组合子早有所闻,但这两个字母所代表的意思却一直不知道,原来是出自于《To Mock a Mockingbird and Other Logic Puzzles》这本书,作者用starlingkestrel这两只鸟来演绎哥德尔的证明。SK是这两只鸟的缩写,我是看到这篇Blog才了解到的。

早先只知道starlingkestrel是twitter的消息中间件产品,原来产品名还有这个来由。

我所理解的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的含义是什么。