我所理解的monad(7):把monad看做行为的组合子

先从最简单的情况开始,我们用monad封装一段执行逻辑,然后提供一个map组合子,可以组合后续行为:

// 一个不完善的monad
class M[A](inner: => A) {

    // 执行逻辑
    def apply() = inner

    // 组合当前行为与后续行为,返回一个新的monad
    def map[B](next: A=>B): M[B] = new M(next(inner))
}

用上面的例子模拟几个行为的组合:

scala> val first = new M({println("first"); "111"})
first: M[String] = M@745b171c

scala> val second = first.map(x => {println("second"); x.toInt})
second: M[Int] = M@155f28dc

scala> val third = second.map(x => {println("third"); x + 200})
third: M[Int] = M@b345419

scala> third()
first
second
third
res0: Int = 311

看上去对行为的组合也不过如此,其实在Function1这个类里已经提供了对只有一个参数的函数的组合:

scala> class A; class B; class C

scala> val f1: A=>B = (a:A) => new B

scala> val f2: B=>C = (b:B) => new C

scala> val f3 = f1 andThen f2
f3: A => C = <function1>

Function1里的andThen方法可以把前面函数的结果交给后边的函数处理,A=>BB=>C 组成函数 A=>C

这样看上去我们当前实现的monad和Function1有些相似,封装了一段行为,提供方法将下一个行为组合成新的行为(可以不断的组合下去),在java里我们可以对比Command模式和Composite模式。

真实世界的”行为”(Action),普通函数的问题

1) 结果的不确定性,行为链的校验问题

这个不完善的monad已经可以做一些事情,但有个很显著的问题,只能组合”普通函数(plain)”,所谓普通函数是指结果类型就是我们想要的数据类型。

比如f: A=>B 这个函数可以表示一个行为,这个行为最终得到的数据类型是B,但如果这个行为遇到异常,或者返回为null,这时我们的组合过程会如何?

这意味着我们必须在组合过程中判断每个函数的结果是否合法,只有合法的情况下,才能与下一步组合。你可能会想把这些判断放在组合逻辑里不就得了吗?

def map[B](next: A=>B): M[B] = { 
        val result = inner  // 执行了当前行为
        if(result != null) {
            new M(next(result))
        }else {
            null.asInstanceOf[M[B]]
        }
    }

上面的情况不是我们希望的,因为要判断当前行为(inner)的结果是否符合传递给下一个行为,只有执行当前行为才能拿到结果。而我们希望组合子做的是先把所有行为组合起来,最后再一并执行。

看来只能要求next函数在实现的时候做了异常检测,但即使next函数做了判断,也不一定完美;因为行为已经先被组合好了,执行的时候,链上的每个函数仍会被调用。假设组合了多个函数,执行时中间的一个函数即使为null,仍会传递给下一个执行(下一个也必须也对参数检测),其实这个时候已经没有必要传递下去了

在scala里对这种结果不确定的情况,提供了一个专门的Option,它有两个子类:SomeNone,其中Some表示结果是一个正常值,可以通过模式匹配来获取到这个值,而None则表示为空的情况。

如果我们Option来表示我们前面的行为,可以写为:f: A=>Option[B],即结果被一个富类型给包装起来,它表示结果可能有值,也可能为空。

2) 副作用的问题

另外一个真实世界中无法用函数式完美解决的问题是IO操作,因为IO无论如何总要伴随状态的产生或变化(也就是副作用)

一段常见的举例片段:

def read(state: State) = {
    // 返回下一状态和读取到的字符串
    (state.nextState, readLine)
}

def write(state: State, str: String) = {
    //返回下一状态,和字符串处理的结果
    //这里是print返回为Unit类型,所以最终返回一个State和Unit的二元组
    (state.nextState, println(str))
}

这两个函数类型为State => (State, String)(State,String) => (State, Unit) 在入参和出参里都伴随State,是一种”不纯粹”的函数,因为每次都执行状态都不一样,即使两次的字符串是一样的,状态也是不同的。这是一种典型的“非引用透明”问题,这样的函数无法满足结合率,函数的组合性无法保障。

要实现组合特性,需要把函数转换为符合“引用透明”的特性,我们可以通过柯里化来把两个函数转化为高阶函数:

def read = 
    (state: State) => (state.nextState, readLine)

def write(str: String) = 
    (state: State) => (state.nextState, println(str))

现在这两个函数相当于只是构造了行为,要执行它们需要后续传入“状态”才行;等于把执行推迟了;同时这两个函数现在符合“引用透明”特性了。

再进一步,为了把State在构造行为的时候给隐藏起来,我们继续重构:

class IOAction[A](expression: =>A) extends Function1[State, (State,A)] { 

    def apply(s:State) = (state.next, expression) 
}

def read = new IOAction[String](readLine)

def write(str: String) = new IOAction[Unit](println(str))

现在我们可以把read看做是一个 () => IOAction[String] 的函数,write则是:String => IOAction[Unit]的函数。

用一个”富类型”表示行为的结果

我们看到现实世界的行为,除了可以用A=>B这样的plain function描述,还有A=>Option[B]A=>IOAction[B] 这种结果是一个富类型的函数来描述。我们把后两种统一描述为:

A => Result[B]

当我们要组合一个这种形式的行为时,不能再使用map,而是flatMap组合子。

实际上,我们一开始就提到过map并不是必须的方法,flatMap才是,可以把map看做只是一种特例。把行为都用统一形式A => Result[B] 来描述,对于普通的A=>B也可以转为A=>Result[B]

现在我们看几个flatMap的例子,先看一个Option的实际例子:

scala> Some({println("111"); new A}).
        flatMap(a => {println("222");Some(new B)}).
        flatMap(b => {println("333"); None}).
        flatMap(c => {println("444"); Some(new D)})
111
222
333
res14: Option[D] = None

上面的例子看到,在组合第三步的时候,得到None,后边的第四步c => {println("444"); Some(new D)}没有被执行。这是因为None与后续的行为结合时,会忽略后续的行为。

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

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