Category theory jargon cheat sheet

jargon.md

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.

Functor

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.map(identity) = F
2. Composition: for all functors F, F.map(f).map(g) = F.map(f compose g)

e.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!

Applicative

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.

Monad

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.

Semigroup

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.

Monoid

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.

Arrow

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

Recap

• 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.