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 1X: X → X which satisfies the following rules:

  • f ο 1A = f
  • 1B ο 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(1A) = 1F(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

About these ads

About Heiko Seeberger

Scala enthusiast. Free climber and half marathon runner. Director of Education for Typesafe.
This entry was posted in Category Theory, Functional Programming, Scala. Bookmark the permalink.

33 Responses to Introduction to Category Theory in Scala

  1. Hey Heiko,

    Thanks a lot for writing this article! I’ve been meaning to get into Category Theory for some time now but I found it hard to figure out where to start and how it relates to Scala – You’ve solved that problem with this article, so thank you and keep them coming :)

    Mads

  2. Daniel Ribeiro says:

    Nice description. However, it is important to note that functors, in general, are not computable. This is because the set of all computable functions may be infinite, but not only is it a set, it is also enumerable (as Turin Machines are enumerable). However the class (as in defined in category theory, and not as in OO) of functors is a proper class and not a set, therefore it is “bigger” than the enumerable set of computable functions.

    Also, I’d like to add a very good introductory paper on the subject (written by a Google researcher): Physics, Topology, Logic and Computation: A Rosetta Stone

  3. nuttycom says:

    Awesome introduction to the notion of a category, Heiko! Thanks so much for putting this up – it clarifies things tremendously for me. The notion of a category-theoretic arrow as a generalization of a function had never really sunk in before reading this post, but now that I can see it simply as a type constructor of two arguments for which identity and composition can be defined, many more things make sense!

  4. Channing Walton says:

    Thanks for writing this, I’ve been studying this stuff lately and this will help.

    However, I got stuck with ->>. What is that? What does it mean?

    Channing

  5. Channing Walton says:

    Aha, dont’ worry, I just got it :)

  6. Very nice blog,

    i’ve seen your excellent intro to Scala in Java-magazine, and I am looking forward to more of your blogs. There is, by the way, a wonderful book on category theory in ML by D.Rydeheard and Ron Burstall : Computational category theory (Prentice Hall, 1988, and now free on the net) that would be wonderful to see in Scala.

    H.Peter Gumm

  7. Adelar da Silva Queiróz says:

    Thanks. Very good article.

  8. @ Channing Walton : maybe you could explain it to me? ;)
    I understand that ->>[A, B] means “it takes a type A and returns a type B”. I just don’t know where this lives in “real world programming” (not that Functors aren’t a part of real world programming . . . but . . . errrr . . . you get the idea)

    Anyway: great post Heiko! Makes me want to go and reexplore all those concepts I got in touch with, while doing a little Haskell . . .

    • to make my question a little bit more clear:

      it’s the distinction between A -> B and A ->> B that puzzles me a bit. It’s my understanding that the first one says “takes a parameter of type A and returns something with type B” while the second one says “takes a type A and returns a type B”.
      Is that correct?

      • A ->> B is the same as ->>[A, B].
        ->>[_, _] ist just an arbitrary type constructor; I could also have written F[_, _], but I like the correspondence to maps / morphisms.

  9. Pingback: Functional Code in the News « Statically Typed

  10. Dan says:

    Heiko,

    I think that the confusion that aglWritesThings encountered is the same as my initial confusion. When I first saw ->> I thought it referred to the name of a trait, not a type parameter. It might make it easier to read your article if you made that a little more clear when you first introduce ->> and ->>>. Otherwise I loved your article, it has made category theory a little bit more comprehensible to me :D

  11. I think I *almost* got it. Whe you used ‘->>’ and ‘->>>’ you could have named them i.e. “Bob” and “Alice” right? It’s not a special notation in Scala, it’s just an arbitrary name that looks good… right?

    • Tomas,

      Yes, ->> and ->>> are type constructors in operator notation. I could also have written ->>[A, B] instead of A ->> B. And I could have used a letter like M, i.e. M[A, B]. But the arrows and operator notation make it much clearer that I am talking about maps (aka arrows).

  12. Det says:

    Interesting:

    So
    a) ->> is a type parameter … that is, similar to A and B in [A,B] ?
    Didn’t know that type parameter names can be symbolic, although in the end it seems consistent to the fact that classes/objects can have symbolic names.

    b) there is an infix notation for types with two parameters.
    Tested in REPL: class MyClass[A,B] ; type Check = String MyClass Int ; new Check
    creates new MyClass[String, Int] instance.

    Both of these facts, especially the latter, aren’t covered in the books, at least the ones I’ve read until now (or I must have overlooked it even when rescanning them), and at least not explicitly. Even Google did not bring up satisfying results.
    I assume this allows for very interesting stuff, so that lack of explicit mentioning is a bit sad.

    • Det,

      In my example ->> is a parameter for a type constructor (aka higher kinded type), i.e. for something that is not a type itself but needs to be give a type to create another one. Just think of List, which isn’t a type, but List[Int] is one.

      As operator notation works for “normal” methods, e.g. “John Doe” split ” “, it is just consistent that it works for type constructors, too.

      • Det says:

        Consistent, but not obvious to someone who has grown OO in Javaland. Java did not train the higher level thinking like Scala does.

        For a Java developer, your operator example is simply “omit the dot and the parens”. From a functional view this may be “put function name between the arguments”. But as this “function” is in this case -as we Java people got to learn- a method on class string, this knowledge is like a cave for Scala Think.

        Rereading the other comments after your response taught me to be more careful in reading. Type parameter, type constructor, type constructor parameter.
        As javapeople got Generics on top of an existing OO system, List is for us not a type constructor, but a “raw type”. And type is too much mixed up with class.
        You never had to think about the type of a collection, before Java 1.5 (meaning: not explicitly, consciously).

        It’s sometimes hard to put that aside and let Scala et al write on a clean sheet.

        What about a series covering “thinking in types for aged Javaanses”? ;-)

  13. Alexi says:

    Wondering if somebody can explain

    def id[A]: A => A = a => a

    I understand what it does, since I played with it in REPL, but I don’t understand how to read it from Scala syntax stand point.

    I understand it as type constructor which produces family of functions which take the same type as argument and return the same type. What I don’t understand how “a” is introduced. In other words how Scala knows that a is an argument for a function

    • Alexi,

      def id[A]: A => A = a => a is not a type constructor, but an arity-0 method (zero arguments) that returns a function. It is a polymorphic method, i.e. takes a type parameter A. A => A is the return type of the method which means you can call it for example with a String or an Int and get a function String => String or Int => Int. a => a is the “implementation” of the method, where a is just a named parameter for the function literal which makes up the return value of the method. You could call it b or foo or whatever you like.

      Hoping that helps.

      Cheers,

      Heiko

  14. volker bardenhorst says:

    very nice, so some of the scala constructs fit nicely into the set set up of categories

    are there examples where the RESULTS of cat theory were used to come up with something new or surprising results in programming?

  15. Surjit Sen says:

    The GitHub link https://github.com/weiglewilczek/fun is broken

  16. Stefan W. says:

    In diagram 2, shouldn’t ‘carnivore’ point to ‘meat’ and ‘herbivore’ to ‘grass’?

    Yes, I can imagine a meaning for the function ‘avoids to eat’ for example…

  17. Hi Heiko,
    something occurs to me re-reading this. You said “we now have something more general: A fmap method that works for any type for which we provide a functor.”

    It must be more than that though? If you need to provide a functor implementation for every kind so that fmap supports that kind, you could just implement that method on the kind itself. So it might seem that nothing has been gained.

    Surely the real benefit is that the implementation of fmap is now decoupled from the kind, fmap can now be added to any kind, even those you don’t have code for or written without the idea of fmap.

    Maybe I have missed something?

  18. H.Sugasawa says:

    That’s great!

    This post can help beginner to learn Scala and category theory.
    May I translate the post into Japanese and upload it onto Japan Scala Users’ Group website?
    http://jp.scala-users.org/

  19. Cap Table says:

    Pretty helpful, thanks for sharing.

  20. Pingback: A Taste of Monadic Design « Software Jockey

  21. Pingback: Category Theory and Scala http hseeberger wordpress com… « tylerweir

  22. >> dummkopf (screamingly funny for a German like me, according to http://www.dict.cc this seems to be a proper English verb)

    You probably meant “English noun”? :)

  23. Pete Kneller says:

    Fantastic post Heiko. Very clear and well thought out. Thanks!

    Like other readers I got stuck for a while on the use of symbolic type parameters, and the infix notation, but the comments have sorted me out there.

    I thought I understood functors and applicatives from playing with Haskell, but couldn’t wrap my head around the more general concept of a Category. This post, with those diagrams, has gotten me that much closer to grasping it. Thanks again!

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s