Skip to content

Instantly share code, notes, and snippets.

@cb372 cb372/jargon.md
Last active Jul 31, 2019

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

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

This comment has been minimized.

Copy link

commented Aug 3, 2015

Great stuff! Short and nice to read, thanks!

@cfeduke

This comment has been minimized.

Copy link

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

This comment has been minimized.

Copy link

commented Aug 7, 2015

Thanks! Very concise and useful.

@cb372

This comment has been minimized.

Copy link
Owner Author

commented Nov 9, 2015

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

@arunlakshman

This comment has been minimized.

Copy link

commented Jul 27, 2017

Thanks. Very useful !

@neko-kai

This comment has been minimized.

Copy link

commented May 27, 2018

@alhassy

This comment has been minimized.

Copy link

commented Nov 12, 2018

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

@narley

This comment has been minimized.

Copy link

commented Jan 18, 2019

saving to my bookmark!!

@adam-arold

This comment has been minimized.

Copy link

commented Apr 19, 2019

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
You can’t perform that action at this time.