Skip to content

Instantly share code, notes, and snippets.

Last active May 8, 2023 16:03
Star You must be signed in to star a gist
What would you like to do?
Category theory jargon cheat sheet

Category theory jargon cheat sheet

A primer/refresher on the category theory concepts that most commonly crop up in conversations about Scala or FP. (Because it's embarassing when I forget this stuff!)

I'll be assuming Scalaz imports in code samples, and some of the code may be pseudo-Scala.


A functor is something that supports map.

e.g. List is a functor because you can do List(1, 2, 3).map(_ + 1).

Basically any type constructor with one hole is a functor. Option is the other standard example.

Something that supports map is only a functor if it obeys the 2 functor laws:

  1. Identity: for all functors F, = F
  2. Composition: for all functors F, = compose g)


List(1, 2, 3).map(x => x) == List(1, 2, 3)
List(1, 2, 3).map(x => x + 1).map(x => x * 2) == List(1, 2, 3).map(x => (x + 1) * 2)

It's worth noting that Function1[A, ?] is also a functor, using function composition (andThen) as our map operation.

type IntToSomething[R] = Function1[Int, R]
val addOne: IntToSomething[Int] = (i => i + 1)
val addOneAndToString: IntToSomething[String] = addOne.andThen(i => i.toString)

Here we've mapped a function over an IntToSomething[Int], resulting in an IntToSomething[String]. Just pretend we wrote map instead of andThen (which you can do if you're using Scalaz), and you've got a functor!


Extends functor, adding 2 new operations:

  • pure, also known as point. This takes a single value (e.g. 1) and wraps it in an applicative functor (e.g. List(1) or Some(1)).
  • <*>, also known as ap. This is similar to map, but instead of mapping a function across the values in the functor, it takes a functor containing one or more functions, and maps those functions across the values.

Some examples of the second operation, using Scalaz:

val list = List(1,2,3)
val addOne: Int => Int = _ + 1
val timesTwo: Int => Int = _ * 2
val functions: List(Int => Int) = List(addOne, timesTwo)
val result: List(Int) = list <*> functions
// List(2, 3, 4, 2, 4, 6)

As you can see, it maps all the functions in the second list across all the values in the first list, wrapping the result in another list.

Similarly for Option:

val maybeInt: Option[Int] = Some(123)
val maybeFunction: Option[Int => String] = Some(_.toString)
val result: Option[String] = maybeInt <*> maybeFunction
// Some("123")

List and Option are both examples of applicative functors.

Applicative functors must obey the applicative laws, which I'll gloss over.


A monad extends an applicative functor to add support for bind, also known as flatMap.

val list: List[Int] = List(100, 200, 300)
val function: Int => List[Int] = (i => List(i + 1, i + 2))
val result: List[Int] = list.flatMap(function)
// List(101, 102, 201, 202, 301, 302)

Again, glossing over the monad laws.


A semigroup is anything that supports appending.

e.g. 2 and 3 can be appended (resulting perhaps in 5 if you choose addition as your append operation, or 6 if you choose multiplication), so integers are a semigroup. List(1, 2, 3) and List(4, 5) can be appended, so List[Int] is a semigroup. Option[A: Semigroup] is also a semigroup: to append two Somes, you create a new Some containing the result of appending the two contained values.


A monoid is a semigroup with a zero value.

e.g. for integers under addition, it's 0. For integers under multiplication, it's 1. For lists, it's Nil.


TODO: I still have no idea what an Arrow is.


  • Functor supports map.
  • Applicative functor extends functor and adds pure and <*>.
  • Monad extends applicative and adds flatMap (a.k.a bind).
  • Semigroup supports append.
  • Monoid extends Semigroup and adds zero.
Copy link

crazzle commented Aug 3, 2015

Great stuff! Short and nice to read, thanks!

Copy link

cfeduke commented Aug 6, 2015

Really good. I was curious about arrow: "An arrow is the term used in category theory as an abstract notion of thing that behaves like a function."[1] and I learn best by example.[2]

If I had known about this in the past I think I would have saved myself a lot of match ... case on Option. Well, looking forward to the future.


Copy link

Thanks! Very concise and useful.

Copy link

cb372 commented Nov 9, 2015

Here's a (the?) paper about arrows:

Copy link

Thanks. Very useful !

Copy link

Copy link

alhassy commented Nov 12, 2018

You might find this elementary category cheat sheet of interest

Copy link

narley commented Jan 18, 2019

saving to my bookmark!!

Copy link

Please don't gloss over the laws, that should be part of the cheat sheet.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment