Introduction to Category Theory in Scala

If you are a former Java developer and have become a Scala fanboy like me, you will probably sooner or later encounter terms like monad, functor or other mysteries from the realm of category theory which make you feel like a little dummkopf (screamingly funny for a German like me, according to www.dict.cc this seems to be a proper English verb). If you already feel comfortable with these, don’t waste your time and move along. But if not, I would like to invite you to a little sightseeing trip that reflects my efforts to get to know this secret realm somewhere in between abstract mathematics and computer science.

This blog post is meant to be an introduction. Depending on the effect on my health (while writing I’m often afraid that my head might explode), my future spare time (understanding comes very slowly, if at all) and your feedback, I am going to write a follow-up. But for now let’s get started.

What’s a category?

Obviously this should be the first question when talking about category theory, although in my opinion the concept of a category is not too useful for programming. Here comes a comprehensive answer:

A category is made up from objects and maps (aka morphisms or arrows) between these objects. Maps can be composed in an associative fashion and for each object there is an identity map which is neutral with regard to composition.

Objects can be anything, but let’s look at a simple case: The category of finite sets. The diagram below depicts two such finite sets as well as a map from the one called source (aka domain) to the other called target (aka codomain).

A little more formally, we can call the domain A and the codomain B and write the map like this:

f: A → B

Now what’s composition? Let’s look at the next diagram, where I added another finite set and another map. Please don’t worry that in this strange world eating habits are different from what you might know 😉

Let’s call the new set C and the new map g: B → C. Obviously we can get from A to C by first following f and then g. Therefore we get a new map from composing f and g:

g ο f: A → C

Now that we know composition, we have to talk about associativity and identity. Let’s add another map h: C → D. Then the associativity law requires the following to hold true:

(h ο g) ο f = h ο (g ο f)

Associativity should become clear pretty fast from thinking of addition or multiplication of numbers. Therefore let’s move along towards the identity laws. These require that for each object X of the category there is an identity map 1_X: X → X which satisfies the following rules:

• f ο 1_A = f
• 1_B ο f = f

The following diagram depicts an identity map in our example category of finite sets. Obviously for identity maps the domain and codomain are the same object.

OK, that’s it. That’s categories. Objects, maps, composition, associativity and identity. If you would like to dive a little deeper into the theory, I recommend Wikipedia or “Conceptual Mathematics” by Lawvere and Schanuel. I will move along and look at categories from a Scala point of view.

Categories in Scala

Note: In the following I will borrow a lot of ideas and even some (slightly modified) code from the scalaz project. This Scala library, together with the Apocalisp blog, provides an incredibly valuable source of information and inspiration about advanced functional programming in Scala.

Now that we have investigated the category of finite sets, let’s implement another one in Scala. Therefore we consider the category made up from Scala types as objects and Scala functions as maps. We still have to prove that this is a category, but first let’s code it up:

object Category {
  def id[A]: A => A = a => a
  def compose[A, B, C](g: B => C, f: A => B): A => C =
    g compose f // This is Function.compose, not a recursive call!
}

OK, it looks like we have all the ingredients we need: Types are objects, functions with one argument (trait Function) are maps, id returns the identity function for each A and compose composes two functions.

It looks obvious, that the associativity and identity laws are satisfied, but better let’s check using a simple unit test written using the awesome specs and ScalaCheck frameworks:

class CategorySpec extends Specification with ScalaCheck {
  import Category._

  "A Category" should {

    val f = (i: Int) => i.toString
    val g = (s: String) => s.length
    val h = (i: Int) => i * i

    "satisfy associativity" in {
      Prop forAll { (i: Int) =>
        compose(h, compose(g, f))(i) == compose(compose(h, g), f)(i)
      } must pass
    }

    "satisfy identity" in {
      Prop forAll { (i: Int) =>
        compose(f, id[Int])(i) mustEqual compose(id[String], f)(i)
      } must pass
    }
  }
}

OK, so now we know that Category indeed adheres to the category laws. But that’s not the end of our story! Let’s move along to a more general category in Scala: While sticking to the Scala types as objects we will use the type constructor ->> for the maps.

trait GenericCategory[->>[_, _]] {
  def id[A]: A ->> A
  def compose[A, B, C](g: B ->> C, f: A ->> B): A ->> C
}

Please note, that A ->> B is just another way to write ->>[A, B], which nicely reflects the fact that we are talking about maps here.

Of course our Category is an implementation of this GenericCategory:

object Category extends GenericCategory[Function] {
  def id[A]: A => A = a => a
  def compose[A, B, C](g: B => C, f: A => B): A => C =
    g compose f // This is Function.compose, not a recursive call!
}

If you are interested in further types of categories, don’t hesitate to take a look at scalaz: You can find numerous categories there, e.g. a category of partial functions or a monoid category. I will keep it that way and move along to another important concept in category theory.

Functors

Now that we know categories and how to represent certain ones in Scala, let’s look at another important concept of category theory, which is also very important for functional programming. Consider two categories C1 and C2; then a functor F is a structure-preserving mapping between these categories.

OK, but what does that mean? A mapping between categories simply means that

• every object A ∈ C1 is mapped to to an object F(A) ∈ C2 and
• every map A → B between two objects A, B ∈ C1 is mapped to a map F(A) → F(B) between two objects F(A), F(B) ∈ C2.

In order to preserve the category structure this mapping must preserve the identity maps and the compositions. More formally:

• F(1_A) = 1_F(A) ∀ A ∈ C1
• F(g ο f) = F(g) ο F(f) ∀ f: A → B, g: B → C where A, B, C ∈ C1

Before thinking about the “meaning” of a functor, let’s code it up in Scala using our GenericCategory (of Scala types and arbitrary maps between these) as foundation:

trait GenericFunctor[->>[_, _], ->>>[_, _], F[_]] {
  def fmap[A, B](f: A ->> B): F[A] ->>> F[B]
}

Again, ->> and ->>> as well as F are type constructors. Looking at the ingredients, we find all that we need: Types A and B are mapped to types F[A] and F[B] and maps A ->> B are mapped to maps F[A] ->>> F[B].

Now let’s move along from arbitrary maps to Scala functions, i.e. choose our Category as source and target of the functor. This results in a so called endofunctor (same source and target) and looks like the following:

trait Functor[F[_]] extends GenericFunctor[Function, Function, F] {
  final def fmap[A, B](as: F[A])(f: A => B): F[B] =
    fmap(f)(as)
}

Please note, that the new fmap method is just for convenience and delegates to the inherited one. Using the higher kinded type for the first parameter list makes it possible to infer the type of A for the function in the second parameter list.

In order to code up some examples, we have to specify the type constructor F. Let’s start with good old List:

object ListFunctor extends Functor[List] {
  def fmap[A, B](f: A => B): List[A] => List[B] = as => as map f
}

This one let’s us map a function over a List, which means that this functor looks like a container that allows us to apply a function to all of its elements. This is a very intuitive way to think about functors. And it makes clear, that functors are a very important concept for functional programming, because if you look at the collections of the Scala library, you will see, that all of them provide this “mapping a function over the elements”.

OK, let’s see how we can use that. Therefore we add a Functor object, move our ListFunctor into that and make it implicit and add a generic fmap method:

object Functor {

  def fmap[A, B, F[_]](as: F[A])(f: A => B)(implicit functor: Functor[F]): F[B] =
    functor.fmap(as)(f)

  implicit object ListFunctor extends Functor[List] {
    def fmap[A, B](f: A => B): List[A] => List[B] =
      as => as map f
  }
}

Welcome type classes! The new generic fmap method takes an additional and implicit parameter of type Functor parameterized with a higher kinded type. When we call this method with an instance of this higher kinded type and a function but no functor, the compiler will look for a matching implicit value. Let’s see it in action:

scala> import com.weiglewilczek.cats.Functor._
import com.weiglewilczek.cats.Functor._

scala> fmap(List(1, 2, 3))(x => x + 1)        
res0: List[Int] = List(2, 3, 4)

While we could have reached the same result by simply calling map on the List instance, we now have something more general: A fmap method that works for any type for which we provide a functor.

We still have to verify that our ListFunctionFunctor satisfies the functor laws. Hence we write another unit test:

class ListFunctorTest extends Specification with ScalaCheck {
  import Functor.ListFunctor._

  "A ListFunctor" should {

    "preserve identity" in {
      val stringID = (s: String) => s
      val stringListID = (ss: List[String]) => ss
      Prop forAll { (ss: List[String]) =>
        fmap(stringID)(ss) == stringListID(ss)
      } must pass
    }

    "preserve composition" in {
      val f = (i: Int) => i.toString
      val g = (s: String) => s.length
      Prop forAll { (is: List[Int]) =>
        fmap(g compose f)(is) == (fmap(g) compose fmap(f))(is)
      } must pass
    }
  }
}

Fine! Now let’s look at another example. Why not use Option as type constructor for the Functor trait?

implicit object OptionFunctor extends Functor[Option] {
  def fmap[A, B](f: A => B): Option[A] => Option[B] =
    o => o map f
}

This one let’s us map a function over an Option, which can be thought of as applying the function in the context of the Option. If it is None, the function won’t be applied, if it is Some, it will be applied. This “computational context” is another way of looking at functors which sometimes is called “lifting” of functions: The function is lifted from its normal context to the functor’s context.

Let’s code up another example that makes this interpretation even more obvious. Now we use Function0 as type constructor for the Functor trait:

implicit object Function0Functor extends Functor[Function0] {
  def fmap[A, B](f: A => B): Function0[A] => Function0[B] =
    a => () => f(a())
}

Let’s see this one in action:

scala> val f = (s: String) => s.length
f: (String) => Int = <function1>

scala> val lifted = fmap(() => "abc")(f)
lifted: () => Int = <function0>

scala> lifted()
res1: Int = 3

As you can see, the function f is lifted into the context of the given Function0, i.e. it works on the output of that.

Conclusion

In this blog post we looked at two basic objects from category theory: Categories and functors. Of course there are others, some of them heavily used (e.g. monads), but I will keep it like that for now. Hopefully I could show you that category theory offers some interesting and valuable concepts that can be applied to and expressed in Scala. As I consider myself still a rookie in category theory, I’d be happy to get your feedback.

If you are interested in the code examples shown above, you can find these here: https://github.com/weiglewilczek/fun