Skip to content

Instantly share code, notes, and snippets.

@cb372
Last active May 14, 2024 03:45
Show Gist options
  • Save cb372/b1bad150e0c412fb7364 to your computer and use it in GitHub Desktop.
Save cb372/b1bad150e0c412fb7364 to your computer and use it in GitHub Desktop.
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.

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.
@crazzle
Copy link

crazzle commented Aug 3, 2015

Great stuff! Short and nice to read, thanks!

@cfeduke
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.

  1. http://eed3si9n.com/learning-scalaz/Arrow.html
  2. http://www.casualmiracles.com/2012/07/02/a-small-example-of-kleisli-arrows/comment-page-1/

@growlingchaos
Copy link

Thanks! Very concise and useful.

@cb372
Copy link
Author

cb372 commented Nov 9, 2015

Here's a (the?) paper about arrows: http://www.cse.chalmers.se/~rjmh/Papers/arrows.pdf

@arunlakshman
Copy link

Thanks. Very useful !

@neko-kai
Copy link

@alhassy
Copy link

alhassy commented Nov 12, 2018

You might find this elementary category cheat sheet of interest
https://github.com/alhassy/CatsCheatSheet/blob/master/CheatSheet.pdf

@narley
Copy link

narley commented Jan 18, 2019

saving to my bookmark!!

@adam-arold
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