我所理解的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)做参数。