Monoid

什么是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