Monoids, Functional Programming in Scala

Monoids.scala

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

val intAddition = new Monoid[Int] {
  def op(int1: Int, int2: Int) = int1 + int2
  def zero = 0
}

val intMultiplication = new Monoid[Int] {
  def op(int1: Int, int2: Int) = int1 * int2
  def zero = 1
}

val booleanOr = new Monoid[Boolean] {
  def op(b1: Boolean, b2: Boolean) = b1 || b2
  def zero = false
}

val booleanAnd = new Monoid[Boolean] {
  def op(b1: Boolean, b2: Boolean) = b1 && b2
  def zero = true
}


def endoMonoid[A]: Monoid[A => A] =
  new Monoid[A => A] {
    def op(x: A => A, y: A => A) = x andThen y
    val zero: A => A = identity
  }
  
def dual[A](m: Monoid[A]) = new Monoid[A] {
  def op(a1: A, a2: A) = m.op(a2, a1)
  def zero = m.zero
}

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)))
  
def foldLeft[A, B](as: List[A])(z: B)(f: (B, A) => B): B = {
  val mb = new Monoid[B] {
    def op(b1: B, b2: B): B = b1 b2
    val zero: B = z
  }
  foldMap(as, mb)(f)
}


def foldMapV[A, B](v: Seq[A], m: Monoid[B])(f: A => B): B = {
  def loop(u: Seq[A]): B =
    if (u.isEmpty)
      m.zero
    else if (u.size == 1)
      f(u(0))
    else {
      val (l, r) = u.splitAt(u.size / 2)
      m.op(loop(l), loop(r))
    }
  loop(v)
}

def ordered(v: Seq[Int]): Boolean =
  foldMapV(v, new Monoid[(Int, Boolean)] {
    def op(ib0: (Int, Boolean), ib1: (Int, Boolean)) = {
      val (i0, b0) = ib0
      val (i1, b1) = ib1
      println(s"$b0 && $i0 <= $i1, $b1")
      (i1, b1 && i0 <= i1)
    }
    val zero = (Int.MinValue, true)
  })((_, true))._2


sealed trait WC
case class Stub(chars: String) extends WC
case class Part(lStub: String, nWords: Int, rStub: String) extends WC
  
val wcMonoid = new Monoid[WC] {
  def op(a: WC, b: WC) =
    (a, b) match {
      case (Stub(a0), Stub(b0)) => Stub(a0 + b0)
      case (Stub(a0), Part(l, wc, r)) => Part(a0 + l, wc, r)
      case (Part(l, wc, r), Stub(b0)) => Part(l, wc, r + b0)
      case (Part(la, wca, ra), Part(lb, wcb, rb)) => Part(la, wca + (if ((ra + lb).isEmpty) 0 else 1) + wcb, rb)
    }
  val zero = Stub("")
}

def count(s: String): Int =  
  foldMapV(s.toIndexedSeq, wcMonoid) { c: Char =>
    if (c.isWhitespace) Part("", 0, "")
    else Stub(c.toString)
  } match {
    case Stub(a) => stubVal(a)
    case Part(a, wc, b) => stubVal(a) + wc + stubVal(b)
  }

def stubVal(s: String) = s.size min 1

trait Foldable[F[_]] {
  def foldRight[A, B](as: F[A])(z: B)(f: (A, B) => B): B = foldMap(as)(f.curried)(endoMonoid[B])(z)
  def foldLeft[A, B](as: F[A])(z: B)(f: (B, A) => B): B = foldMap(as)(a => (b: B) => f(b, a)))(dual(endoMonoid[B]))(z)
  def foldMap[A, B](as: F[A])(f: A => B)(mb: Monoid[B]): B
  def concatenate[A](as: F[A])(ma: Monoid[A]): A = foldLeft(as)(ma.zero)(ma.op)
}

val foldableList = new Foldable[List] {
  def foldRight[A, B](as: F[A])(z: B)(f: (A, B) => B): B = 
  def foldLeft[A, B](as: F[A])(z: B)(f: (B, A) => B): B
  def foldMap[A, B](as: F[A])(f: A => B)(mb: Monoid[B]): B
}

def functionMonoid[A, B](bMonoid: Monoid[B]): Monoid[A => B] =
  new Monoid[A => B] {
    def op(f: A => B, g: A => B): A => B = a => bMonoid.op(f(a), g(a))
    def zero: A => B = _ => bMonoid.zero
  }
  
def bag[A](as: IndexedSeq[A]): Map[A, Int] = foldMapV(as, mapMergeMonoid(intAddition))(Map(_ -> 1))