月度归档:2013年06月

scala雾中风景(5): 中缀表达

scala中的中缀表达在3个地方存在:操作符、模式匹配、类型声明

1)中缀操作符最常见: a + bx foo y 里的+foo都是中缀操作符(严格的说scala里没有操作符,其实都是方法)。

其中需要注意的一点是名称最后以“:”结尾的,调用顺序与普通中缀操作符想反:从右往左。比如h :: t 实际是 t.::(h),它的意义在于可以让表达看起来更“顺眼”一些。比如我们自定义一个:

// 一个Cache单例,提供了 >>: 方法
scala> object Cache { def >>:(data:String) { println(data) } }
defined module Cache

scala> "myData" >>: Cache
myData

上面的方法很直观,让人一看就容易理解是把数据追加到cache中。还可以支持连续操作,稍修改一下:

scala> object Cache { def >>:(data:String):Cache.type = { println(data); Cache } }
defined module Cache

scala> "data2" >>: "data1" >>: Cache
data1
data2
res6: Cache.type = Cache$@45d2d12f

实际中,最常见的从右往左结合的中缀操作符是 List:: 方法

scala> val list = List()
list: List[Nothing] = List()

scala> "A" :: "B" :: list
res4: List[String] = List(A, B)

2) 当一个高阶类型有2个参数化类型,比如

scala> class Foo[A,B]

在声明变量类型时,也可以用 A Foo B 中缀形式来表达,Foo也称为中缀类型

scala> val x: Int Foo String = null

Int Foo String 等同于 Foo[Int,String]

3) 包含两个参数的构造器,在模式匹配时也可以用中缀表达

scala> case class Cons(a:String,b:String)
defined class Cons

scala> val x = Cons("one", "two")
x: Cons = Cons(one,two)

scala> x match { case "one" Cons "two" => println("ok") }
ok

"one" Cons "two" 等同于 Cons("one", "two")

对于2)和3)似乎也体现了某种一致性,不过暂对中缀类型的好处没有体会,对于类型系统中的这种风格也还不了解,暂不做比较。

现实中有个很容易迷惑人的地方,常用的 List ,即存在了一个:: 方法, 也存在了一个:: 名字的case类(List的子类)。

所以,构造一个list可以通过::的伴生对象提供的工厂方法,也可以通过Nil的::方法

scala> val l = ::("A",Nil) // 这里::是伴生对象, 相当于 ::.apply()
l: scala.collection.immutable.::[String] = List(A)

scala> val l2 = "A" :: Nil // 这里::是方法, 相当于 Nil.::()
l2: List[String] = List(A)

scala> l == l2
res1: Boolean = true

在模式匹配时,可以用中缀形式:

// 这里::是伴生对象,相当于 ::.unapply()
case head :: tail => …

所以::在不同的场景,意思不同,有时是方法名,有时是伴生对象名。这个设计,最初了解时很爱吐槽。但它提供了一种看上去很一致的表象,在中缀形式下都是表示”头”与”尾”的连接。

scala雾中风景(4): Unit类型

这个例子是一次错误的尝试时发现的,通常我们不太会用Unit类型声明参数,更多情况它是出现在函数类型声明里的出参部分(如 String=>Unit)。这个例子仅用作案例分析,先考虑下面的方法执行结果会如何?

scala> def foo(p:Unit) = {println("hi")}
foo: (p: Unit)Unit

scala> foo(2)

直觉上,感觉编译会报错,类型不匹配么,声明Unit类型,传入的确实Int类型。

实际上尝试一下会发现,它编译和运行都很正常。甚至无所谓你传入几个参数,或什么类型:

scala> foo(2,3,"OK")
hi

都能正常运行,看起来太诡异了。这背后隐含了编译器对Unit类型变量在赋值时的处理逻辑。

Unit类型是值类型,全局只存在唯一的值:()

scala> val a:Unit = ()
a: Unit = ()

若尝试把其它类型的值赋给它,也ok:

scala> val a:Unit = 2
a: Unit = ()    // 暂忽略编译器的警告,跟我们要关注的无关

诊断一下:

$ scala -nocompdaemon -Xprint:typer  -e 'val a:Unit = 2'
… 
private[this] val a: Unit = {
    2;
    ()  // 编译器自动增加了一个Unit的值:()
};
…

原因是编译对待等号右边的表达式,看待成为“行为”,会把这段“行为”统一放入花括号里。
并判断最后一句表达式的值是不是Unit类型的,如果不是则自动增加一个值:()

所以等号右边的 2 最终被转化为 { 2; () } 所以 foo(2,3,"OK") 也是被翻译为了

foo( {(2, 3, "OK"); ()} )

参数封装在一个tuple里,在最后返回一个 ()

再探究一步,Unit类型通常是用于声明方法返回值的,比如:

def foo:Unit = 2

它被翻译为:

def foo: Unit = {
    2;
    () // 编译器判断结果返回不是Unit类型的话,自动在最后返回()
}

当Unit用在值的类型时,编译器保持与方法一致的处理逻辑。

小结:通常Unit只用来声明函数或方法的返回值,其他场景基本是没有意义的。

scala雾中风景(3): for表达式的背后

这个例子是以前从scala-user邮件列表看到的,我借用这里例子加工了一下,这是一个for表达式转换的细节

//有一个map,里面有一些自定义类型的数据,然后在用下面的for进行操作
for((key,value) <- m; name=key) { 
    println(name) 
}

他在运行时发现上面的代码时发现key的hashCode会被调用,而正好这个hashCode的实现很复杂,导致效率很低。而他使用下面的写法则没有问题:

for((key,value) <- m) { 
    val name=key
    println(name) 
}

分析一下第一种写法为什么会导致hashCode方法被执行,先模拟一下:

scala> class MyKey { override def hashCode() = { println("key"); super.hashCode }}

scala> class MyValue { override def hashCode() = { println("value"); super.hashCode }}

// 把上面的k,v放入一个map;在放入Map的过程 k和v的hashCode方法都被执行了
scala> val m = Map[MyKey, MyValue](new MyKey() -> new MyValue())
key     
value   

// 模拟第一种for表达式
scala> for( (k,v) <- m; name = k ) { println(name+" do nothing") }
key     // k的hashCode被调用
$line3.$read$$iw$$iw$MyKey@63b97fd0 do nothing

是否这里又把k放入了Map?在上面的for表达式里,没有用到yield,是否直接被转换为foreach呢?

for表达式的展开和转换不在这里讨论,关于其语法背后的转换可以参考这篇文章。我们聚焦在这个案例的细节上。for表达式可以这样描述:

for([pattern <- generator; definition*]+; filter* )
    [yield] expression

在for小括号(也可以用花括号)内部由一个或多个 p <- generator; definition* 以及0个或多个filter组成。后跟着一个可选的yield关键字,以及后续的逻辑表达。

p <- generator; definition* 这句再展开,由一个 p <- generator 以及0个或多个definition组成。

这个问题的细节就在于有没有definition对for表达式在转换时的影响;也就是说 for(p <- generator)for(p <- generator; definition) 是不一样的。

没有yield关键字,for((key,value) <- m) 直接翻译为

m.foreach(…)

for((key,value) <- m; name=key) 被翻译为

m.map(…).foreach(…)

为什么中间多了一次map操作?我们通过一个简单例子来看:

scala> import reflect.runtime.universe._

scala> val list = List("A","B","C")

scala> reify( for(e <- list; x=e;y=e) { println(x+y) } )
res1: reflect.runtime.universe.Expr[Unit] =
Expr[Unit]($read.list.map(((e) => {
    val x = e;
    val y = e;
    Tuple3.apply(e, x, y)
}))(List.canBuildFrom).foreach(((x$1) => x$1: @unchecked match {
    case Tuple3((e @ _), (x @ _), (y @ _)) => Predef.println(x.$plus(y))
})))

从reify的结果可以看到,对于for(e <- list; x=e; y=e) 里面的x=ey=e两个definition中的变量x,y与e一同用一个tuple封装起来,即map的结果得到的是一个 List[Tuple3] 类型的数据。随后再对这个新结果进行foreach

所以最初的问题是因为for里面存着了一个definition,而导致转换过程多了一次map,也就是创建了一个新的Map[Tuple2],并把数据放入新Map,在这个过程导致了hashCode的调用。

小结:对于for表达式要知道背后会被转换为什么,不要滥用for的语法糖,误用导致低效率。

scala雾中风景(2): 小括号与花括号

下面的问题,表面上看是小括号与花括号的问题。

// map方法这样写不能编译通过
scala> List(2).map( case 2 => "OK" )

// 换做花括号就可以了
scala> List(2).map{ case 2 => "OK" }

不了解原因的话,觉得很诡异。分析一下,首先,map方法接受一个函数,这个函数将List中的元素映射为其他类型。

实际上case 2 => "OK" 不是一段lambda表达式(也就是说它不是函数),它是一段模式匹配语句。
那为什么在第二行可以编译通过呢?

稍微有点基础的话,会清楚方法的花括号有2种意思:
1)scala中函数的小括号,可以用花括号来表示,即foo{xx}foo(xx)是一回事儿。
2)对于只有一个参数的方法,其小括号是可以省略的,map(lambda)可写为 map lambda,即这块{case 2 => "OK"} 连同花括号整体是一个lambda(函数字面量)。

这儿显然是第2个(追究原因就要看编译器在语法解析式的优先级了,看样子把花括号对待为lambda字面量的一部分要高于把花括号当作小括号来对待),那么为什么加了花括号的{case 2 => "OK" }就可以当作一段函数字面量?

这要引出偏函数的概念,所谓偏函数(也叫部分函数)与完全函数想对应,普通的方法都是完全函数,即 f(i:Int) = xxx 是将所有Int类型作为参数的,是对整个Int集的映射;而偏函数则是对部分数据的映射,比如上面{case 2=> "OK" }就仅仅只对2做了映射。偏函数的实现都是通过模式匹配来表达的。

scala> val p:PartialFunction[Int,String] = { case 2 => "OK" }

因为偏函数是通过 { case x => y } 这种特殊的方式来描述的,上面的{case 2=>"OK"}就被当作了一段偏函数字面量,而偏函数背后的类型PartialFunction[A,B]是继承自Function1[A,B]的,所以将这段匿名的偏函数传给map方法是ok的。

小结:表达式 {case x=>y}会被当作偏函数字面量。

scala雾中风景(1): lambda表达式的缩写

scala中的函数是可以像普通变量一样来传递的,也允许方法的参数是函数类型。运行时传递一个函数变量,或者用lambda表达式描述的一段匿名函数。比如:

// 普通函数
scala> def foo(s:String) = { println(s) }

// 高阶函数
scala> def hf(f:String=>Unit) = f("higher")

// 把普通函数赋值给变量f
scala> val f:String=>Unit = foo

// 上面的函数类型String=>Unit 也可以写为Function1[String,Unit]
scala>  val f:Function1[String,Unit] = foo

// 把变量 f 当作参数传递给高级函数hf
scala> hf(f)
higher

现在看看以lambda的形式

scala> hf((s:String)=>println(s))
higher

这里使用lambda表达式 (s:String) => println(s) 作为匿名函数传入的,有趣的是,它可以简化:

scala> hf(s=>println(s)) // 第1个简化版本
higher

scala> hf(println(_)) // 第2个简化版本
higher

scala> hf(println _) // 第3个简化版本
higher

scala> hf(println) // 第4个简化版本
higher

上面的简化版本里前面的都好理解。第1个版本省略了s的类型,这是因为在定义hf时已经声明了参数类型为String=>Unit,编译器会把lambda表达式中的入参和出参按声明的类型来对待。

第2个版本则是采用了占位符的方式。它的形式为,对于所有的 x=>g(x) 都可以用占位符的形式写为:g(_),相当于省去了lambda表达式的入参和箭头部分,然后用占位符表示入参。

第3个简化版本是第2个版本的变种,是函数式语言里的一个习俗,scala继承了这一风格:当只有一个参数时,函数的小括号可写可不写。f(x) 可以写为 f x

//2014.9月更正,上面中划线部分是错误的说法,单独调用函数时小括号部分不可省略,单个参数的函数其小括号只有在 Object func param这种形式下可省略,比如 a equals b

第3个版本和第2个版本都是部分应用函数(partial applied function)的写法,当只有一个参数时,这两个写法是等价的。

让人困惑的是第4个版本!为什么连参数都可以省略?这还是一个lambda表达式么?是所有的lambda都可以缩写成这种形式么?

第4个版本的背后其实是编译器支持lambda的“eta转换”(可以参考之前的文章scala中的eta-conversion)。
简单的说就是对于lambda表达式中只有一个参数,并且箭头右边的逻辑是对入参执行一个函数:即 x => f(x)
则可以简写为f

所以第4个版本的简化就是eta转换,根据上面的说法,并不是所有的lambda表达式都可以缩写成这个样子的。

小结:lambda表达式的简化有时让人觉得云里雾里,但每个简化形式背后都有规则或习俗。eta-conversion是最容易迷惑的一种形式,它让表达式看上去不像是lambda表达式。

scala雾中风景(0): 序

最近看了一部分ruby作者松本行弘的新书《代码的未来》,对于未来语言的畅想有一段我比较认同:

通过反观过去半个世纪以来编程语言的进化方向,我认为编程语言绝对不会按照保罗.格雷厄姆所说,向着“小而干净”的方向进化。现在的编程语言,无论时功能上还是语法上都已经不是那样单纯了,虽然也曾经有人努力尝试将这些语言变得更小更简单,但包括保罗.格雷厄姆自己所设计的Arc在内,都决不能算是成功的尝试。

在我看来,编程语言的进化动机,不是工具和语言本身的简化,而是将通过这些工具和语言所得到的结果(解决方案)更简洁地表达出来。近半个世纪以来,编程语言不断提供愈发高度的抽象化特性,也正是为了达到这个目的。因此我们可以很自然地认为,这种趋势在将来也应该会继续保持。

在语言的进化中,scala是一门大胆尝试的语言。喜爱它的人认为它是一门聪明的语言,大胆进取,吸纳百家之长;而讨厌它的人则认为它复杂,语法过于灵活容易表达混乱,复杂的类型系统难以把握,不够纯粹,品味太烂。这是个哲学和审美问题,我不愿陷入争论,更偏向于实用主义。

对scala的批评和恐惧者中有很多是对于它的表现形式深感不爽的,尤其是没有函数式背景的初学者。实际上scala灵活的表达背后是有“历史习俗”或理论支撑的,如果了解了这些背后的东西,或许它不再那么晦涩。

这是我在向很多新人布道scala过程中发现的问题,促使我想通过一些具体的例子来理解其背后的缘由,一但熟悉了这些领域(主要是函数式)的一些概念和门路,再看scala就不容易被一些表面的东西所困惑。

注:这一系列针对初学scala的人。

翻译 monads-are-elephants 第三部分

原文:http://james-iry.blogspot.com/2007/10/monads-are-elephants-part-3.html

在这个系列我们提出了关于盲人与大象这个古老寓言的另一种观点。在这种观点里,从每个盲人那儿听取有限的解释,最终达到对大象很好的理解。

到目前我们还是站在monads的外面来看它。那让我们保持了很大的距离,现在可以看看它的内部了。真正决定大象成为大象的是它的DNA。Monads有它们自己的公共的DNA: monadic法则。

这篇文章要一下子消化它有点多,或许一段一段来读更有意义。在重读的时候把一个你已经理解的monad(例如List)带入规则会很有用。

Equality for All (相等性)

在我继续之前,我需要半正式的解释一下我在这些规则中使用(恒)等号的意思,比如 "f(x) ≡ g(x)" 数学上使用”=”表示相等性。我刻意避免使用”=”是为了避免与(用等号来)赋值相混淆。我是说左边的表达式与右边的表达式相同(is the same)。但现在个问题,什么是“相同”(same)。

第一,我不是在说引用一致(scala的eq方法),引用一致能满足我的定义,但这个要求太过强烈。第二,我不是必须要 == 或 equality,除非它的实现恰好是正确的。

我所说的”相同”是指两个对象在不直接或间接使用原始引用相等情况下是不可区分的。特别是,它可能对左边的表达式产生的对象与右边的(表达式产生的对象)内部存在微妙的差异,但仍可以说相同。例如,一个对象可能用一个迂回的间接层达到相同的结果。重要的是,从外部看,两个对象必须表现的一致。

对于“相同”还有点要注意的,我展示的所有的法则隐含假定没有副作用。对于副作用我会在文章的结尾更多描述。

Breaking the Law (打破法则)

不可避免的一些人会好奇“如果我打破法则会发生什么”?完整的答案取决于打破了什么法则,怎么打破的,我想先从整体上接近它。这儿再提醒一个其他来自数学分支的法则。

如果a,b,c是有理数,它们之间的乘法(*)遵循下面的法则:

a * 1 ≡ a
a * b ≡ b * a
(a * b) * c ≡ a * (b * c)

当然很容易创建一个有理数(RationalNumber)的类,并实现一个乘法(*)操作。但如果它不遵循这些法则,结果可能是令人困惑的。使用你的类的用户试着把数据塞入公式,却可能得到错的答案。坦白的说,很难打破这些法则却最终结果仍符合有理数乘法。

Monads不是有理数。但它们有法则帮助我们定义它们的操作方法。就像算数操作,它们(monads的操作方法)也有“公式”,你可以以有趣的方式来使用。例如,Scala的”for”表达式会用依赖这些法则的公式来进行展开。所以打破monad法则,就像打破”for”或使用者的一些其他预期。

介绍够了,开始解释monad法则,我将从另一个怪异的词语开始:函子(functor)

什么是函子(Functor)?

通常以”monad”或者”functor”开始的文章,很快就变成了一锅希腊字母。这是因为两个概念都来自一个叫做范畴论(category theory)的数学分支,完整的解释它们是一个数学练习。幸运的是,我的任务不是完整的解释它们而是用scala描述。

在Scala里functor是一个带有map方法和一些简单属性的类(class)。对于一个类型为M[A]的functor,map方法可以接受一个A=>B的函数,返回结果为M[B]。换句话说map用一个函数参数把M[A]转换为M[B]。重要的一点是要想到这个转换不需要任何循环,只要map就执行了转换。它可能是通过循环实现的,但也有可能不是。

Map的签名看上去像:

class M[A] {  
    def map[B](f: A => B):M[B] = ...  
}  
第一条Functor(函子)法则:Identity

我创建了一个名为identity的函数(译注: 这个identity就是幺半群里的单位元的概念)

def identity[A](x:A) = x  

这个明显对任何x都有这样的性质:

identity(x) ≡ x

它什么也没做,但这正是要点。它只是返回了参数(不管什么类型),不做任何改变。所以我们第一条functor法则,对于任何函子m:

F1. m map identity ≡ m // or equivalently *
F1b. m map {x => identity(x)} ≡ m // or equivalently
F1c. m map {x => x} ≡ m

换句话说,什么也没做,结果也不变。
聪明!不过,我要提醒你左边表达式可能返回一个内部结构与右边不同的对象。只要你没法分辨它们。
如果你创建一个functor不遵循这条法则,那么下面的将不能保证为true。看看为什么那样会导致困惑,假定m是一个List:

F1d. for (x <- m) yield x ≡ m
第二条Functor法则:Composition(组合)

第二条functor法则指定了几个”map”组合在一起的方式。

F2. m map g map f ≡ m map {x => f(g(x))} 

对m使用函数g进行map然后在对结果用函数f进行map,它与对m使用 f(g(x)) 来进行map是相同的。(译注:这也是幺半群里的结合律的概念)组合法则允许程序员把所有的事情一块儿干,或伸展到多个语句里。基于这条法则,程序员可以总假定下面的能工作:

val result1 = m map (f compose g)  
val temp = m map g  
val result2 =  temp map f  
assert result1 == result2  

在“for”表达式中,这条法则看起来让人眼睛疼。

F2b. for (y<- (for (x <-m) yield g(x)) yield f(y) ≡ for (x <- m) yield f(g(x))

Functors 与 Monads

你或许现在已经猜到,所有monads都是函子(functors),所以他们必须遵循functor法则。实际上,functor法则可以从monad法则中推导出来。只是因为functor法则简单且更容易搞定。

提醒,一个scala monad同时有map和flatMap方法,同下面的签名:

class M[A] {  
    def map[B](f: A => B):M[B] = ...  
    def flatMap[B](f: A=> M[B]): M[B] = ...  
}  

此外,我在这儿呈现的法则将基于”unit”。”unit”表示一个单个参数的构造器或类似下面签名的工厂方法:

def unit[A](x:A):M[A] = ...  

“unit”不应该被认为是字面名字的函数或方法,除非你想要。scala没有规定或使用它,但它是monads的重要一部分。任何满足这个签名和行为的函数,依据monad法则都可以。通常通过case类可以快捷的创建一个monad M,或者通过在这个类的伴生对象中定义个专用的apply(x:A):M[A]方法,这样M(x)的行为就是unit(x)

Functor/Monad连接法则:第零条法则

在这个系列的第一部分,我介绍过下面的关系:

FM1. m map f ≡ m flatMap {x => unit(f(x))}

这条法则单独来说没什么,但它可以在这三个概念间创建一个连接:unit, map, 和flatMap。这条法则可以使用”for”很好的表达:

FM1a. for (x <- m) yield f(x) ≡ for (x <- m; y <- unit(f(x))) yield y

回顾Flatten

在第一篇文章,我提到”flatten”或”join”的概念,用来转换一个monad的类型,M[M[A]]到M[A],但没有正式描述它。在那篇文章我说flatMap是一个map之后伴随flatten。

FL1. m flatMap f ≡ flatten(m map f)

这给出一个非常简单的flatten定义:

flatten(m map identity) ≡ m flatMap identity // 用identity替代f
FL1a. flatten(m) ≡ m flatMap identity // by F1

所以对m进行flattening 与对m用identity函数进行flatMapping是相同的。
在这篇文章我不会用flatten法则,因为flatten不是scala必须的,但这是个很好的概念,你可以放到你的后裤兜里,如果flatMap看起来太抽象的话。

第一条Monad法则:Identity

第一条也是最简单的monad法则是monad identity法则

M1. m flatMap unit ≡ m // or equivalently
M1a. m flatMap {x => unit(x)} ≡ m

连接器法则连接了3个概念,这条法则聚焦在它们两者之间的关系上。解读这条法则的一种方式是:某种意义上,flatMap总会把unit做的事情给还原。(译注:请google “monad与太空衣”,这个比喻很形象,unit的行为是给宇航员穿上太空衣,而flatMap则是脱掉) 再次提醒,左边结果的对象可能实际上内部有差异,只要它行为与”m”一致就行。

使用identity和连接法则,我们可以推导出functor的 identity 法则

m flatMap {x => unit(x)} ≡ m // M1a
m flatMap {x => unit(identity(x))}≡ m // identity
F1b. m map {x => identity(x)} ≡ m // by FM1

反过来推导也一样。在”for”表达式里monad identity法则非常直接。

M1c. for (x <- m; y <- unit(x)) yield y ≡ m

第二条Monad法则:Unit(构造方法)

Monads有一个逆向的monad identity法则:

M2. unit(x) flatMap f ≡ f(x) // or equivalently
M2a. unit(x) flatMap {y => f(y)} ≡ f(x)

这条法则基本上是说 unit(x) 必须以某种方式保存”x”,如果把函数f传给它,要能够计算出f(x)。正是在这个意义上,可以说任何monad都是一种类型的容器(但这不意味着monad是一个集合)。

在”for”表达式中,unit法则变为:

M2b. for (y <- unit(x); result <- f(y)) yield result ≡ f(x)

这条法则对unit以及它与map的关系,还有另一个含义

unit(x) map f ≡ unit(x) map f     // no, really, it does!
unit(x) map f ≡ unit(x) flatMap {y => unit(f(y))} // by FM1
M2c. unit(x) map f ≡ unit(f(x)) // by M2a

换句话说,如果我们通过一个参数”x”创建一个monad实例,然后传入函数f进行map;那么跟我们通过 f(x)的结果创建一个monad实例是一样的。在”for”表达式里

M2d. for (y <- unit(x)) yield f(y) ≡ unit(f(x))

第三条Monad法则:Composition(组合)

组合法则是一条怎么让一系列flatMap一起工作的规则。

M3. m flatMap g flatMap f ≡ m flatMap {x => g(x) flatMap f} // or equivalently

M3a. m flatMap {x => g(x)} flatMap {y => f(y)} ≡ m flatMap {x => g(x) flatMap {y => f(y) }}

这是所有法则中最难懂的,花点时间去领会。

在左边,我们对一个monad实例m,先通过函数g进行flatMap,然后对结果再通过函数f进行flatMap。在右边,我们创建一个匿名函数 x => g(x) flatMap f ,即对传入的参数x先执行函数g,然后在使用函数f进行flatMap,最终m使用这个匿名函数进行flatMap。两边有相同的结果。

在”for”表达式里组合法则会让你惶恐的逃离,所以我建议略过它。

M3b.for (a <- m;b <- g(a);result <- f(b)) yield result 
     ≡ 
    for(a <- m; result <- for(b < g(a); temp <- f(b)) yield temp) yield result

从这一法则,我们可以推导出函子组合法则。也就是说打破了monad组合法则,也打破了(更简单的)函子组合(functor composition)。

证明涉及了针对这个问题抛出的若干monad法则,不是给胆小的人看的。

m map g map f ≡ m map g map f   // I'm pretty sure
m map g map f ≡ m flatMap {x => unit(g(x))} flatMap {y => unit(f(y))} // by FM1, twice
m map g map f ≡ m flatMap {x => unit(g(x)) flatMap {y => unit(f(y))}} // by M3a
m map g map f ≡ m flatMap {x => unit(g(x)) map {y => f(y)}} // by FM1a
m map g map f ≡ m flatMap {x => unit(f(g(x))} // by M2c
F2. m map g map f ≡ m map {x => f(g(x))} // by FM1a

总是失败的Zeros (Total Loser Zeros)

List有Nil(表示一个空List),Option有None。Nil和None看起来有某些相似之处:它们都表示空 (emptiness)。形式上它们被称为monadic zeros(译注: 可理解为单位元

一个monad可以有多个zeros。举例来说,想象一个类似Option的monad,我们称为Result。一个Result可以是Success(value)或者Failure(msg) 两者中的一个。Failure构造器有一个String类型参数表示为什么发生失败。对Result来说,每一个不同的failure对象是一个不同的zero。

一个monad可以没有zeros。不过所有的集合monads都有zeros(空集合),其他类型的monads可以有或没有,取决于是否它们有一个遵循zero法则的”emptiness”或”failure”的概念

第一条zero法则:Identity

如果mzero是一个monadic zero那么对于任何函数f,它的意义是:

MZ1. mzero flatMap f ≡ mzero

翻译成德克萨斯话: if t’ain’t nothin’ to start with then t’ain’t gonna be nothin’ after neither.

这一法则让我们派生出另外的zero law

mzero map f ≡ mzero map f // identity
mzero map f ≡ mzero flatMap {x => unit(f(x)) // by FM1
MZ1b. mzero map f ≡ mzero // by MZ1

对一个zero使用任何函数来map,结果都是一个zero。这条法则明确zero是不一样的;unit(null)或一些其他构造方法可以构造出的“空,但不是”真空”(empty enough)。

看看为什么这样:

unit(null) map {x => "Nope, not empty enough to be a zero"} 
≡ 
unit("Nope, not empty enough to be a zero")

第二条 zero法则:M to Zero in Nothing Flat

zero identity法则的反面看起来像:

MZ2. m flatMap {x => mzero} ≡ mzero

把所有元素都替换为nothing,结果也是nothing,嗯。。。当然。这条法则确立了你对如何将zeros进行”flatten”的直觉。

第三和第四 zero法则: Plus (相加操作)

Monads有zeros,也可以有类似加法的操作。对于List,“加法”(plus)等价于":::",对于Option就是"orElse"。不管它叫什么,签名类似下面:

class M[A] {  
    ...  
    def plus(other:M[B >: A]): M[B] = ...  
}  

加法(plus)要遵循下面两个法则才有意义:任何东西与zero相加还是那个东西

MZ3. mzero plus m ≡ m
MZ4. m plus mzero ≡ m

如果两者都不是monadic zero的话,加法法则不会说 "m" + "n" 是什么。这完全交由你决定,不同的monad会有不同的实现。典型的,如果monad的串联有意义,加法(plus)就是串联的结果。否则,它会表现的像一个或(or),返回第一个non-zero值。

回顾Filtering

在前边的部分,我简单提到过filter可以看做纯粹的monadic术语。monadic zeros只是一个小诀窍(trick)。提醒,一个可过滤的monad看起来像是:

class M[A] {  
    def map[B](f: A => B):M[B] = ...  
    def flatMap[B](f: A=> M[B]): M[B] = ...  
    def filter(p: A=> Boolean): M[A] = ...  
}  

过滤方法完全可以用一条简单规则来描述:

FIL1. m filter p ≡ m flatMap {x => if(p(x)) unit(x) else mzero}

我们创建一个匿名函数,接受x返回unit(x)mzero(取决于x的断定结果)。接着用这个匿名函数对m进flatMap。这儿有几个结果:

m filter {x => true} ≡ m filter {x => true} // identity
m filter {x => true} ≡ m flatMap {x => if (true) unit(x) else mzero} // by FIL1
m filter {x => true} ≡ m flatMap {x => unit(x)} // by definition of if
FIL1a. m filter {x => true} ≡ m // by M1

所以用常量”true”过滤结果是同一对象。相反:

m filter {x => false} ≡ m filter {x => false} // identity
m filter {x => false} ≡ m flatMap {x => if (false) unit(x) else mzero} // by FIL1
m filter {x => false} ≡ m flatMap {x => mzero} // by definition of if
FIL1b. m filter {x => false} ≡ mzero // by MZ1

用常量”false”过滤结果是一个monadic zero。

副作用

贯穿这篇文章我隐含假定了没有副作用。让我们重新看第二条: 函子法则(functor law)

m map g map f ≡ m map {x => (f(g(x)) }

如果m是一个包含若干元素的List,那么左边和右边的操作的顺序将不同。在左边,对m中的每个元素都会调用g,然后再对结果中的每个元素调用f。在右边,对函数f和函数g的调用是交织的。如果f和g有副作用,比如执行IO或修改了其他变量的状态,有人将一个表达式重构为另一个,那么系统可能会有不同的表现。

注意:在定义或使用map,flatMap和filter的时候要避免副作用。

坚持foreach的副作用,要在每次定义时要给出一个警告标记,重排序可能会引起不同的行为。说到这儿,foreach的法则在哪儿?嗯,鉴于foreach没有返回任何结果,唯一可以表达的规则是:

m foreach f ≡ ()

这将意味着foreach什么也没干(译注:上面的小括号表示Unit类型实例)。从一个纯函数式意义上: 它用f函数转换m为一个空(void)结果。但是foreach意味着副作用–它是命令式结构。

第三部分的结论

直到现在,聚焦在Option和List让你用直觉感受monads,通过这篇文章最终你会看到真正让monad成为monad的是什么。结果表明monad法则与集合没有关系,它们比集合更“泛”(general)。只不过monad法则恰好对集合非常适用。

在第四部分,我将呈现一个已发育成熟的大象 monad,与集合没有任何相似,在适当的光线下它仅仅是个容器。

下面是Scala与Haskell的法则对比

Scala Haskell
FM1 m map f ≡ m flatMap {x => unit(f(x))} fmap f m ≡ m >>= \x -> return (f x)
M1 m flatMap unit ≡ m m >>= return ≡ m
M2 unit(x) flatMap f ≡ f(x) (return x) >>= f ≡ f x
M3 m flatMap g flatMap f ≡ m flatMap {x => g(x) flatMap f} (m >>= f) >>= g ≡ m >>= (\x -> f x >>= g)
MZ1 mzero flatMap f ≡ mzero mzero >>= f ≡ mzero
MZ2 m flatMap {x => mzero} ≡ mzero m >>= (\x -> mzero) ≡ mzero
MZ3 mzero plus m ≡ m mzero ‘mplus’ m ≡ m
MZ4 m plus mzero ≡ m m ‘mplus’ mzero ≡ m
FIL1 m filter p ≡ m flatMap {x => if(p(x)) unit(x) else mzero} mfilter p m ≡ m >>= (\x -> if p x then return x else mzero)

一次狼狈的骑行

前天(周五) 早上6点半从杭州骑自行车出发去北仑,出门的时候已经下起雨来,但是既然出门了就不想就这么回去。
骑了十几分钟后,雨变大,在路边停下,把雨披披上。继续骑行,在经过灵隐路的时候,看到一个车站的牌子上写着“立马回头”。心想这该不是给我的警告吧?

经过虎跑然后上一桥,大桥在钱塘江的一片雨雾中很美,之前住在滨江的时候曾想过有空在下雨天拍几张大桥的照片,但一直未去做。沿着滨康路、金城路20多公里,上104国道,雨一直在持续。鞋子不防雨,已经湿透,之前在市区的路段红绿灯比较多,速度较慢,上了国道之后速度快了一些,但因为下雨的原因速度还是慢很多。

快要达到绍兴城区的时候,后车胎扁了,我没有工具和备胎(也不会补胎),一个人骑行碰到这种事是最麻烦的,尤其此时还下着雨。心里想着难道那个“立马回头”的警告灵验了?不过也没什么比这更糟糕的了,平静的接受吧,幸运的是这段路已经接近城区,路边有很多仓库和汽车维修点,推着车走了十几分钟问了几个人,后来一个老人告诉我反方向有个修自行车的铺子,又往回走了二十分钟,在那个修车铺子里本想让老板直接换个内胎,但他那儿的内胎只有一种,不是给山地车用的,气孔跟我自己的打气筒不匹配,只好补一下了。

这一下耽误了近一个小时,此时不过骑了60多公里,对后续130公里的路程感觉比较紧张。继续上路后在经过绍兴城区的时候,又走错了路,本想从二环北路,直接绕城而过,却穿过市区了。在市区速度大大降下来,不过也让我看到了绍兴的另一面。我大概在七八年前来过一次,当时主要去了几个旅游景点,只是觉得绍兴还算别致,小家碧玉的江南城市;并没有感到现代化的一面,这次穿过市区看到了它高楼林立的一面。

出绍兴后,继续沿着国道104,已经是下午一点多,后边还有一大半的路程,让我信心越来越不足,加上下雨,速度始终起不来,估算着起到北仑要下半夜了。于是做好了最坏打算:放弃。先继续往前骑,看能到什么地方吧,不行了再打电话给老婆让她开车来接我。后续只按照正常速度前进,体力已经消耗很多,路上吃了一些士力架和饼干,能量补充的不是很充分。

沿路遇到的木偶警察,以及像是被劈歪的避雷针?

经过上虞不远处

小越镇上的吴越公主

从104国道在靠近上虞的地方切换到329国道,然后又切换到省道s61上,终于在快到余姚的时候,感觉颈椎难受,已快到下午4点多;后边的80公里放弃,打电话让老婆开车过来接我。

这是一次狼狈的骑行,有天气的因素,不过更重要的是自己已经有一年多没有骑过长距离的了,准备很不充足,始终没有一种兴奋感。

翻译 monads-are-elephants 第二部分

原文:http://james-iry.blogspot.com/2007/10/monads-are-elephants-part-2.html

在第一部分,我通过盲人摸象的寓言介绍了Scala的monads。正常情况我们认为每个盲人所说的不会让你对大象的理解更接近一些。但我提出另一种观点,如果你听到了所有盲人对他们经历的描述,你很快会对大象建立一个令人惊叹的理解。

在第二部分,我将通过探索scala的monad相关语法糖“for-comprehaension”来更深的戳一下这个怪兽

一个简单的”For”

一个非常简单的”for”表达式,看起来像这样:

val ns = List(1, 2)  
val qs = for (n <- ns) yield n * 2  
assert (qs == List(2, 4))  

“for”可以读作 “for[each] n [in] ns yield n*2” 它看起来想一个循环,但它不是。这是我们的老朋友map的伪装。

val qs = ns map {n => n * 2}  

这儿的规则很简单

for (x <- expr) yield resultExpr  

展开为(注释1)

expr map {x => resultExpr}  

提醒,它等同于

expr flatMap {x => unit(resultExpr)}  

多一点的”For”

for(的括号)中只有一条表达式并不很有趣,让我们再加一些

val ns = List(1, 2)  
val os = List (4, 5)  
val qs = for (n <- ns; o <- os) yield n * o  
assert (qs == List (1*4, 1*5, 2*4, 2*5))  

这条”for”可以读作”for[each] n [in] ns [and each] o [in] os yield n*o” 这个形式的”for”看起来想一个嵌套循环,但它不过是map和flatMap。

val qs = ns flatMap {n => os map {o => n * o }}  

值得花一点时间理解一下。这儿是它怎么计算的:

val qs = ns flatMap {n => 
            os map { o => n * o } //1
          }

val qs = ns flatMap {n =>        //here
            List(n * 4, n * 5)  //上面的1
         }

val qs = List(1 * 4, 1 * 5, 2 * 4, 2 * 5) //上面的here

更多的表达式

让我们更进一步

val qs = for (n <- ns; o <- os; p <- ps) yield n * o * p  

这个”for”展开为

val qs = ns flatMap {n => 
            os flatMap {o =>   
                {ps map {p => n * o * p}}}}  

这个看起来与之前的那个相似。这是因为转换规则是递归的:

for(x1 <- expr1;...x <- expr) yield resultExpr  

转换为

expr1 flatMap {x1 =>   
    for(...;x <- expr) yield resultExpr  
}  

这条规则可以重复的应用(转换为flatMap),直到只剩下一条表达式,将被转换为map。这儿展示了编译器怎么展开 "val qs = for …"

1. val qs = for (n <- ns;  //第一个表达式
                o <- os;    //第二个
                p <- ps)    //第三个
            yield n * o * p


2. val qs = ns flatMap {n => //上面的第一个表达式,用flatMap翻译
                for(o <- os; 
                p <- ps) 
                yield n * o * p}

3. val qs = ns flatMap { n => 
                os flatMap {o => //第二个也用flatMap翻译
                for(p <- ps) 
                yield n * o * p}}

4. val qs = ns flatMap {n => os flatMap {o =>
                {ps map {p => n * o * p}}} //第三个(最后一个)用map翻译

命令式的”For”

“for”也有一个命令式(imperative)的版本,用于那些你只调用一个函数,并不在意副作用的情况。这种版本只用去掉yield声明。

val ns = List(1, 2)  
val os = List (4, 5)  
for (n <- ns; o <- os)  println(n * o) 

这个展开规则很像yield版本的,但用foreach替代了flatMap或map

ns foreach {n => os foreach {o => println(n * o) }}  

如果你不想使用命令式的”for”,你不需要实现foreach,但既然我们已经实现的map,foreach的实现是微不足道的。

class M[A] {  
    def map[B](f: A=> B) : M[B] = ...  
    def flatMap[B](f: A => M[B]) : M[B] = ...  
    def foreach[B](f: A=> B) : Unit = {  
        map(f)  
        ()  
    }  
}  

换句话说,foreach可以通过调用map并丢掉结果来实现。不过这么做运行时效率可能不好,所以scala允许你用自己的方式定义foreach。

带过滤的 “For”

到目前为止,monads建立在一些关键概念上。有这三个方法: map, flatMap和forEach 几乎所有的for都可实现。

Scala的”for”声明还有一个特征:”if”守护(guard)。看一个例子:

val names = List("Abe", "Beth", "Bob", "Mary")  
val bNames = for (bName <- names;  
                if bName(0) == 'B'  
            ) yield bName + " is a name starting with B"  

assert(bNames == List(
    "Beth is a name starting with B",   
    "Bob is a name starting with B"))  

“if”守护会映射为一个叫做filter的方法。Filter接受一个判定函数(一个返回结果为true或false的函数)并创建一个新的monad过滤出那些与判定不匹配的元素。上面的for语句会翻译成下面的:

val bNames = (names filter { bName => bName(0) == 'B' }) 
             .map { bName =>   
                bName + " is a name starting with B"   
             }  

首先list过滤出名字以’B’开头的,然后对过滤后的list用一个追加一段字符” is a name” 的函数来进行map

不是所有的monads可以被过滤的。用容器来比拟,filtering或许可以删除全部的元素,而有些容器是不能为空的。对于这样的monads你不需要创建filter方法。

只要你不在”for”表达式中使用”if”守护,scala就不会抱怨。关于filter我在下一部分还有更多要说的,如何用纯粹的monadic术语定义来定义,什么样的monads不能被过滤。

第二部份结论

“For”是一个使用monads的简便方式。它的语法在使用List和其它集合时特别有用。但是”for”更通用(比monad),它展开为map,flatMap,foreach和filter。因此,map和flatMap在任何monad都应该定义。如果你想要monad是命令式的,可以定义foreach方法,它的实现也很轻松。filter可以在一些monads中定义,但另一些则不能。

"m map f" 可以实现为 "m flatMap { x => unit(x) }"
"m foreach f" 可以根据map来实现,或根据 flatMap 来实现"m flatMap {x => unit(f(x));()}"。甚至 "m filter p" 也可以用 flatMap来实现(我将在下一次展示)。flatMap真是这头野兽的心脏。

记住monads是大象。我所绘画的monads目前都是强调集合特性。在第4部分,我将呈现一个不是集合的monad,只是某种抽象的容器。但在第4部分之前,第3部分需要介绍一些真正monads的属性:monadic法则。同时,这儿有个作弊抄展示 Haskell与Scala的相关性

Haskell Scala
do var1<- expn1

var2 <- expn2

expn3
for {var1 <- expn1;

var2 <- expn2;

result <- expn3

} yield result
do var1 <- expn1

var2 <- expn2

return expn3
for {var1 <- expn1;

var2 <- expn2;

} yield expn3
do var1 <- expn1 >> expn2

return expn3
for {_ <- expn1;

var1 <- expn2

} yield expn3
脚注

1) Scala语言规范里实际指定”for”扩展使用模式匹配。实际的规范扩展了我在这儿呈现的规则,允许在左边使用 “<-“来进行模式匹配。太深入钻研的话会使这篇文章模糊混乱(涉及到太多其他概念)。

翻译 monads-are-elephants 第一部分

原文:http://james-iry.blogspot.com/2007/09/monads-are-elephants-part-1.html

介绍monads有点像互联网时代的家庭手工业。我想 “为什么要反对传统?”,但这篇文章将以Scala对待monads的方式来描述。

有个古老的寓言,讲述了几个瞎子第一次摸到大象。一个抱着大象的腿说:“它是一棵树”;另一个摸着大象的鼻子则说:“它是一条大蛇”;第三个则说:“它是一把扇子”。。。

从这个寓言我们可以得到个结论:古人相信视觉障碍者喜欢调戏大型哺乳动物(此句英文原意可能带有其它含义)。幸运的是我们生活在一个更开明的时代。我们也应该了解自己的局限,防止它阻碍我们把握事物的全貌,在某些方面,我们都如同盲人一般。

还有一点,与主要意图相反:通过一系列有限的解释,有可能更多的了解大局。如果你从没有看到过一个大象,人们告诉你:“它的腿粗的像树干”,“鼻子像一条蛇”,“尾巴像扫帚”,“耳朵像扇子”,等等,那么你很快就理解了。或许你自己的概念并不完美,但当你真正看到一头大象,它将归入到你脑海中已慢慢建立起来的图片。就像大象要踩到你一样,你会想“哇,它的腿真的像一颗树”。

Monads是容器类型

一个最常用的容器类型是List,我们将花点时间来说它。
我也在之前的文章中提到过Option类型。再提醒一下,Option要么是Some(value) 要么是 None
或许List与Option的关系并不那么清晰,这样理解可能有些帮助,你可以把Option看成一个萎缩的List,它只能容纳0或1这两个元素。树(Trees)和集(Sets)也可以当作monads。但要记得monads是一头大象,所以一些monads你不得不眯着点眼睛来把它看做容器。

Monads是参数化的(parameterized,可理解成泛型)。List是个有用的概念,但你需要知道List里面有什么。一个存放字符串的List (List[String]) 与存放整数的List (List[Int]) 是不同的。明显的从一个转换成另一个是有用的。不过这将引入下一个问题。

Monads支持高阶函数

高阶函数是一个将另一个函数作为参数,或返结果为函数的函数。Monads是定义了若干高阶函数的容器。既然我们谈论scala,monads有一系列的高阶”方法”(译注:在scala里函数与方法并不刻意对两个名词划清界限,很多情况下函数就是指方法,关于方法与函数的差异可在这个ppt中了解)。

map就是这样的一个高阶函数。如果你了解函数式语言,那么可能map已经以某种形式被你熟知。map方法接受一个函数,并对容器中的每一个元素应用改函数,返回一个新的容器。举例:

def double(x: Int) = 2 * x  
val xs = List(1, 2, 3)  
val doubles = xs map double  
// or val doubles = xs map {2 * _}  
assert(doubles == List(2, 4, 6))  

map方法的结果(新产生的容器)不改变Monad的性质(kind),但它可能会改变参数类型…

val one = Some(1)  
val oneString = one map {_.toString}  
assert(oneString == Some("1"))  

这儿 {_.toString} 的意思是对每个元素调用toString

Monads是可组合的(combinable)

现在,我们有一个配置库用来获取参数。对于任何参数,我们取得的都是 Option[String],换句话说我们能否取到一个String取决于这个参数有没有被定义(没有定义得到None)。另外,我们还有个 stringToInt的方法,接受一个String,如果字符串可以解析成Int的话返回Some[Int] ,否则返回None。如果我们尝试用map方法来组合它们,会遇到麻烦:

val opString : Option[String] = config fetchParam "MaxThreads"  
def stringToInt(string:String) : Option[Int] = ...  
val result = opString map stringToInt  

很不幸,我们把Option里面的每个元素执行map操作,并返回另一个Option。变量”result”现在是包含Option元素的Option,即Option[Option[Int]] 类型。这在大多情况下不太有用(我们期望结果是Option[Int])。

激励一个解决方案, 想象如果代替Option,我们使用List ( List[List[Int]]),换句话说一个包含了若干个List的List。假定这样的话我们只需要”flatten”:一个接受一组lists (List[List[A]]) 作为参数,并返回一个把所有结果连接在一起的单一的list(List[A]) 的函数(注释1)。

Option[Option[A]]的flatten函数(与List的相比)有些不同:

def flatten[A](outer:Option[Option[A]]) : Option[A] =
    outer match {  
        case None => None   
        case Some(inner) => inner   
    }  

如果外部Option为None,结果就是None。否则结果是内部的Option。

这两个flatten函数有相似的签名:接受一个 M[M[A]] 返回 M[A]. 但他们实现方式不同。其他的monads也会有它自己flatten的方式–甚至可能是很复杂的方式。这种可能的复杂也解释了为什么 monads会常常使用“join”替代“flatten”,“join”简洁的表示外部的monad与内部monad的某些方面可能会被组合(combined/joined)。我会继续用”flatten”,因为它符合我们的容器比喻。

现在,Scala不需要你显式的写flatten方法。但对于每个monad,必须要有flatMap方法(注释2)。什么是flatMap? 就像它的字面意思:执行map,然后把结果压扁(flattening)

class M[A] {  
    private def flatten[B](x:M[M[B]]) : M[B] = ...  
    def map[B](f: A => B) : M[B] = ...  
    def flatMap[B](f: A => M[B]) : M[B] = flatten(map(f))  
}  

有了flatten方法,我们再回到之前有问题的代码处:

val opString : Option[String] = config fetchParam "MaxThreads"  
def stringToInt(string:String) : Option[Int] = ...  
val result = opString flatMap stringToInt  

flatMap方法使我们最终得到的”result”是一个Option[Int]类型。如果我们想要,我们可以对result用一个Int=>Option[Foo]的函数来进行flatMap。然后我们可以用Foo=>Option[Bar]等等之类的函数进行flatMap。
如果深究的话,你会发现很多关于monads的论文使用”bind”一词替代”flatMap”,而Haskell里使用”>>=”操作符;它们都是一个概念。

Monads可以用不同的方式构造

我们看到了怎么使用map来构造一个flatMap方法。还有另一种可能的方式:先实现一个flatMap然后可以基于flatMap实现一个map。为了做到这一点我们需要引入更多概念。在大多monads的论文里称为”unit”的概念,在Haskell里它称为”return”。

Scala是一门面向对象的语言,所以相似的概念可以称为“单个参数构造器”(single argument constructor) 或“工厂”(factory)。基本上,unit接受一个A类型的值,返回一个M[A]类型的monad。
对于List,unit(x) == List(x) ,对于Option,unit(x) == Some(x)。(译注,这里的List(x)和Some(x)都是scala的伴生对象的工厂方法)

Scala不需要一个独立的”unit”函数,你写不写unit是一个风格问题。在写这个版本的map时我会显式的写unit方法,只是展示它怎么在内部使用的。

class M[A](value: A) {  
    private def unit[B] (value : B) = new M(value)  
    def map[B](f: A => B) : M[B] = flatMap {x => unit(f(x))}  
    def flatMap[B](f: A => M[B]) : M[B] = ...  
}  

在这个版本的 flatMap的实现不引用map或flatten,它将一气呵成的完成这两个操作。有趣的是map,它接受一个函数作为参数传入,并把它变成一个适用于flatMap的新函数,新函数看起来像 {x=>unit(f(x))} 意思是先对x执行f函数,然后在对f(x)的结果执行unit。

第一部分的结论

Scala中的monads必须有map和flatMap方法,map可以通过flatMap和一个构造器来实现,或者 flatMap可以通过map和flatten来实现。

flatMap是这头大象的心脏。当你刚开始了解monads,通过map和flatten有助于你构造第一个版本的flatMap。map通常是非常简单直接的。搞清楚flatten对什么有意义是难懂的部分。

当你进入的monads不是集合,你会发现 flatMap 应该先实现,然后map基于flatMap和unit来实现。

在第二部分,我将揭露Scala对monads的语法糖。在第三部分,我将展示大象的DNA:moands法则。最终,在第四部分,我将演示一个monad只能勉强算是一个容器。同时,这儿有个作弊抄比较各种有关monads的论文,Haskell和Scala

Generic Haskell Scala
M data M a

or

newtype M a

or

instance Monad (M a)
class M[A]

or

case class M[A]

or

trait M[A]
M a M a M[A]
unit v return v new M(v)

or

M(v)
map f m fmap f m m map f
bind f m m >>= f

or

f =<< m
m flatMap f
do for
脚注:

1)Scala标准库中的List包含了flatten方法。它非常平滑,但为了解释它我又不得不引入隐式转换,这是个重大干扰(隐式转换是scala里特有的,对monad没有直接的关系)。平滑的部分是flatten对List[List[A]]存在意义,而对 List[A]没有意义,然而Scala里的flatten方法定义在所有的List中,并且是静态的类型检查。

2)我在这儿用了一点简化。Scala不需要特别的方法名称来表示一个monad。你可以取任何方法名如 “germufaBitz” 或 “frizzleMuck”。然而如果你坚持使用map和flatMap的话,你将可以使用Scala的”for comprehensions”