# Intro to category theory for functional programmers

Notes on a presentation I gave for work!

## What's the point?

• Better understand your everyday toolbox and law violations / compilation errors / wtfjavascript errors
• safe function composition --> value wrapping; "metadata"

## Disclaimer

I am no expert and am continuning to grok more category theory as I write and revise this. Please comment for any corrections.

## Goal: Grok this sentence

A monad is a monoid in the category of endofunctors.

To dissect, but not in this order:

• What is a monad?
• What is a monoid?
• What is a category?
• What is an endofunctor?
• (What is a functor?)
• (What is category theory?)
• (What are some other related terms commonly thrown around?)

## What is category theory?

The study of objects based on their relationships between one another rather than their intrinsic characteristics. In other words, learning about things in context rather than in isolation. See Eugenia Cheng, Lambda World: Category Theory in Life.

## What is a category?

A collection of 3 components. In Scala, a category is represented as a type class. The 3 components are

1. A collection of objects
• For programmers, types
• For mathematicians, anything
2. A collection of arrows. An arrow is
• A way to turn things into other things while preserving their internal structures
• A morphism
• For programmers, a function
3. A representation of following certain laws:
• identity
• composition, which is typically associative

Example: `trait Cat[Int]`, for "Category of Integers":

``````trait Cat[Int] {
def identity: Int = ???
def compose(a: Int, b: Int): Cat[Int] = ???
}
``````

From now on, "objects" will be referred to as "types".

## Categorical Laws

When we say that a type class must "provide evidence" to be a lawful category, monad, monoid, etc., we mean that they must implement functions the represent certain laws:

#### Identity

Examples

• `empty` in Cats `Monoid`
• `zero` in Scalaz `Monoid`

identity: A function for a type that doesn't affect the result of a composition of types(https://en.wikipedia.org/wiki/Identity_element)^.

``````trait Cat[Int] {
def identity: Int = 0
def compose(a: Int, b: Int): Cat[Int] = ???
}
``````

#### Composition

Example: `flatMap`

composition:^2^ if a category has arrows that go from `A -> B` and `B -> C`, then one can derive a morphism to go from `A -> C`. In other words, if there is a morphism in which the target type^3^ matches the source type^4^ of another morphism, we can combine the morphisms to go from the first morphism's source type to the second morphism's target type.

``````trait Cat[Int] {
def identity: Int = 0
def compose(a: Int, b: Int): Cat[Int] = a + b
}
``````

(If we were to compose with multiplication, our `identity` would be `1`.)

^2^ Aka a binary operation.

^3^ Aka "codomain"

^4^ Aka "domain"

#### Associativity

Composition must be associative, i.e., the order of compositions for a type does not matter as long as the order of types^3^ stays the same.

Or, as we learned in high school, moving parentheses around when adding or multiplying (but keeping the order of individual numbers the same) yields the same result.

`(1 + 3) + 7 = 1 + (3 + 7)`

``````val monsters = Some("Monsters")
val demons   = Some("Demons")
val men      = Some("Men")
val jasna    = Some("Wonder Woman")

val res1 =
monsters
.flatMap(_ => demons
.flatMap(_ => men)
).flatMap(_ => jasna) // Some("Wonder Woman")

val res2 =
monsters
.flatMap(_ => demons)
.flatMap(_ => men)
.flatMap(_ => jasna) // Some("Wonder Woman")
``````

^3^ Aka operands in mathematics.

## What is a monoid?

• a category with 1 type, or
• a semigroup with identity and closed associative composition

closed: the resulting type is the same as the parameter(s)' types

Examples

• Cats Monoid
• `cats.Monoid.empty` is the identity law evidence
• Extends `cats.Semigroup`, which provides `cats.Semigroup.combine`, the composition law evidence
• `Semigroup` has a single type as well, the single associative composition
• scalaz Monoid
• `scalaz.Monoid.zero` is the identity law evidence
• `scalaz.Monoid.append` is the composition law evidence
• This comes from `scalaz.Semigroup`, which follows SemigroupLaw's closed composition and associativity

## What is a functor?

• an arrow between categories^6^, or
• a wrapper around values of different or same types, that
• follows functor laws of identity and composition (like category!)

• in Scala, a type class with `map`

Functor identity: `map`ping over a `List` with `identity`^7^ results in the same `List`.

``````List(1, 2, 3) map {identity} assert_=== List(1, 2, 3)
``````

Functor composition. `map`ping from `List` to `List` to `List` to `List`, parentheses don't matter.

``````(List(1, 2, 3)
map {{(_: Int) * 3}
map {(_: Int) + 1}})
assert_=== (List(1, 2, 3)
map {(_: Int) * 3}
map {(_: Int) + 1})
``````

^6^ The collection of functors between two given categories is also considered a category, aka the functor category.

^7^ Here we are referring to Scala's native `identity` function, which in practice sugars `foo.fold(a => a, b => bar)` to `foo.fold(identity, b => bar)`

### What is an endofunctor?

• an arrow that turns a category `A` back into category `A`, or
• a functor in which the source category is the same as the target category. (like closed composition.)

Example: `map map map`!

We often deal a lot with endofunctors in programmatic function composition.

• a category with one type (monoid)
• that implements `flatMap` (and `map`) (which makes it a functor)
• (`map` is closed, so monad's an endofunctor)
• has a constructor to create a new (monadic) instance from a plain value
• `cats.Monad.pure`
• `scalaz.Applicative.point` or alias `.pure`
• `scalaz.Monad` extends `scalaz.Applicative`

In other words, a monad is a category, specifically, a monoid, that is a functor which is also an endofunctor. Does this sound familiar?

## Summary (in dev speak)

• category: typically a class / wrapper around types with a set of functions that follow the laws of identity and associative composition
• semigroup:^✪^ almost a category; doesn't necessarily follow identity
• monoid: a category with 1 type and specifically closed composition
• functor: a category or arrow between categories; has `map`
• endofunctor: an arrow whose source category = its target category, like `map`
• natural transformation:^✪^ a set of functors between two given categories
• monad: A monad is a monoid in the category of endofunctors. Obviously.

## ✪ Bonus

### Wrappers as "metadata"

Daniela Sfregola thinks of these wrappers--monads, monoids, functors, and endofunctors--as "metadata" for your pure value types, or your data. In other words, wrappers as metadata transcend the data and provide a safe, consistent container for your data--most importantly, they tell you whether or not a value is empty and how to safely chain operations with them.

### Semigroup^8^

A type class^9^ that follows the law of associative composition but not necessarily of identity. So not all semigroups are valid categories!

^8^ See cats.Semigroup and scalaz.Semigroup.

^9^ In math, it's an algebraic structure.

### Natural transformation

A collection of functors between 2 given categories. When composing functors, the internal structures of the functors are respected. Comparing with other terms:

• functor = category morphism
• natural transformation = functor morphism

### The Category of "Sets"

In the world of category theory, we programmers operate in the broad category of Sets, for our morphisms are functions: ## (Understandable) Resources*

### Video

*Like this talk, these resources may not be entirely mathematically accurate. But hopefully they are enough to level up as a functional programmer.

1. 1 ↩︎