Monoid在Scala中的应用笔记

---

这个例子来源于scala圣经级教程《Functional Programming in Scala》，虽然原书的随书代码可以找到这些类的影子，但却没有关于如何使用这些类的示例代码，本人在阅读此书期间，除了跟着书中的代码敲了一遍之外，还写了一些测试代码进行验证，贴出来作为blog主要是为了方便自己，也为那些同样在阅读此书的人参考。注释不多，本人也不可能写太多，因为这本书不是简单的入门书，而是一本进阶，升华用的内涵书籍，三言两语也解释不清其中的很多细节，如果看不懂，但是又感兴趣的就去看原书吧……

---

package monoids

import parallelism.Nonblocking.Par.toParOps
import parallelism.Nonblocking._

import scala.language.{higherKinds, implicitConversions}

trait Monoid[A] {
  def op(a1: A, a2: A): A

  def zero: A
}

object Monoid {

  val stringMonoid = new Monoid[String] {
    def zero = ""

    def op(a1: String, a2: String) = a1 + a2
  }


  def listMonoid[A] = new Monoid[List[A]] {
    def op(a1: List[A], a2: List[A]) = a1 ++ a2

    val zero = Nil
  }

  val intAddition: Monoid[Int] = new Monoid[Int] {
    def zero: Int = 0

    def op(x: Int, y: Int): Int = x + y
  }

  val intMultiplication: Monoid[Int] = new Monoid[Int] {
    def op(x: Int, y: Int) = x * y

    val zero = 1
  }

  val booleanOr: Monoid[Boolean] = new Monoid[Boolean] {
    def op(x: Boolean, y: Boolean) = x || y

    val zero = false
  }

  val booleanAnd: Monoid[Boolean] = new Monoid[Boolean] {
    def op(x: Boolean, y: Boolean) = x && y

    val zero = true
  }

  // Notice that we have a choice in how we implement `op`.
  // We can compose the options in either order. Both of those implementations
  // satisfy the monoid laws, but they are not equivalent.
  // This is true in general--that is, every monoid has a _dual_ where the
  // `op` combines things in the opposite order. Monoids like `booleanOr` and
  // `intAddition` are equivalent to their duals because their `op` is commutative
  // as well as associative.
  def optionMonoid[A]: Monoid[Option[A]] = new Monoid[Option[A]] {
    def zero: Option[A] = None

    def op(a1: Option[A], a2: Option[A]): Option[A] = a1 orElse a2
  }

  // We can get the dual of any monoid just by flipping the `op`.
  def dual[A](m: Monoid[A]): Monoid[A] = new Monoid[A] {
    def zero: A = m.zero

    def op(x: A, y: A): A = m.op(y, x)
  }

  // Now we can have both monoids on hand
  def firstOptionMonoid[A]: Monoid[Option[A]] = optionMonoid[A]

  def lastOptionMonoid[A]: Monoid[Option[A]] = dual(firstOptionMonoid)


  // There is a choice of implementation here as well.
  // Do we implement it as `f compose g` or `f andThen g`? We have to pick one.
  def endoMonoid[A]: Monoid[A => A] = new Monoid[A => A] {
    def zero: A => A = (a: A) => a

    def op(f: A => A, g: A => A): A => A = f compose g
  }

  import testing._
  import testing.Prop._


  def monoidLaws[A](m: Monoid[A], gen: Gen[A]): Prop =
  // Associativity
    forAll(for {
      x <- gen
      y <- gen
      z <- gen
    } yield (x, y, z))(p =>
      m.op(p._1, m.op(p._2, p._3)) == m.op(m.op(p._1, p._2), p._3)) &&
      // Identity
      forAll(gen)((a: A) => m.op(a, m.zero) == a && m.op(m.zero, a) == a)


  def concatenate[A](as: List[A], m: Monoid[A]): A = as.foldLeft(m.zero)(m.op)

  // Notice that this function does not require the use of `map` at all.
  // All we need is `foldLeft`.
  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)))

  // The function type `(A, B) => B`, when curried, is `A => (B => B)`.
  // And of course, `B => B` is a monoid for any `B` (via function composition).
  def foldRight[A, B](as: List[A])(z: B)(f: (A, B) => B): B = foldMap(as, endoMonoid[B])(f.curried)(z)


  // Folding to the left is the same except we flip the arguments to
  // the function `f` to put the `B` on the correct side.
  // Then we have to also "flip" the monoid so that it operates from left to right.
  def foldLeft[A, B](as: List[A])(z: B)(f: (B, A) => B): B = foldMap(as, dual(endoMonoid[B]))(a => b => f(b, a))(z)


  def foldMapV[A, B](as: IndexedSeq[A], m: Monoid[B])(f: A => B): B =
    if (as.length == 0)
      m.zero
    else if (as.length == 1) f(as(0))
    else {
      val (l, r) = as.splitAt(as.length / 2)
      m.op(foldMapV(l, m)(f), foldMapV(r, m)(f))
    }

  // This implementation detects only ascending order,
  // but you can write a monoid that detects both ascending and descending
  // order if you like.
  def ordered(ints: IndexedSeq[Int]): Boolean = {
    // Our monoid tracks the minimum and maximum element seen so far
    // as well as whether the elements are so far ordered.
    val mon = new Monoid[Option[(Int, Int, Boolean)]] {
      def op(o1: Option[(Int, Int, Boolean)], o2: Option[(Int, Int, Boolean)]) =
        (o1, o2) match {
          // The ranges should not overlap if the sequence is ordered.
          case (Some((x1, y1, p)), Some((x2, y2, q))) =>
            Some((x1 min x2, y1 max y2, p && q && y1 <= x2))
          case (x, None) => x
          case (None, x) => x
        }

      val zero = None
    }
    // The empty sequence is ordered, and each element by itself is ordered.
    foldMapV(ints, mon)(i => Some((i, i, true))).map(_._3).getOrElse(true)
  }


  // This ability to 'lift' a monoid any monoid to operate within
  // some context (here `Par`) is something we'll discuss more in
  // chapters 11 & 12
  def par[A](m: Monoid[A]): Monoid[Par[A]] = new Monoid[Par[A]] {
    def zero = Par.unit(m.zero)

    def op(a: Par[A], b: Par[A]) = a.map2(b)(m.op)
  }

  // we perform the mapping and the reducing both in parallel
  def parFoldMap[A, B](v: IndexedSeq[A], m: Monoid[B])(f: A => B): Par[B] =
    Par.parMap(v)(f).flatMap { bs =>
      foldMapV(bs, par(m))(b => Par.lazyUnit(b))
    }


  def productMonoid[A, B](A: Monoid[A], B: Monoid[B]): Monoid[(A, B)] =
    new Monoid[(A, B)] {
      def op(x: (A, B), y: (A, B)) = (A.op(x._1, y._1), B.op(x._2, y._2))

      val zero = (A.zero, B.zero)
    }

  def functionMonoid[A, B](B: Monoid[B]): Monoid[A => B] =
    new Monoid[A => B] {
      def op(f: A => B, g: A => B) = a => B.op(f(a), g(a))

      val zero: A => B = a => B.zero
    }

  def mapMergeMonoid[K, V](V: Monoid[V]): Monoid[Map[K, V]] =
    new Monoid[Map[K, V]] {
      def zero = Map[K, V]()

      def op(a: Map[K, V], b: Map[K, V]) = (a.keySet ++ b.keySet).foldLeft(zero) { (acc, k) =>
        acc.updated(k, V.op(a.getOrElse(k, V.zero), b.getOrElse(k, V.zero)))
      }
    }


  def bag[A](as: IndexedSeq[A]): Map[A, Int] = foldMapV(as, mapMergeMonoid[A, Int](intAddition))((a: A) => Map(a -> 1))


  sealed trait WC

  case class Stub(chars: String) extends WC

  case class Part(lStub: String, words: Int, rStub: String) extends WC

  val wcMonoid: Monoid[WC] = new Monoid[WC] {
    val zero = Stub("")

    def op(a: WC, b: WC) = (a, b) match {
      case (Stub(c), Stub(d)) => Stub(c + d)
      case (Stub(c), Part(l, w, r)) => Part(c + l, w, r)
      case (Part(l, w, r), Stub(c)) => Part(l, w, r + c)
      case (Part(l1, w1, r1), Part(l2, w2, r2)) => Part(l1, w1 + (if ((r1 + l2).isEmpty) 0 else 1) + w2, r2)
    }
  }

  def count(s: String): Int = {
    // A single character's count. Whitespace does not count,
    // and non-whitespace starts a new Stub.
    def wc(c: Char): WC = if (c.isWhitespace)
      Part("", 0, "")
    else Stub(c.toString)


    // `unstub(s)` is 0 if `s` is empty, otherwise 1.
    def unstub(s: String) = s.length min 1


    foldMapV(s.toIndexedSeq, wcMonoid)(wc) match {
      case Stub(s) => unstub(s)
      case Part(l, w, r) => unstub(l) + w + unstub(r)
    }
  }

}


object MonoidTest {

  import testing._

  def main(args: Array[String]): Unit = {

    //验证Monoid.intAddition的正确性
    Prop.run(Monoid.monoidLaws(Monoid.intAddition, Gen.choose(Int.MinValue, Int.MaxValue)) tag " monoid laws error ")


    val stringLi = List("I ", "am ", "a ", "monster ")

    val stringLiRes = Monoid.concatenate(stringLi, Monoid.stringMonoid)
    println(stringLiRes)


    val intLi = List(1, 3, 5, 7, 9)
    val f = (a: Int) => a.toString + " "
    val intLiFoldMapRes = Monoid.foldMap(intLi, Monoid.stringMonoid)(f)
    println(intLiFoldMapRes)


    val intLi1 = List(1, 2, 3, 4, 5, 6, 7, 8, 9)
    val max = Monoid.foldLeft[Int, Int](intLi1)(0)((b, a) => if (b > a) b else a)
    println(max)


    println("ordered:  " + Monoid.ordered(intLi1.toIndexedSeq))


    println(Monoid.bag[Int](List(1, 2, 3).toIndexedSeq))


    println(Monoid.bag[Int](List(1, 1, 2).toIndexedSeq))

    println("word count: " + Monoid.count("one"))

    println("word count: " + Monoid.count("two words"))

  }

}

上述代码运行结果如下:

+ OK, passed 100 tests.
I am a monster 
1 3 5 7 9 
9
ordered:  true
Map(1 -> 1, 2 -> 1, 3 -> 1)
Map(1 -> 2, 2 -> 1)
word count: 1
word count: 2

---

[e-mail]  lhever

.---.                                                                         
|   |   .              __.....__   .----.     .----.   __.....__              
|   | .'|          .-''         '.  \    \   /    /.-''         '.            
|   |<  |         /     .-''"'-.  `. '   '. /'   //     .-''"'-.  `. .-,.--.  
|   | | |        /     /________\   \|    |'    //     /________\   \|  .-. | 
|   | | | .'''-. |                  ||    ||    ||                  || |  | | 
|   | | |/.'''. \\    .-------------''.   `'   .'\    .-------------'| |  | | 
|   | |  /    | | \    '-.____...---. \        /  \    '-.____...---.| |  '-  
|   | | |     | |  `.             .'   \      /    `.             .' | |      
'---' | |     | |    `''-...... -'      '----'       `''-...... -'   | |      
      | '.    | '.                                                   |_|      
      '---'   '---'