Add WriterT monad transformer

[sungiant]

I find the WriterT monad transformer to be really useful for logging. When moving a project of mine from scalaz over to cats I found that WriterT didn't exist, so had to implement a minimal version of it myself. I imagine that I'm not the first person to run into this problem, so how about we add WriterT to cats?

Here's my current, minimal implementation:

final case class WriterT[T[_], L, V] (run: T[(L, V)]) {
  def written (implicit functorT: Functor[T]): T[L] = functorT.map (run)(_._1)
  def value (implicit functorT: Functor[T]): T[V] = functorT.map (run)(_._2)
  def map[Z](fn: V => Z)(implicit f: Functor[T]): WriterT[T, L, Z] = WriterT {
    f.map (run) { z =>
      (z._1, fn (z._2))
    }
  }
  def flatMap[U](f: V => WriterT[T, L, U])(implicit monadT: Monad[T], semigroupL: Semigroup[L]): WriterT[T, L, U] = WriterT {
    monadT.flatMap (run) { lv =>
      monadT.map (f (lv._2).run) { lv2 =>
        (semigroupL.combine (lv._1, lv2._1), lv2._2)
      }
    }
  }
}
object WriterT {
  def putT[T[_], L, V] (vt: T[V])(l: L)(implicit functorT: Functor[T]): WriterT[T, L, V] = WriterT (functorT.map (vt)(v => (l, v)))
  def put[T[_], L, V] (v: V)(l: L)(implicit functorT: Functor[T], applicativeT: Applicative[T]): WriterT[T, L, V] = WriterT.putT[T, L, V](applicativeT.pure (v))(l)
  def tell[T[_], L] (l: L)(implicit functorT: Functor[T], applicativeT: Applicative[T]): WriterT[T, L, Unit] = WriterT.put[T, L, Unit](())(l)
  def value[T[_], L, V] (v: V)(implicit functorT: Functor[T], applicativeT: Applicative[T], monoidL: Monoid[L]): WriterT[T, L, V] = WriterT.put[T, L, V](v)(monoidL.empty)
  def valueT[T[_], L, V] (vt: T[V])(implicit functorT: Functor[T], monoidL: Monoid[L]): WriterT[T, L, V] = WriterT.putT[T, L, V](vt)(monoidL.empty)

  implicit def writerTMonad[T[_], L] (implicit monadT: Monad[T], monoidL: Monoid[L]) = new Monad[({type WT[α] = WriterT[T, L, α]})#WT] {
    override def pure[A] (a: A): ({type WT[α] = WriterT[T, L, α]})#WT[A] = WriterT.value[T, L, A](a)
    override def flatMap[A, B] (fa: ({type WT[α] = WriterT[T, L, α]})#WT[A])(f: A => ({type WT[α] = WriterT[T, L, α]})#WT[B]): WriterT[T, L, B] = fa.flatMap (a => f (a))
    override def ap[A, B] (fa: ({type WT[α] = WriterT[T, L, α]})#WT[A])(ff: ({type WT[α] = WriterT[T, L, α]})#WT[A => B]): ({type WT[α] = WriterT[T, L, α]})#WT[B] = fa.flatMap (a => ff.map (f => f (a)))
  }
}

I'm not up to speed with all of the discussions around the structuring and best practices used in cats, so I didn't want to simply submit a pull request, however, I'd be happy to do so if someone informed me as to where in the project WriterT should live...

[non]

👍 I think it makes sense to add this to core (probably cats.data.WriterT). What do you all think?

[adelbertc]

cats.data.WriterT sounds good. May also be nice to have a Writer, either as it's own data type or via a type alias (with convenience methods).

[ceedubs]

Added in #542