Type Class 101: Category and Monads

I found a post by Qiaochu Yuan that has the following definiton: A comathematician is a device for turning cotheorems into ffee.

Apparently this is a very funny joke. Could someone explain it to me and tell me where I could learn about the subject in question? Thank you very much in advance.

+1 for “Apparently this is a very funny joke”. math.stackexchange.com

Category and Monads

By the way, the above joke has nothing to do with todays topic, I just found it funny.

I had a little bit of a writers block since the last episode in the series about ApplicativeBuilder, since I was not sure how to approach the coming topics. Hence we take a little bit of time to disgress. Semigroups, Monoids, Functors and Applicatives are all concepts found in category theory. Category theory is a very general mathematical theory, but it deals with something which is at the core of functional programming, and hence makes it so attractive for programmers. It is dealing with:

  • Abstraction
  • Composition

And composition is something which we want to exploit, and there stems our interest in category theory.

What is a category?

In Scala terms the definition of a category is simple:

trait Category[=>:[_,_]] {
  def id[A] : A =>: A // identity arrow
  def compose[A,B,C](g: B =>: C, f: A =>: B) : A =>: C // composition arrow
}

We have some objects of any type, and we can connect these objects using arrows. So if we have an arrow from f: A -> B and an arrow from g: B -> C, category theory implies that we also have h: A -> C (dashed arrow).

We also need an id - Arrow: an arrow pointing back to the identical object.

A category for Scala Types and functions

So - what if we create a category for our Scala types as objects and functions as arrows:

val simpleCategory : Category[Function1] = new Category[Function1] {
  def id[A] : A => A = {a => a} // identity function
  def compose(g: B => C, f: A => B) : A => C = g.compose(f) // function composition
}

This was as simple as useless, because we already have composition for functions in Scala. Do we really?

One step beyond

Let’s see what happens if we try to compose some fancy functions, like f: A => Option[B] and g: B => Option[C]. Well, they don’t compose:

scala> val f : Int => Option[String] = a => Some(a.toString)
f: Int => Option[String] = <function1>

scala> val g: String => Option[String] = a => Some(a + " " + a)
g: String => Option[String] = <function1>

scala> g.compose(f)
<console>:10: error: type mismatch;
 found   : Int => Option[String]
 required: ? => String
              g.compose(f)

Let’s create a small helper class called Fancy, which wraps our fancy methods (this is just a workaround to get a safe way to talk about our fancy functions):

case class Fancy[A,B](run : A => Option[B])

Can we create a Category for Fancy?

val fancyCategory: Category[Fancy] = new Category[Fancy] {
  def id[A] : Fancy[A,A] = Fancy {a => Some(a)}
  def compose[A,B,C](g: Fancy[B,C], f: Fancy[A,B]) : Fancy[A,C] =  Fancy[A,C]{ a =>
    f.run(a) match {
      case Some(b) => g.run(b)
      case None => None
    }
  }
}

Hell yeah, we can!

val f : Int => Option[Int] = a => if (a > 0) Some(a) else None

val g: Int => Option[String] = a => Some(a.toString)

val h = fancyCategory.compose(Fancy(g),Fancy(f))
h: Fancy[Int,String] = Fancy(<function1>)

scala> h.run(3)
res0: Option[String] = Some(3)

scala> h.run(-1)
res1: Option[String] = None

This was nice. Let’s do it again. This time for List:

case class Fancy2[A,B](run: A => List[B])

val fancy2Category : Category[Fancy2] = new Category[Fancy2] {
  def id[A] = Fancy2 { a => List(a)}
  def compose[A,B,C](g: Fancy2[B,C], f: Fancy2[A,B]) : Fancy2[A,C] = Fancy2[A,C] { a => f.run(a) flatMap g.run }
}

Well, I cheated a bit by using flatMap in this implementation. But we could have used flatMap in Fancy for our Option as well. Let’s write the two implementation under each other:

// function from a simple type to a fancy type
case class Fancy [A,B](run : A => Option[B])
case class Fancy2[A,B](run: A => List[B])
// put something into a fancy
def id[A] = Fancy  { a => Some(a)}
def id[A] = Fancy2 { a => List(a)}
// compose the fancies
def compose[A,B,C](g: Fancy[B,C], f: Fancy[A,B]) : Fancy[A,C] =  Fancy[A,C]{ a => f.run(a) flatMap g.run }
def compose[A,B,C](g: Fancy2[B,C], f: Fancy2[A,B]) : Fancy2[A,C] = Fancy2[A,C] { a => f.run(a) flatMap g.run }

Hmm, almost the same, let’s abstract over that:

trait Monad[F[_]] { // F = Fancy type, like Option or List
  def pure[A](a: A) : F[A] // put something into a fancy
  def flatMap[A,B](fa: F[A])(f: A => F[B]) : F[B] // compose
}

implicit val optionMonad : Monad[Option] = new Monad[Option] {
  def pure[A](a: A) = Some(a)
  def flatMap[A,B](fa: Option[A])(f: A => Option[B]) : Option[B] = fa.flatMap(f)
}

implicit val listMonad : Monad[List] = new Monad[List] {
  def pure[A](a: A) = List(a)
  def flatMap[A,B](fa: List[A])(f: A => List[B]) : List[B] = fa.flatMap(f)
}

case class Fancy3[M[_], A, B](run : A => M[B])

implicit def monadCategory[M[_]](implicit M : Monad[M]) : Category[({type l[A,B] = Fancy3[M,A,B]})#l] =
new Category[({type l[A,B] = Fancy3[M,A,B]})#l] {
  def id[A] = Fancy3[M,A,A] { a => M.pure(a)}
  def compose[A,B,C](g: Fancy3[M,B,C], f: Fancy3[M,A,B]) : Fancy3[M,A,C] = Fancy3 { a => M.flatMap(f.run(a))(g.run)}
}

We haz Monads!

Some explaining is probably in order:

  • the Monad trait is just another typeclass
  • the funny construct ({type l[A,B] = Fancy3[M,A,B]})#l creates a type alias, as if we said type FancyOpt[A,B]=Fancy3[Option, A, B] only, that we need to it dynamically, because only at the time we want to construct the category M is known.
  • Our Fancy3 helper class is the Kleisli class in scalaz. It is just a wrapper with lots of helper functions for functions of the type A => M[B]

But the important thing is, we just constructed a Monad. And if you tried to come to terms yet, what a Monad exactly is: it enables you to compose fancy functions (with some constraints/laws).

Outro

I am neither a mathematician nor particularly good at Category Theory, for more details read the very good blog posts byBartosz Milewski. He helped me get various pieces together, especially seeing many of the constructs in category theory as means to compose things of a special structure.

For further articles in this series: TypeClass101

typeclass101 scalaz scala

Kommentare