By Jasna in code —

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
  • Create your own monads!
    • 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?)

To learn more about category theory, you shouldn't ask me. See (Understandable) Resources.

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[1](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!)

Functor identity: mapping over a List with identity^7^ results in the same List.

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

Functor composition. mapping 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.

Monad

  • 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*

Text

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 ↩︎