翻译 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)

翻译 monads-are-elephants 第三部分》上有4条评论

  1. Pingback引用通告: 我所理解的monad(6):从组合子(combinator)说起 | 在路上

发表评论

电子邮件地址不会被公开。 必填项已用*标注