Skip to content

Instantly share code, notes, and snippets.

@daewon daewon/jargon.md forked from cb372/jargon.md
Last active Aug 29, 2015

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