什么是monoid
一个monoid有如下构成
1、一个类型A
2、一个可结合的二元操作op，它接收两个参数然后返回相同类型的值，对于任何x: A，y: A，z: A来说，这两个操作是等价的：op(op(x, y), z) == op(x, op(y, z))
3、一个值，zero: A，它是一个单位元，对于任何x: A来说，zero和它的操作都等于x本身：op(x, zero) == x 或 op(zero, x) == x
可以使用trait表达：
trait Monoid[A] {
def op(a1: A, a2: A): A
def zero: A
}
练习 10.1
给出moniod实例，用来处理整数相加、相乘和布尔操作。
object Monoid {
val intAddition: Monoid[Int] = new Monoid[Int] {
override def op(a1: Int, a2: Int): Int = a1 + a2
override def zero: Int = 0
}
val intMultiplication: Monoid[Int] = new Monoid[Int] {
override def op(a1: Int, a2: Int): Int = a1 * a2
override def zero: Int = 1
}
val booleanOr: Monoid[Boolean] = new Monoid[Boolean] {
override def op(a1: Boolean, a2: Boolean): Boolean = a1 || a2
override def zero: Boolean = false
}
val booleanAnd: Monoid[Boolean] = new Monoid[Boolean] {
override def op(a1: Boolean, a2: Boolean): Boolean = a1 && a2
override def zero: Boolean = true
}
}
练习 10.2
给出能够组合Option值的实例。
def optionMonoid[A]: Monoid[Option[A]] = new Monoid[Option[A]] {
override def op(a1: Option[A], a2: Option[A]): Option[A] = a1.orElse(a2)
override def zero: Option[A] = None
}
练习 10.3
我们吧参数和返回值是相同类型的函数称为自函数（endofunction）。为endofunction编写一个monoid。
def endoMonoid[A]: Monoid[A => A] = new Monoid[(A) => A] {
override def op(a1: (A) => A, a2: (A) => A): (A) => A = a1.andThen(a2)
override def zero: (A) => A = a => a
}
使用monoid折叠列表
monoid和列表的折叠有着紧密联系，观察List的foldLeft和foldRight的函数签名：
def foldLeft[B](z: B)(f: (B, A) => B): B
def foldRight[B](z: B)(f: (A, B) => B): B
当A和B类型是一样的时：
def foldLeft[A](z: A)(f: (A, A) => A): A
def foldRight[A](z: A)(f: (A, A) => A): A
monoid的各个部分符合这些参数，Monoid[A]的zero可以作为参数z；Monoid[A]的op可以作为参数f。所以折叠一个List[String]和List[Int]可以表示为：
val stringMonoid: Monoid[String] = new Monoid[String] {
override def op(a1: String, a2: String): String = a1 + a2
override def zero: String = ""
}
val words = List("He", "ll", "o")
val s = words.foldLeft(stringMonoid.zero)(stringMonoid.op)
val nums = List(2, 0, 1, 8)
val n = nums.foldLeft(intAddition.zero)(intAddition.op)
我们可以编写一个函数concatenate，使用monoid折叠列表
def concatenate[A](li: List[A], m: Monoid[A]): A =
li.foldLeft(m.zero)(m.op)
但是假如列表中的元素类型不是monoid的实例，该怎么办？总是可以将类型为A的列表map成类型为B的列表。
def foldMap[A, B](as: List[A], m: Monoid[B])(f: A => B): B
练习 10.5
实现foldMap
def foldMap[A, B](as: List[A], m: Monoid[B])(f: A => B): B =
as.map(f).foldLeft(m.zero)(m.op)
练习 10.6
foldMap可以通过foldLeft和foldRight来实现，foldMap也可以实现foldLeft和foldRight，试一下。
def foldMap1[A, B](as: List[A], m: Monoid[B])(f: A => B): B =
as.foldRight(m.zero){(a, b) => m.op(f(a), b)}
def foldMap2[A, B](as: List[A], m: Monoid[B])(f: A => B): B =
as.foldLeft(m.zero){(b, a) => m.op(b, f(a))}
结合律和并行化
monoid操作的结合律意味着可以自由的选择如何进行数据结构的折叠操作，就像列表操作那样。假如有个monoid，甚至可以使用平衡折叠法对列表进行折叠，这样对于某些操作可能更有效率，更易于并行化。
练习 10.7
为indexedSeq实现foldMap，使用的策略是将顺序集拆分成两部分，递归的处理每一部分，然后使用monoid将结果加起来。
def foldMapV[A, B](v: IndexedSeq[A], m: Monoid[B])(f: A => B): B =
if (v.length <= 1)
v.headOption.map(f).getOrElse(m.zero)
else {
val (l, r) = v.splitAt(v.length)
m.op(foldMapV(l, m)(f), foldMapV(r, m)(f))
}
可折叠的数据结构
在第3章节中实现了List和Tree的数据结构，两者都是可以折叠的。在第5章节实现了Stream，也是一个可以折叠的数据结构。在编写代码去处理这类数据结构的时候，通常不会在意具体数据结构是什么（List或Tree），例如：
ints.foldLeft(0)(_ + _)
我们并不关心ints是什么类型，它可以是List[Int]也可以是Stream[Int]，还可以是含有foldLeft方法的其它类型。可以这种通用性表示成下面的trait:
练习 10.12
trait Foldable[F[_]] {
def foldLeft[A, B](as: F[A], b: B)(f: (B, A) => B): B
def foldRight[A, B](as: F[A], b: B)(f: (A, B) => B): B
def foldMap[A, B](as: F[A], m: Monoid[B])(f: A => B): B
def concatenate[A](as: F[A], m: Monoid[A]): A =
foldLeft(as, m.zero)(m.op)
}
object Foldable {
val foldableList: Foldable[List] = new Foldable[List] {
override def foldRight[A, B](as: List[A], b: B)(f: (A, B) => B): B =
as.foldRight(b)(f)
override def foldMap[A, B](as: List[A], m: Monoid[B])(f: (A) => B): B =
as.foldLeft(m.zero){(b, a) => m.op(b, f(a))}
override def foldLeft[A, B](as: List[A], b: B)(f: (B, A) => B): B =
as.foldLeft(b)(f)
}
val foldableIndexSeq: Foldable[IndexedSeq] = new Foldable[IndexedSeq] {
override def foldRight[A, B](as: IndexedSeq[A], b: B)(f: (A, B) => B): B =
as.foldRight(b)(f)
override def foldMap[A, B](as: IndexedSeq[A], m: Monoid[B])(f: (A) => B): B =
as.foldLeft(m.zero){(b, a) => m.op(b, f(a))}
override def foldLeft[A, B](as: IndexedSeq[A], b: B)(f: (B, A) => B): B =
as.foldLeft(b)(f)
}
val foldableStream: Foldable[Stream] = new Foldable[Stream] {
override def foldRight[A, B](as: Stream[A], b: B)(f: (A, B) => B): B =
as.foldRight(b)(f)
override def foldMap[A, B](as: Stream[A], m: Monoid[B])(f: (A) => B): B =
as.foldLeft(m.zero){(b, a) => m.op(b, f(a))}
override def foldLeft[A, B](as: Stream[A], b: B)(f: (B, A) => B): B =
as.foldLeft(b)(f)
}
}
练习 10.13
在第3章实现了二叉树，为它实现Foldable实例。
sealed trait Tree[+A]
case class Leaf[A](value: A) extends Tree[A]
case class Branch[A](left: Tree[A], right: Tree[A]) extends Tree[A]
val foldableTree: Foldable[Tree] = new Foldable[Tree] {
override def foldRight[A, B](as: Tree[A], b: B)(f: (A, B) => B): B = as match {
case Leaf(a) => f(a, b)
case Branch(l, r) => foldRight(l, foldRight(r, b)(f))(f)
}
override def foldMap[A, B](as: Tree[A], m: Monoid[B])(f: (A) => B): B =
foldLeft(as, m.zero){(b, a) => m.op(b, f(a))}
override def foldLeft[A, B](as: Tree[A], b: B)(f: (B, A) => B): B = as match {
case Leaf(a) => f(b, a)
case Branch(l, r) => foldLeft(r, foldLeft(l, b)(f))(f)
}
}
练习 10.14
编写Foldable[Option]的实例
val foldOption: Foldable[Option] = new Foldable[Option] {
override def foldRight[A, B](as: Option[A], b: B)(f: (A, B) => B): B =
as.foldRight(b)(f)
override def foldMap[A, B](as: Option[A], m: Monoid[B])(f: (A) => B): B =
as.foldLeft(m.zero){(b, a) => m.op(b, f(a))}
override def foldLeft[A, B](as: Option[A], b: B)(f: (B, A) => B): B =
as.foldLeft(b)(f)
}
练习 10.15
编写通用的转化方法，将Foldable结构转化成List
def toList[A](fa: F[A]): List[A] =
foldRight(fa, List.empty[A]){(a, b) => a :: b}
组合monoid
monoid本身的抽象还不是那么引人入胜，在泛化foldMap的帮助下它也只是变得有趣了些。它真正强大之处来自于它的组合。
这意味着，假如A和B是monoid，那么tuple类型(A, B)同样也是monoid（称为product）。
练习 10.16
证明：当且仅当A.op和B.op的实现是可结合，那么如下的op实现也是可结合的。
def productMonoid[A, B](ma: Monoid[A], mb: Monoid[B]): Monoid[(A, B)] =
new Monoid[(A, B)] {
override def op(a1: (A, B), a2: (A, B)): (A, B) = {
val (aa1, bb1) = a1
val (aa2, bb2) = a2
(ma.op(aa1, aa2), mb.op(bb1, bb2))
}
override def zero: (A, B) = (ma.zero, mb.zero)
}
练习 10.17
def functionMonoid[A, B](b: Monoid[B]): Monoid[A => B] = new Monoid[(A) => B] {
override def zero: (A) => B = a => b.zero
override def op(a1: (A) => B, a2: (A) => B): (A) => B =
a => b.op(a1(a), a2(a))
}
使用组合的monoid融合多个遍历
多个monoid可以组合成一个，意味着折叠数据结构时可以同时执行多个计算。比如可以同时获取List的长度和总和用于计算平均值：
val m = productMonoid(intAddition, intAddition)
val p = foldMap(List(1, 2, 3, 4), m)(a => (a, 1))
val mean = p._1 / p._2
