Category Theory

Usefulness

I am still uncertain about the usefulness of learning category theory.

Notes

Categories

A Category is a bunch of objects and morphisms.

The morphisms must be composable and associative, meaning

f ∘ (g ∘ h) = (f ∘ g) ∘ h = f ∘ g ∘ h

where f, g, and h are morphisms and ∘ is composition.

There must be an identity morphism for each object in the category such that

f ∘ id = f

and

id ∘ f = f

hom-set

A set of morphisms from object 𝑎 to object 𝑏 in a category 𝐂 is called a hom-set and is written as 𝐂(𝑎, 𝑏)

Initial object

The initial object is the object that has one and only one morphism going to any object in the category.

There is only one unique initial object even though multiple objects in a category can satisfy the definition, because those objects are all equal up to isomorphism, whatever that means.

There might not be an initial object in a category. For example, the category of the integers with the less than or equal to relationship as morphisms doesn't have an initial object because the negative integers never end. Given any number, there's always a lesser one.

Opposite category

If you reverse the direction of all the morphisms in a category, you get Cop, the opposite category. You just need to redefine morphism composition. Opposite categories usually have the prefix "co".

Product

A product of two objects a and b is the object c equipped with two projections such that for any other object c' equipped with two projections there is a unique morphism m from c' to c that factorizes those projections.

Note that this is the product of objects in a category, not the product of two categories.

The product does not necessarily exist.

Total and Partial Functions

Functions always have one argument. Their arity is always 1.

A total function is defined for every element in its domain, which is the set (in Haskell, it's type, which is a set) of its argument.

A partial function is only defined for some elements of its domain, but not every element.

A bijection is a function that is truly symmetric. It is a one to one mapping from one set to another and it can be inverted to get a one to one mapping from the codomain back to the domain. Bijections in set theory are the same as isomorphisms in category theory.

Applications

Monoids

A monoid is an algebraic structure with an associative binary operation and an identity element.

Examples:

Integers, where 0 (zero) is the identity element and + (addition) is the associative binary operator.

Strings, where '' (the empty string) is the identity element and ++ (concatenation) is the associative binary operator.

Monoids can be considered a category with one object. I think the one object is a set. So the set of strings is one object, and morphisms are just functions from that set to itself.

0 is like a initial object 1 is like a terminal object

Haskell

The Haskell type system is a category.

The product of two types is a pair of those types, denoted by (a, b).

The sum of two types is denoted by Either a b.

In Haskell, Void is an uninhabited type, meaning it is a type with no values. The function from Void -> a is called absurd and it can never be called because an argument for it does not exist.

In Haskell, () is called unit and it represents a singleton I think.

The pair (a, ()) is isomorphic to a and Either a Void is isomorphic to Void. This is similar to a × 1 = a and a × 0 = 0.

Isomorphism

An isomorphism is when there's a morphism from one object to another and another morphism from the second object back to the first. We say that those two objects are equal up to isomorphism, because you can always get one from the other by following a morphism.

Containers

If functions are pure, then there's almost no difference between a function and a container. What's the difference between a hash map of the values of sin vs a function for sin?

Writing

What does a database write look like in functional programming? If every function is pure, how do I write to a file or to the screen or to the DOM?

Bifunctors

I finally understand why they're useful. We need functor of two arguments in order to have structures of arbitrary length.

Let's first look at functors of one argument. A functor of one argument is like Identity a, which takes a type a and maps it to something like Identity String, depending on what a is.

A bifunctor takes two arguments, like Cons a (List b).

Covariant and Contravariant Functors

A functor from one category to another is covariant. So all functors are covariant. A contravariant functor is from an opposite category to a category. All contravariant functors are also covariant.

Profunctors

A profunctor is a bifunctor whose first functor is covariant and second argument is contravariant.

Currying

Haskell types form a category.

Each Haskell type is a set (maybe only up to isomorphism, I'm not sure).

Every function can only have one argument, which is a type (which is a set).

We know that the product of two types (sets) is a pair of those types. For example, the product of the types String and Int is (String, Int). A pair is itself a type. Since a pair is a type and functions can only take one type as an argument, a function can take a pair of types as an argument.

This is where currying comes in. The function we call "curry" is obtained by using the universal construction. (Note, I need to clarify here exactly how that's done). At the end of it you get a function (curry) that takes a function that takes a pair and returns a function that returns a function.

It goes from (a, b) -> c to a -> b -> c.