Skip to content

2023 01 06 Category theory

functionalProgramming math

Category theory is a branch of mathematics initially concerned with finding similar constructs within different areas of mathematics. It is a unifying theory. It later was applied to FP.

Parts

In category theory, objects can be anything: sets, numbers, matrices, just to name a few. In addition to having objects, a category also needs something called morphisms. A morphism can be defined only in the context of two objects from the category. Let us suppose that A and B are objects from a category C. Then a morphism is an arrow from A to B.

We write it like this:

  • A → B

But what does an arrow mean, exactly? Well, it connects object A to object B. Where the arrow starts and where the arrow ends is the information that defines the morphism.

In category theory, objects can be anything: sets, numbers, matrices, etc

A morphism from object A to object B is an arrow from A to B. You could also think of it as a pair of objects in a particular order.

First, morphisms compose. What does this mean? We will give the actual definition of two morphisms composing, but the general idea is that when you compose two morphisms, you call one morphism and then apply the second morphism to the result of calling the first morphism. Example:

f: A → B is a morphism, and g: B → C is a morphism. Since we are in a category, there must exist a morphism h from A to C satisfying: If f is a morphism from A to B, and g is a morphism from B to C, then there must exist a morphism h from A to C where for all x in A, h(x) = g(f(x)). In this case, we denote h with the expression g o f and call it f composed with g.

  • h(x) = g(f(x))

A set is just a collection of objects. The objects can be numbers, people, or even other sets. We are about to consider the category whose objects are all sets.

The identity function on a set A is the function that maps every element to itself. The category theory version of this is that the identity morphism on A, denoted idA, when it composes with another function, leaves that function unchanged. * idB o g = g

Category theorists tend to think not in terms of points, but rather in terms of composition of functions. The earlier expression is how you express the identity function in category theory in terms of composition.... Instead of saying identity morphism takes every point in the object to itself (because we don’t think about the points), you say that when you compose the identity morphism with another morphism, you get the original morphism back.

A semigroup is a non-empty set with an associative binary operation on it.

A semigroup has two main parts, a set of elements, (could be any non-empty set) and a binary operation on the set. A binary operation, like multiplication for whole numbers, takes two things and returns a third thing. There is one condition that must hold. The binary operation must be associative. We will denote the binary operation with an asterisk (*).

In a semigroup, we often call the binary operation multiplication, even if it is not necessarily the usual multiplication of numbers.

Functor
Is a function that when gets a type applied, produces another type:
List[String] is not a functor. It is a type. List by itself is a functor. When you apply it to a type, like String, for example, you get a type. This is why, in Scala, a functor is also called a type constructor.
(given two categories: C1 and C2.)
Then a functor F from C1 to C2 is a function from the first category to the second category, which satisfies the following properties.

  1. F takes objects in C1 to objects in C2. (Just like List takes String to List[String].)

  2. F takes morphisms in C1 to morphisms in C2. (What List does to a morphism is trickier. It involves the map function and we will address this next.)

  3. F(f o g) = F(f) o F(g) whenever the morphism domains and codomains of f and g line up.

This condition basically means that the two categories C1 and C2 have similar structure with respect to morphisms. The idea to keep in mind when considering functors is that they measure how similar two categories are.

Functors turn up in FP anywhere there are types that implement the map function. Think functor = mappable trait (or interface).

In category theory, the map function is what you get when you apply a functor to a morphism.
We know that there are three properties a functor from category C to category D must satisfy:

  • A functor F takes objects in C to objects in D. In the case of the category Scal, this means F takes Scala types to Scala types.

  • F takes morphisms in C to morphisms in D.

  • A composition property, seen here:

    F(f o g) = F(f) o F(g)$ where f and g are morphisms.

  • They always have a map function.

  • They can always be composed.

Monoids

As I mentioned earlier in the chapter, a semigroup is a set with an associative operation on it. If a semigroup has an identify element, which means an element e in the semigroup with the property that: e * x = x * e = x for all elements x in the semigroup, the semigroup is called a monoid.

Categories

Set

The objects are all sets. What are the morphisms? Simply all functions from A to B. Every function from A to B is a morphism. So the category Set is the category whose objects are sets and morphisms are functions from A to B, for all pairs of sets, A and B. A is called the domain of the morphism and B is called the codomain of the morphism

Sources

Learning Functional programming by Jack Widman in aug. 2022