{{ message }}

Instantly share code, notes, and snippets.

# cb372/jargon.md

Last active Mar 15, 2021
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)
``````

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.

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 `Some`s, 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 commented Aug 3, 2015

 Great stuff! Short and nice to read, thanks!

### 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." and I learn best by example. 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.

### growlingchaos commented Aug 7, 2015

 Thanks! Very concise and useful.

### cb372 commented Nov 9, 2015

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

### arunlakshman commented Jul 27, 2017

 Thanks. Very useful !

### 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 commented Jan 18, 2019

 saving to my bookmark!!

### adam-arold commented Apr 19, 2019

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