boring writer monad example for @johnynek

Writer.scala

package sandbox

trait Monoid[A] {
  def empty: A
  def append(lhs: A, rhs: A): A
}

case class Writer[W, A](a: A, w: W) {
  def map[B](f: A => B): Writer[W, B] = Writer(f(a), w)
  def flatMap[B](f: A => Writer[W, B])(implicit W: Monoid[W]) = {
    val Writer(b, ww) = f(a)
    Writer(b, W.append(w, ww))
  }
}

object Writer {
  implicit def seqMonoid[A]: Monoid[Seq[A]] = new Monoid[Seq[A]] {
    def empty: Seq[A] = Seq.empty
    def append(lhs: Seq[A], rhs: Seq[A]): Seq[A] = lhs ++ rhs
  }

  type Logger[W, A] = Writer[Seq[W], A]

  def tell[W](w: W): Writer[W, Unit] = Writer((), w)
  def log[W](w: W): Logger[W, Unit] = tell(Seq(w))

  def fib(n: Int): Logger[String, BigInt] = n match {
    case 0 | 1 => for {
      _ <- log("fib(%d) === 1".format(n))
    } yield 1
    case _     => for {
      _ <- log("computing fib(%d)...".format(n))
      a <- fib(n - 1)
      b <- fib(n - 2)
      sum = a + b
      _ <- log("fib(%d) === %d".format(n, sum))
    } yield sum
  }

  def main(args: Array[String]): Unit =
    fib(5).w foreach println
}

/* output:

  computing fib(5)...
  computing fib(4)...
  computing fib(3)...
  computing fib(2)...
  fib(1) === 1
  fib(0) === 1
  fib(2) === 2
  fib(1) === 1
  fib(3) === 3
  computing fib(2)...
  fib(1) === 1
  fib(0) === 1
  fib(2) === 2
  fib(4) === 5
  computing fib(3)...
  computing fib(2)...
  fib(1) === 1
  fib(0) === 1
  fib(2) === 2
  fib(1) === 1
  fib(3) === 3
  fib(5) === 8

*/