这是观看Cousera上的课程《Principles of Reactive Programming》中week1里的Monad一节所做的笔记。
What is a Monad?
What is a Monad?
A monad is a parametric type M[T] with two operations, flatMap and unit, that have to satisfy some laws.
这里是说Monad是一类特殊的类型，它有两个方法， flatMap和unit，这两个方法必须满足一些约束。嗯……并不是说任何有flatMap和unit方法的类都是Monad， Monad的这两个方法是有特定语义的，也正是这两个方法的语义使一个类型成为Monad.
用Scala来定义Monad如下：
trait M[T] {
def flatMap[U](f: T => M[U]): M[U]
}
def unit[T](x: T): M[T]
如果Monad被定义为一个trait，那么unit方法并不是这个trait的一部分，而是独立于Monad对象的。我觉得，可以理解为unit是一个生成Monad对象的方法，它和具体的对象没有关系。
Examples of Monads
- List is a monad with unit(x) = List(x)
- Set is a monad with unit(x) = Set(x)
- Option is a monad with unit(x) = Some(x)
- Generator is a monad with unix(x) = single(x) 注：Generator是Cousera的这门课程里的上一小节里讲到的一个类
flatMap is an operation on each of these types, whereas unit in Scala is different for each Monad.
实际上，List Set Option和Generator都可以看成集合，从这些集合的unit方法的定义可以看出，unit就是简单的对一个元素进行包装，使其成为一个类似于“单元素集合”的东西。
Monad and map
map can be defined for every monad as a combination of flatMap and unit:
m map f == m flatMap (x => unit(f(x)))
== m flatMap( f andThen unit)
实际上map的这种定义已经限制了flatMap和unit的语义。
m map f， 对于上边提到的Monad的语义都是把m中的每个元素通过f映射为另一个monad中的一个元素。因此，若想m map f == m flatMap( x => unit(f(x)))， unit和语义和flatMap的语义就得配合起来。也就是说，对于f(x),经过unit的处理，再经过flatMap的处理，还是f(x).
因此定义flatMap的重点在于如何把一组Monad组合成一个Monad。对于List，这个组合方法就是 ++， 对于Generator，就是
def flatMap[S](f: T => Generator[S]): Generator[S] = new Generator[S]{
def generate = f(self.generate).generate
}
即将每个元素运用f，生成一组Monad， 然后取这一组Monad中每个Monad的第一个元素组成一个Monad.
假如，我们定义一种Monad: 一串山楂。 0000
定义unit为：把一个山楂 0 拿一个竹签串起来，让它成为”一串山楂“。 0
定义g为把一个山楂变为一串山楂，具体怎么变由g的定义决定。 可见unit函数是g函数的一种。
定义flatMap(g)为把此山楂串的每个山楂应用g，得到很多串山楂，然后把这些山楂串 串成一整个山楂串。
定义函数f为把每个山楂包上糖。即从 0 变成 @
由以上定义可以推出：
m map f就是把m里的每个山楂都包上糖，再把这些山楂直接串起来，变成 @@@@
那么 x => unit(f(x))就是把一串山楂里的每一个0拿出来，先包上糖变成@，然后用一个竹签把这一个糖山楂串起来。 @
那么flatMap(x => unit(f(x)))就是就是把每个山楂应用 x => unit(f(x))，形成很多只有一个山楂的山楂串 @ @ @ @ ， 然后把它们串到一起，变成 @@@@ , 也就等于 m map f
在以上的定义下 m map f == m flatMap(x => unit(f(x)))
Monad Laws
To qualify a monad, a type has to satisfy three laws:
Associativity:
m flatMap f flatMap g == m flatMap( x => f(x) flatMap g)
Left unit
unit(x) flatMap f == f(x)
Right Unit
m flatMap unit == m
这个结合律理解起来有点困难，得先回忆一下flatMap的定义
def flatMap[U](f: T => M[U]): M[U]
这里重点留意下定义里跟数据类型有关的部分。
f: T => M[U] 因此，f是一种Monad的生成器。如果把f用于map，即 m map f， 结果的类型会是M[M[U]]，但是m flatMap f， 结果是M[U]。这就是flatMap神奇的地方，m flatMap f得到的值的类型跟m的类型是一样的(都是Monad)。比如，我们定义Int类型有个方法是^2，是求平方，那么就可以 3 ^2 ^2 ^2这样一直算下去，这样就可以很方便地利用递归。比如^6就可以在递归中用^2算出来。因此flatMap的这种对类型的保持，使得可以对Monad做无限的的flatMap，仍然得到Monad。也就是使得所有对Monad的操作都适用于m flatMap f。
也就是说我们可以m flatMap f flatMap g，也可以m flatMap f flatMap g flatMap k这样一直进行下去。
那么
Associativity:
m flatMap f flatMap g == m flatMap( x => f(x) flatMap g)
的意义何在？
Associativity says essentially that one can "inline" nested for expressions:
for(y <- for (x <-m; y <- f(x))yield y
z <- g(y)) yield z
== for{ x <- m
y <- f(x)
z <- g(y)
} yield z
来证明一下：
for( y <- for( x <- m; y <- f(x)) yield y
z <- g(y)) yield z
令 k = for(x <-m; y <- f(x)) yield y
原式变成for{y <- k
z <- g(y)} yield z
== k flatMap (y => for( z <- g(y) yield z)
== k flatMap ( y => (g(y) map ( z => z)))
== k flatMap ( y => g(y))
== k flatMap g
而 k = for{x <- m; y <- f(x)} yield y
= m flatMap ( x => (for( y <- f(x) yield y))
= m flatMap ( x => f(x))
= m flatMap f
所以
for( y <- for( x <- m; y <- f(x)) yield y
z <- g(y)) yield z
== m flatMap f flatMap g
而
for{ x <- m
y <- f(x)
z <- g(y)
} yield z
== m flatMap (x => (for (y <- f(x); z <- g(y)) yield z)
== m flatMap (x => f(x) flatMap( y => g(y))
== m flatMap (x => f(x) flatMap g)
所以，这两个for循环相等，要求 m flatMap f flatMap g == m flatMap(x => f(x) flatMap g), 也就是要求结合律成立。
从另一个角度看这回事，m flatMap f flatMap g就是连续做了两次flatMap。 而 f flatMap(x => f(x) flatMap g)，令k = (x => f(x) flatMap g)), 即m flatMap f flatMap g == f flatMap k， 即我们可以用 x => f(x) flatMap g 构造一个新的函数k，使得 m flatMap f flatMap g == f flatMap g。