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.
A functor is something that supports
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:
- Identity: for all functors F, F.map(identity) = F
- Composition: for all functors F, F.map(f).map(g) = F.map(f compose 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
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!
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.
<*>, 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
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.
A semigroup is anything that supports appending.
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.
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
TODO: I still have no idea what an Arrow is.
- Functor supports
- Applicative functor extends functor and adds
- Monad extends applicative and adds
- Semigroup supports
- Monoid extends Semigroup and adds