daniberg.com

posts github chip8 rtc guitar

Writer Monad

According to the wiki entry All About Monads the writer monad is useful for 'Logging, or other computations that produce output "on the side"'.

In this post we implement the writer monad from scratch in scala. The source code can be found here: Writer Monad.

Let's start by defining the writer class.

case class Writer[A, W](v: A, w: W)

The writer class has two values: A and W. We'll use A to represent regular values and W as our logs or the "output on the side".

Let's first introduce the monad trait.

trait Monad[F[_]] {

  def unit[A](a: A): F[A]

  def flatMap[A, B](fa: F[A])(f: A => F[B]): F[B]

  def map[A, B](fa: F[A])(f: A => B): F[B] = {
    flatMap(fa)(a => unit(f(a)))
  }
}

Our monad trait has the primitives unit and flatMap. We also implement map to support for-comprehensions later in our examples.

Given the monad trait we can implement a writer monad instance.

object Writer {

  implicit def monad[W : Monoid]: Monad[({ type l[x] = Writer[x, W] })#l] =
    new Monad[({ type l[x] = Writer[x, W]} )#l]
    {
      override def unit[A](a: A): Writer[A, W] =
	    Writer(a, implicitly[Monoid[W]].zero)

      override def flatMap[A, B](fa: Writer[A, W])(f: A => Writer[B, W]): Writer[B, W] = {
        val fa2 = f(fa.v)
        Writer(fa2.v, implicitly[Monoid[W]].append(fa.w, fa2.w))
      }
  }

}

Since the writer class expects two types (A, and W) we pin the type W to create a monad instance for our writer class.

Notice that we also require that a monoid instance of W exists when building a monad of type writer. The monoid instance is used in unit to supply the zero value of W and in flatMap to concatenate two W values.

We define the monoid trait below while also including a String instance of the trait that we'll use in our examples later on.

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

object Monoid {
  implicit val monoidString: Monoid[String] = new Monoid[String] {
    override def zero: String = ""
    override def append(a1: String, a2: String): String = a1 ++ a2
  }
}

One more piece of machinery we'll introduce is an implicit conversion from monads to a class that implements map and flatMap so we can leverage for-comprehensions.

object MonadOps {

  // for comprehensions for (*, *) -> *
  implicit class MonadOps2[A, W, F[_, _]](fa: F[A, W])(implicit M: Monad[({ type l[x] = F[x, W] })#l]) {
    def map[B](f: A => B): F[B, W] = M.map(fa)(f)
    def flatMap[B](f: A => F[B, W]): F[B, W] = M.flatMap(fa)(f)
  }

}

The implicit resolution can transform a writer instance into a monad instance, and which in turn, can be transformed into a MonadOps2 instance.

Let's run a few examples.

All examples assume we have the import

// Monad -> MonadOps
import MonadOps._

First, let's check that we can `map` over a writer instance.

val w1: Writer[Int, String] = Writer(10, "I will start with 10. ")
  .map { i => i * 2}

println(w1) // Writer(20,I will start with 10. )

What about flatmap?

val w2 = Writer("Hello", "HelloOnce")
  .flatMap { s => Writer(s * 2, "HelloTwice")}

println(w2) // Writer(HelloHello,HelloOnceHelloTwice)

That means we can write a for-comprehension expression.

val w3: Writer[Int, String] = for {
  x      <- Writer(20, "I start with 20. ")
  isEven <- Writer(x % 2 == 0, "Is it even? ")
} yield if (isEven) x + 1 else x

println(w3) // Writer(21,I start with 20. Is it even? )

Notice that map doesn't give us a chance to add to our log.

We introduce the method `tell` to take care of that.

object Writer {
  def tell[W](w: W): Writer[Unit, W] = Writer((), w)
}

We can now add logs into our program.

val w4: Writer[Int, String] = for {
    x      <- Writer(20, "I start with 20. ")
    isEven <- Writer(x % 2 == 0, "Is it even? ")
    msg = if (isEven) s"Let's make $x odd. " else s"$x is already odd. "
    _      <- Writer.tell(msg)
  } yield if (isEven) x + 1 else x

println(w4) // Writer(21,I start with 20. Is it even? Let's make 20 odd. )

Similarly, we introduce the method `writer` to lift values into a writer instance with an empty log.

object Writer {
  def write[A, W : Monoid](a: A): Writer[A, W] = monad[W].unit(a)
}

Regular values can now be lifted into a Writer.

val w5: Writer[Int, String] = for {
  x      <- write(20)
  isEven <- write(x % 2 == 0)
  odd    <- write(if (isEven) x + 1 else x)
  _      <- tell(s"We had $x, it was${if (isEven) "" else " not"} even, so we have $odd")
} yield odd

println(w5) // Writer(21,We had 20, it was even, so we have 21)