Monoids and Monads

Haskell由于使用了Monad这种较费解的概念来控制副作用而遭到了一些批评意见。Wadler试图平息这些质疑,他解释说:“一个单子(Monad)说白了不过就是自函子范畴上的一个幺半群而已,这有什么难以理解的?”
A monad is just a monoid in the category of endofunctors, what’s the problem?

这一句话包含了好几个概念:单子(monad),自函子(Endo-Functor),幺半群(Monoid),范畴(category)。

Monoid

函数式编程的Monoid形式定义为:

  • 给定的类型 T
  • 一个二元操作,Op: (T,T) => T 使得任意的 x, y, z ∈ T,满足 op(op(x,y), z) == op(x, op(y,z))
  • 元单位 Zero: T 使得任意的 x ∈ T,满足 op(x, zero) == x and op(zero, x) == x

满足以上关系的代数数据结构,存在一种普遍存在形式:

  1. 若T为整数,则有 (a+b)+c == a+(b+c)0+n == n+0 == n; (a*b)*c == a*(b*c)1*n == n*1 == n
  2. 若T为字符串,则有 a+(b+c)==(a+b)+c; ""+s==ss+"" == s
  3. 若T为数组,则有 List(1,2)+List(3,4) == List(1,2,3,4)
  4. 若T为集合,则有 Set(1,2,3)+Set(2,4) == Set(1,2,3,4)

可以看出,整数时明显满足了 “加法交换律和乘法分配律,包含一个单位元e”,它实际上是一个线性空间。尽管其它数据类型没有特别明显,我们要构造相应的定义关系,在其映射关系上构造一个幺半群(Monoid)。

一个群的定义为:

1
2
3
4
(1)封闭性(Closure):对于任意a,b∈G,有a*b∈G
(2)结合律(Associativity):对于任意a,b,c∈G,有(a*b)*c=a*(b*c)
(3)幺元 (Identity):存在幺元e,使得对于任意a∈G,e*a=a*e=a
(4)逆元:对于任意a∈G,存在逆元a^-1,使得a^-1*a=a*a^-1=e

则称 (G, *) 是群,简称G是群。

如果仅满足封闭性和结合律,则称G是一个半群(Semigroup);如果仅满足封闭性、结合律并且有幺元,则称G是一个含幺半群(Monoid)。

所以一个半群(semigroup)的定义是:

1
2
3
trait SemiGroup[T] {
def op(a1: T, a2: T): T
}

包含单位元或幺元的半群,为幺半群(monoid):

1
2
3
4
5
6
trait Monoid[T] {
// 二元操作
def op(a1: T, a2: T): T
// 单位元
def zero: T
}

1
2
3
trait Monoid[T] extends SemiGroup[T] {
def zero: T
}

按照语义,属于群的任意集合要满足定义关系,所以任意集合的形式为:

1
2
3
4
object IntMonoid extends Monoid[Int] {
def op(a1: Int, a2: Int) = a1 + a2
def zero = 0
}

1
2
3
4
val stringMonoid = new Monoid[String] {
override def op(a1: String, a2: String) = a1 + a2
override def zero = ""
}

1
2
3
4
def listMonoid[A] = new Monoid[List[A]] {
override def op(a1: List[A], a2: List[A]) = a1 ++ a2
override def zero = Nil
}

那么这种定义在函数式编程中有什么作用?函数的抽象性在于,我们可以抽象一种类型,实现高阶函数。幺半群(Monoid)的抽象实际是一个域(Domain),对应Scala的类型系统(type class)。我们用一个例子来说明Monoid这种类型类带来的函数式编程魅力。

Monoid带来两个重要法则:

1
2
3
4
5
6
def associativeLaw[A](x: A, y: A, z: A)(implicit m: Monoid[A]): Boolean = m.op(x, m.op(y, z)) == m.op(m.op(x, y), z)

def identityLaw[A](x: A)(implicit m: Monoid[A]): Boolean = {
(m.op(x, m.zero) == x) &&
(m.op(m.zero, x) == x)
}

例子:

1
2
3
4
5
6
7
8
9
10
11
trait Monoid[A] {
def f(a1: A, a2: A): A
def zero: A
}

implicit val intMonoid = new Monoid[Int] {
def f(a: Int, b: Int):Int = a + b
def zero = 0
}

def sum[A](ts: List[A])(implicit m: Monoid[A]): A = ts.foldLeft(m.zero)(m.f)

范畴

范畴由三部分组成:

(1)一组对象
(2)一组态射(morphisms)。每个态射会绑定两个对象,假如f是从源对象A到目标对象B的态射,记作:f:A -> B
(3)态射组合。假如h是态射f和g的组合,记作:h = g o f

下图展示了一个简单的范畴,该范畴由对象 A, BC 组成,有三个单位态射 id_A, id_Bid_C ,还有另外两个态射 f : C => Bg : A => B

Simple-cat

态射我们可以简单的理解为函数,假如在某范畴中存在一个态射,它可以把范畴中一个Int对象转化为String对象。在Scala中我们可以这样定义这个态射:f : Int => String = ...。所以态射的组合也就是函数的组合,见代码:

1
2
3
4
5
6
7
8
scala> val f1: Int => Int = i => i + 1
f1: Int => Int = <function1>

scala> val f2: Int => Int = i => i + 2
f2: Int => Int = <function1>

scala> val f3 = f1 compose f2
f3: Int => Int = <function1>

范畴公理

范畴需要满足以下三个公理。

(1)态射的组合操作要满足结合律。记作:f o (g o h) = (f o g) o h
(2)对任何一个范畴 C,其中任何一个对象A一定存在一个单位态射,id_A: A => A。并且对于态射g:A => Bid_B o g = g = g o id_A
(3)态射在组合操作下是闭合的。所以如果存在态射f: A => Bg: B => C,那么范畴中必定存在态射 h: A => C 使得 h = g o f

Composition-ex

fg 都是态射,所以我们一定能够对它们进行组合并得到范畴中的另一个态射。那么哪一个是态射 f o g 呢?唯一的选择就是 id_A 了。类似地,g o f=id_B

函子(Functor)

函子定义

函子有一种能力,把两个范畴关联在一起。函子本质上是范畴之间的转换。比如对于范畴 C 和 D ,函子F : C => D 能够:将 C 中任意对象a 转换为 D 中的 F(A); 将 C 中的态射f : A => B 转换为 D 中的 F(f) : F(A) => F(B)

下图表示从范畴C到范畴D的函子。图中的文字描述了对象 A 和 B 被转换到了范畴 D 中同一个对象,因此,态射 g 就被转换成了一个源对象和目标对象相同的态射(不一定是单位态射),而且 id_A 和 id_B 变成了相同的态射。对象之间的转换是用浅黄色的虚线箭头表示,态射之间的转换是用蓝紫色的箭头表示。

Functor

单位函子

每一个范畴C都可以定义一个单位函子:Id: C => C。它将对象和态射直接转换成它们自己:Id[A] = A; f: A => B, Id[f] = f

函子公理

(1)给定一个对象 A 上的单位态射Id_A , F(Id_A) 必须也是 F(A) 上的单位态射,也就是说:F(Id_A) = Id_(F(A))
(2)函子在态射组合上必须满足分配律,也就是说:F(f o g) = F(f) o F(g)

一个函子Functor表示范畴A到范畴B之间的映射。函子和函数都表示一种映射关系,但是针对的类型不同。

  1. 函数表达的映射关系在类型上体现在**特定类型(proper type)**上。
1
2
3
4
5
// Int => String
def foo(i:Int): String = i.toString

// List[Int] => List[String]
def bar(l:List[Int]): List[String] = l.map(_.toString)
  1. 函子表达的映射关系,则体现在**高阶函数(high-order function)**上(确切来说是范畴)。

怎么用代码来描述函子?根据定义,它包含两个层面的映射关系:

  1. 将C1中的类型 T 映射为 C2 中的 List[T] : T => List[T]
  2. 将C1中的函数 f 映射为 C2 中的 函数fm : (A => B) => (List[A] => List[B])

我们定义一个类型构造器

1
2
3
4
trait Functor[F[_]] {
def typeMap[A]: F[A]
def funcMap[A,B](f: A=>B): F[A]=>F[B]
}

把这项定义再简化

1
2
3
4
5
6
7
8
trait Functor[F[_]] {
def map[A, B](a: F[A])(f: A => B): F[B]
}

//list Functor的实现
def listFunctor = new Functor[List] {
def map[A, B](a: List[A])(f: (A) => B) = a.map(f)
}

我们用归纳证明的方法来阐述Functor[F[_]]是否满足定义关系。f: A => B 是一个态射,它构成了A=>B => F[A] => F[B] 的一个映射关系。map[Int, Int](List(1, 2, 3))(_ + 1),对于map 它的入参是List(1,2,3),执行过程中被映射该函数 _: Int + 1,得到结果 List(2,3,4)。对于List范畴来说,这个过程就是:List[Int] => List[Int]。它就是Int 到 List 范畴的函子,即 Int => Int => List[Int] => List[Int]

1
2
3
4
5
6
7
8
范畴Int				范畴List[_]
+------------+ +----------------+
| | | |
| Int | map | List[Int] |
| ↓ | =====> | ↓ |
| Int | f:A=>B | List[Int] |
| | | |
+------------+ +----------------+

在haskell里把这两个行为叫做提升(lift),相当于把类型和函数放到容器里。

自函子(Endofunctor)

自函子是一类比较特殊的函子,它是一种将范畴映射到自身的函子 (A functor that maps a category to itself)。例如Int => Int, String => String等。

自函子的映射结果是自身,因此,对于自函子F,F[Int] 的结果是 IntF[Int => String] 的结果仍是 Int => String

Monad

那么回过头来看看定义,“一个单子(Monad)说白了不过就是自函子范畴上的一个幺半群而已,有什么难以理解的。”

首先,自函子是长这样的:

1
2
3
trait Functor[F[_]] {
def map[A, B](a: F[A])(f: A => B): F[B]
}

幺半群是长这样的:

1
2
3
4
trait Monoid[A] {
def f(a1: A, a2: A): A
def zero: A
}

自函子上的幺半群是啥?首先它是一个自函子,所以它应该包含类型[M[_]],自函子满足 A => B → M[A] => M[B] 的关系,所以它包含有:

1
2
3
4
trait Monad[F[_]] {
def flatMap[A, B](value: F[A])(func: A => F[B]): F[B]
...
}

好像还漏点什么?幺元(单位元)!补全之后,

1
2
3
4
trait Monad[F[_]] {
def flatMap[A, B](value: F[A])(func: A => F[B]): F[B]
def unit[A](a: A): F[A]
}

Monad的确切定义为:

Monad是一个函子:M: C -> C,并且对C中的每一个对象x以下两个态射:

  1. unit: x -> M[x]
  2. join/bind: M[M[x]] -> M[x]

第一个态射比较容易理解,它就是子函数的幺元;第二个就是我们描述的自函子!按照定义实现的Monad:

1
2
3
4
trait Monad[M[_]] {
def unit[A](a: A): M[A] //identity
def join[A](mma: M[M[A]]): M[A]
}

它实际上和第一种Monad定义是等价的!!不过它还有更多的推导形式…

1
def join[A](mma: M[M[A]]): M[A] = flatMap(mma)(ma => ma)

例子:我们实现下图的一个装箱操作:

Monad

1
2
3
4
trait Monad[F[_]] {
def flatMap[A, B](value: F[A])(func: A => F[B]): F[B]
def unit[A](a: A): F[A]
}

Monad在类库中总是和implicity一起使用,我们不做这么复杂,假设自函子范畴是List,实现:

1
2
3
4
5
6
7
8
9
10
11
val ListMonad = new Monad[List] {
override def flatMap[A, B](value: List[A])(func: A => List[B]): List[B] = {
def fun: (List[A]) => List[B] = {
case Nil => Nil
case x :: xs => func(x) ::: fun(xs)
}

fun(value)
}
override def unit[A](a: A) = List(a)
}

对该幺半群做自函子的映射,即每个元素加3

1
logger info s"${ListMonad.flatMap(List(1, 2, 3))(x => x + 3 :: Nil) }"

一点改进:尾递归实现:

1
2
3
4
5
6
7
8
9
10
11
12
val listMonad = new Monad[List] {
override def flatMap[A, B](value: List[A])(func: A => List[B]): List[B] = {
@tailrec
def fun(a: List[A], b: List[B]): List[B] = a match {
case Nil => b
case x :: xs => fun(xs, b ::: func(x))
}

fun(value, Nil)
}
override def unit[A](a: A) = List(a)
}

得益于范畴论的推理总是辣么的多,Monad有几个常见的推导:

1
2
3
4
5
6
7
8
trait Monad[F[_]] {
def flatMap[A, B](v: F[A])(f: A => F[B]): F[B]
def unit[A](a: A): F[A]

def compose[A, B, C](f: A => F[B], g: B => F[C]): A => F[C] = a => flatMap(f(a))(g)
def join[A, B](mma: F[F[A]]): F[A] = flatMap(mma)(ma => ma)
def map[A,B](ma: F[A])(f: A => B): F[B] = flatMap(ma)(a => unit(f(a)))
}