Blogger - Scalaz Motivation - 16

object ScalazMotivation extends App {
  def p(a: Any) { println("###> " + a) }

  trait Monoid[A] {
    def mzero: A
    def mappend(a1: A, a2: A): A
  }

  object Monoid {
    implicit object IntMonoid extends Monoid[Int] {
      def mzero = 0
      def mappend(a: Int, b: Int) = a + b
    }

    implicit object StringMonoid extends Monoid[String] {
      def mzero = ""
      def mappend(a1: String, a2: String) = a1 + a2
    }
  }

  trait FoldLeft[M[_]] {
    def foldLeft[A, B](ma: M[A], b: B, op: (B, A) => B): B
  }

  object FoldLeft {
    implicit object ListFoldLeft extends FoldLeft[List] {
      def foldLeft[A, B](ma: List[A], b: B, op: (B, A) => B) = ma.foldLeft(b)(op)
    }

    implicit object TreeFoldLeft extends FoldLeft[Tree] {
      def foldLeft[A, B](ma: Tree[A], b: B, op: (B, A) => B) = {
        def toList(ma: Tree[A]): List[A] = ma match {
          case Node(el, left, right) => toList(left) ::: (el :: toList(right))
          case Empty() => Nil
        }
        toList(ma).foldLeft(b)(op)
      }
    }
  }

  sealed trait Tree[E]
  case class Empty[E]() extends Tree[E]
  case class Node[E](el: E, left: Tree[E], right: Tree[E]) extends Tree[E]

  def sum[M[_], T](xs: M[T])(implicit m: Monoid[T], fl: FoldLeft[M]): T =
    fl.foldLeft(xs, m.mzero, m.mappend)

  val tree: Tree[String] =
    Node("c",
      Node("b",
        Node("a", Empty(), Empty()),
        Node("a",
          Node("r", Empty(), Empty()),
          Empty()
        )
      ),
      Node("d",
        Node("a", Empty(), Empty()),
        Node("b",
          Node("a", Empty(), Empty()),
          Node("r",
            Empty(),
            Node("a", Empty(), Empty())
          )
        )
      )
    )

  p(sum(List(1, 2, 3))) // prints ###> 6
  p(sum(List("lamb", "da"))) // prints ###> lambda
  p(sum(tree)) // prints ###> abracadabra
}