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==s、s+"" == 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）封闭性（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)的定义是：

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

包含单位元或幺元的半群，为幺半群(monoid)：

trait Monoid[T] {
  // 二元操作
  def op(a1: T, a2: T): T
  // 单位元
  def zero: T
}

或

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

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

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

或

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

或

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带来两个重要法则：

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)
}

例子：

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, B 和 C 组成，有三个单位态射 id_A, id_B 和 id_C ，还有另外两个态射 f : C => B 和 g : A => B

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

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 => B 有 id_B o g = g = g o id_A。
（3）态射在组合操作下是闭合的。所以如果存在态射f: A => B 和g: B => C，那么范畴中必定存在态射 h: A => C 使得 h = g o f。

f 和 g 都是态射，所以我们一定能够对它们进行组合并得到范畴中的另一个态射。那么哪一个是态射 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 变成了相同的态射。对象之间的转换是用浅黄色的虚线箭头表示，态射之间的转换是用蓝紫色的箭头表示。

¶单位函子

每一个范畴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)**上。

// Int => String
def foo(i:Int): String = i.toString

// List[Int] => List[String]
def bar(l:List[Int]): List[String] = l.map(_.toString)

2. 函子表达的映射关系，则体现在**高阶函数(high-order function)**上(确切来说是范畴)。

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

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] 
}

把这项定义再简化

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]。

范畴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] 的结果是 Int，F[Int => String] 的结果仍是 Int => String

¶Monad

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

首先，自函子是长这样的：

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

幺半群是长这样的：

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

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

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

好像还漏点什么？幺元(单位元)！补全之后，

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：

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

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

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

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

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，实现：

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

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

一点改进：尾递归实现：

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有几个常见的推导：

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)))
}

---

1. 《Advanced Scala with Cats》, underscore. ↩
2. Scala和范畴论, http://www.jianshu.com/p/31377066bf97 ↩
3. http://stackoverflow.com/questions/3870088/a-monad-is-just-a-monoid-in-the-category-of-endofunctors-whats-the-problem ↩