Monad 简明教程 -- Scala 表述

算数,代数到代数结构

最早我们学习算数,$1+1 = 2$。不久我们发现 $1 + 2 = 2 + 1$, $2 + 5 = 5 + 2$。于是我们提出了「代数」,用字母来表示任意的数字。如此便得到了交换律 $ a + b = b + a$。

之后我们发现 $a + b = b + a$, $ a * b = b * a $。既然他们都有相同的性质,那么也可以按照类似的思路,将相同的部分抽象出来,得到一个称之为代数结构的东西。我们可以用它来表示任何具有相同性质,比如交换律或者更复杂的的运算。

这样,我们便不再受限于已有的运算,而可以去定义任何合理的代数结构来满足我们的需求。下文说到的 Monoid,Functor,Applicative, Monad,都是根据我们的需要发明出来的东西。

难怪有人说「Monid不过是自函子范畴上的一个幺半群而已」。而所谓的「幺半群」,也就是代数结构的一种了。

Monoid

从最简单的Monid开始。一个 Monoid 可以定义为

trait Moioid[T] {
    def zero: T
    def op(l: T, r: T): T
}

其中 zero 是“零元”, 而 op 是满足结合律的二元运算,也就是说

(a op b) op c == a op (b op c) 
x op zero == x
zero op x == x

这里的op不一定满足交换律,所以零元要求满足后面的两个式子。 显然实数和矩阵的加法,乘法都满足这个代数结构。此外如果把op定义为连接字符串,zero定义为空字符串,那么也是满足这个代数结构的。

Functor

Functor 的定义为

trait Functor[C[_]]{
    def op[P,  Q](x: C[P])(f: P => Q): C[Q]
}

首先注意到,Functor 的定义中牵扯到了三个类型:PQ 和泛型 C 。通常也把C称为环境(Context)。它可以是 List[_]或者Option[_]等。而函数op 接受两个参数:x, f。这里的f不是一个值,而是一个P=>Q的函数。而op的作用,是利用fC[P] 变成 C[Q]

functor,有这些限制:

  1. 同一性: op(x)( v => v) = x
  2. 结合律: op( op( x, f1 ), f2) = op(x, f2(f1))

很多集合都是一个 functor,因为我们在上面都定义了 map 函数,而它完全的符合这里的需要。例如对于 List[T]

List[Int](1, 2, 3).map(v=>v.toString)

就完成了 List[Int]List[String]的一个变变换。 为了不至于混淆,在下面我们把 functor 里面的 op 称为 map

Applicative Functor

Applicative 的定义为

trait Applicative[C[_]] extends Functor[C]{
    def pure[P](x:P):C[P]
    def apply[P, Q](x:C[P])(C[P=>Q]):C[Q]   
}

比起 functorapplicative functor 多了两个函数: pureapply`。

pure的含义非常简单,它接受一个值,并把它放在环境之中。

apply函数则和 functor中的map函数比较相似,不同之处在于它接受的函数f也是在环境C中的。

同样,applicative functor也需要满足一些定律

  1. 同一性apply(x)(pure(x=>x)) = x

  2. 一致性apply(pure(x))(pure(f)) = pure(f(x))

  3. 交换律apply(pure(x))(f) = apply(f)(pure(f=>f(x))

  4. 结合律apply(apply(x)(f1))(f2) = apply(x)(apply(f1)(f2))

Monad

Monad 的定义为:

trait Monad[C[_]] extends Applicative[C]{
    def flatMap[P, Q](x:C[P])(f:P=>C[Q]):C[Q]
}

它在Applicative Functor的基础上增加了一个函数flatMap, 满足的限制为:

  1. 左一致性 flatMap(pure(x))(f) = f(x
  2. 右一致性flatMap(x)(pure)= x
  3. 结合性 flatMap(flatMap(x)(f))(g) = flatMap(x)(v=>flatMap(f(x))(g))

Functor, Applicative 和 Monad 的关系

*****
Written by Functor on 26 December 2016
Tags: [ scala  monad  functor  applicative  monoid  教程  函数式编程  ]