函子：對map函數(shù)的泛化
在第一部分和第二部分實現(xiàn)了一些不同組合子庫。這些組合子的相似性是值得注意的憎夷，比如為每個數(shù)據(jù)類型都實現(xiàn)了map函數(shù)，用于提升某個數(shù)據(jù)類型到上下文中的數(shù)據(jù)類型。例如下面的函數(shù)簽名：
def map[A, B](oa: Option[A])(f: A => B): Option[B] = ???
def map[A, B](op: Parser[A])(f: A => B): Parser[B] = ???
def map[A, B](og: Gen[A])(f: A => B): Gen[B] = ???
這些函數(shù)簽名只是數(shù)據(jù)類型不同。這里將它定義為Scala trait并實現(xiàn)map：
trait Functor[F[_]] {
def map[A, B](a: F[A])(f: A => B): F[B]
}
函子法則
無論何時創(chuàng)建一個類似Functor的抽象拱层，都不需要考慮實現(xiàn)哪些抽象方法弥臼，而是考慮遵循哪些法則宴咧。遵循什么樣的法則完全由你決定，Scala不會強加任何這樣的法則径缅。對于Functor掺栅，將引入的法則是：
map(x)(a => a) == x
Monad：對flatMap和unit函數(shù)的泛化
Functor只是眾多抽象中的一個。Functor的作用不是那么顯著纳猪，是因為僅僅使用一個map定義不出太多可用的操作氧卧。接下來我們介紹一個有趣的接口，monad氏堤。使用monad可以實現(xiàn)很多可用的操作沙绝，并且一勞永逸的對重復(fù)的代碼進(jìn)行重構(gòu)嘱腥。同時相關(guān)的法則可以推導(dǎo)庫按照預(yù)期運行÷羊龋現(xiàn)在我們?yōu)镸onad定義一個Scala trait：
trait Monad[F[_]] extends Functor[F] {
def unit[A](a: => A): F[A]
def flatMap[A, B](a: F[A])(f: A => F[B]): F[B]
override def map[A, B](a: F[A])(f: (A) => B): F[B] =
flatMap(a)(a => unit(f(a)))
def map2[A, B, C](fa: F[A], fb: F[B])(f: (A, B) => C): F[C] =
flatMap(fa){a =>
map(fb){b =>
f(a, b)
}
}
}
練習(xí) 11.1
val monadOption: Monad[Option] = new Monad[Option] {
override def flatMap[A, B](a: Option[A])(f: (A) => Option[B]): Option[B] = a match {
case None => None
case Some(a) => f(a)
}
override def unit[A](a: => A): Option[A] = Some(a)
}
val monadStream: Monad[Stream] = new Monad[Stream] {
override def flatMap[A, B](a: Stream[A])(f: (A) => Stream[B]): Stream[B] = a match {
case Empty => Empty
case head #:: tail => f(head) ++ flatMap(tail)(f)
}
override def unit[A](a: => A): Stream[A] = Stream(a)
}
val monadList: Monad[List] = new Monad[List] {
override def flatMap[A, B](a: List[A])(f: (A) => List[B]): List[B] = a match {
case Nil => Nil
case head :: tail => f(head) ++ flatMap(tail)(f)
}
override def unit[A](a: => A): List[A] = List(a)
}
val monadPar: Monad[Par] = new Monad[Par] {
override def flatMap[A, B](a: Par[A])(f: (A) => Par[B]): Par[B] =
es => {
val aa = a(es)
f(aa.get())(es)
}
override def unit[A](a: => A): Par[A] = Par.unit(a)
}
Monadic組合子
現(xiàn)在已經(jīng)有Monad的原始語義了，回看之前的章節(jié)是否有其它為Monadic數(shù)據(jù)類型實現(xiàn)的函數(shù)可以統(tǒng)一被實現(xiàn)氛悬。
練習(xí) 11.3
大家已經(jīng)很熟悉sequence和traverse的組合了购笆，之前的章節(jié)很多地方都實現(xiàn)了它粗悯，現(xiàn)在使用Monad[F]來實現(xiàn)它們：
def sequence[A](li: List[F[A]]): F[List[A]] = {
def loop(n: Int, res: F[List[A]]): F[List[A]] = n match {
case m if m < 0 => res
case _ =>
val temp = flatMap(res){la =>
map(li(n)){a =>
a :: la
}
}
loop(n - 1, temp)
}
loop(li.length - 1, unit(Nil))
}
def traverse[A, B](la: List[A])(f: A => F[B]): F[List[B]] =
sequence(la.map(f))
練習(xí) 11.4
實現(xiàn)replicateM。
def replicateM[A](n: Int, ma: F[A]): F[List[A]] = {
val la = List.fill(n)(ma)
sequence(la)
}
練習(xí) 11.6
實現(xiàn)函數(shù)filterM同欠，它看起來和filter類似样傍，它接受的不是函數(shù)A=>Bollean，而是A=>F[Boolean]
def filterM[A](la: List[A])(f: A => F[Boolean]): F[List[A]] = {
def loop(n: Int, res: F[List[A]]): F[List[A]] = n match {
case m if m < 0 => res
case _ =>
val temp = flatMap(res){li =>
map(f(la(n))){b =>
if(b) la(n) :: li
else li
}
}
loop(n - 1, temp)
}
loop(la.length - 1, unit(Nil))
}
單子定律
毫無疑問functor法則對Monad是成立的铺遂，因為Monad[F]是一個Functor[F]衫哥，但是除此之外呢？什么樣的法則可以約束flatMap和unit襟锐？
結(jié)合法則
x.flatMap(f).flatMap(g) == x.flatMap(a => f(a).flatMap(g))
KLEISLI組合：結(jié)合律更清晰的視圖
Monad的結(jié)合法則看起來不是很清晰撤逢，幸運的是有種方法可以讓它更清晰。不考慮F[A]類型monadic值，而是考慮A => F[B]的monadic函數(shù)笛质。這樣的函數(shù)稱為Kleisli箭頭泉沾。它們是可以相互組合的。
練習(xí) 11.7
實現(xiàn)Kleisli composition函數(shù)compose妇押。
def compose[A, B, C](f: A => F[B], g: B => F[C]): A => F[C] =
a => flatMap(f(a))(g)
現(xiàn)在可以使用一個更加對稱的方式為Monad聲明結(jié)合法則了：
compose(compose(f, g), h) == compose(f, compose(g, h))
單位元法則
compose(f, unit) == f
compose(unit, f) == f
練習(xí) 11.12
第三種monadic組合的最小集合map跷究、unit和join。使用flatMap實現(xiàn)join敲霍。
def join[A](mma: F[F[A]]): F[A] =
flatMap(mma){ma => ma}
練習(xí) 11.14
使用join和map實現(xiàn)flatMap或compose俊马。
def flatMap[A, B](a: F[A])(f: A => F[B]): F[B] =
join(map(a)(f))
def compose[A, B, C](f: A => F[B], g: B => F[C]): A => F[C] =
a => join(map(f(a))(g))
什么是monadic
Monad和Monoid一樣是一個更加抽象、純代數(shù)的接口肩杈。Monad組合通常是一個Monad數(shù)據(jù)類型所有API中的一小部分柴我，Monad不是對一個類型的泛化，而是大量不同的數(shù)據(jù)類型滿足Monad接口和法則的抽象扩然。兩個Monad法則需要被滿足結(jié)合法則（associativity）和單位元法則（identity）艘儒，它們可以以不同的方式公式化。因此我們可以簡單的描述Monad：
monad是一個滿足associativity和identity法則的monadic組合的最小集的實現(xiàn)
identity monad
為了提煉monad的本質(zhì)夫偶，先看一個有趣的例子界睁，identity monad。
case class Id[A](value: A)
練習(xí) 11.17
為這個類型實現(xiàn)map和flatMap方法兵拢，并實現(xiàn)Monod[Id]翻斟。
case class Id[A](value: A) {
def map[B](f: A => B): Id[B] = this match {
case Id(a) => Id(f(a))
}
def flatMap[B](f: A => Id[B]) = this match {
case Id(a) => f(a)
}
}
val monadId: Monad[Id] = new Monad[Id] {
override def unit[A](a: => A): Id[A] = Id(a)
override def flatMap[A, B](a: Id[A])(f: (A) => Id[B]): Id[B] =
a.flatMap(f)
}
從上面的中可以看出，monad提供了一個引入和綁定變量的上下文说铃，同時執(zhí)行了變量替換访惜。
狀態(tài)monad和partial type application
def stateMonad[S] = new Monad[({type f[X] = State[S, X]}) # f] {
override def unit[A](a: => A): State[S, A] = State(s => (a, s))
override def flatMap[A, B](a: State[S, A])(f: (A) => State[S, B]): State[S, B] =
a.flatMap(f)
}
