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

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

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

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!

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

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

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

Thanks. Very good article.

@ 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 aparameterof type A and returns something with type B” while the second one says “takes atypeA 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.

Pingback: Functional Code in the News « Statically Typed

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 bitmore comprehensible to me :DI 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).

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, butList[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.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,

Listis 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”? ;-)

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 => ais 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 parameterA.A => Ais the return type of the method which means you can call it for example with aStringor anIntand get a functionString => StringorInt => Int.a => ais the “implementation” of the method, whereais just a named parameter for the function literal which makes up the return value of the method. You could call itborfooor whatever you like.Hoping that helps.

Cheers,

Heiko

Thanks a lot. I get it now

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?

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

Sorry, but things change ;-)

I suggest you take a look at the Scalaz sources.

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…

You got it ;-)

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?

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/

Sure. Thanks!

Pretty helpful, thanks for sharing.

Pingback: A Taste of Monadic Design « Software Jockey

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

>> 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”? :)

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!