Reading Category Theory for Programmers by Bartosz Milewski on stream.

Previous reading: 20260213033430

At the beginning of stream, I talked about:

• Someone random found the #godot:tsuki.games matrix channel, because it got indexed on https://matrixrooms.info/search/godot
• Nubby's Number Factory is almost the Numberwang game I didn't know I wanted.

Part 1, Section 3
Categories Great and Small:

• Types of categories
  • No Objects
    • An empty category has no objects. Since it has no objects, it also has no morphisms.
  • Simple Graphs
    • A free category is a set of objects and all possible morphisms and combinations of morphisms (also known as chains) between those objects.
  • Orders
    • A preorder is a set of objects and morphisms between those objects where the morphisms define an order between the objects. There is at most one morphism from any object a to any object b. Since there is at most one morphism between each pair of objects, this is also known as a thin category. Cycles can exist. They don't say it here, but I think they mean that not every element is necessarily comparable (for example, it could say x < z and y < z and say nothing about the relation between x and y), based on my reading of Category Theory Illustrated. ¹
    • A partial order is a preorder where if a ≤ b and b ≤ a, then a must be the same as b. Because of this, cycles cannot exist.
    • A linear order or a total order is a partial order where each pair of elements is comparable.
    • A set of morphisms between a pair of objects in a category is known as a hom-set. For example, Hom_C(a, b) is the set of morphisms between a and b in category C, which is either empty or a singleton for a preorder.
• Monoid as Set
  • A monoid is a set, an associative binary operation, and a unit element. For example, the natural numbers under addition with zero (the unit element) is a monoid.
    • Addition is commutative, but this is not required for monoids.
  • For a very long time, I've wondered why combining functions together in Haskell is known as "point-free" syntax

    • In Haskell, there are two ways to write a function definition. Consider the following functions:
      hs foo :: a -> b bar :: b -> c foobar :: a -> c

    • To define foobar, one can either do foobar a = bar (foo a) or foobar = bar . foo.

    • It's weird that the second one is considered to be "point-free", because the operator to combine functions together is literally a point.

    • The author says that when writing a function definition with the arguments, the values of the arguments are sometimes called points. Defining the function this way is known as extensional equality or point-wise equality.

    • However, when the "points" or arguments are left out, we're defining the morphism equality and is known as point-free.

• Monoid as Category
  • Monoid as a set defines a monoid in terms of elements of a set. But in Category Theory, we want to be less concerned with the contents of objects and focus more on the morphisms.
  • Think of the application of the binary operator as moving or shifting things around a set.
  • For numbers:
    • The functions that adds zero is the identity morphism
    • For every number n there is a functions which can add n.
    • The functions that add a specific amount can be combined with one another to create another function that adds a specific amount. We could call these adders.
    • mappend :: m -> m -> m from Haskell can be interpreted as m -> (m -> m), which can be read as "given some number n, returns an adder that adds that number to another."
    • Forget the numbers -- just think about the set of all the adders. A monoid is a single object category. There's only one thing in this category: the adders.
  • For strings:
    • There's two ways we can define a monoid for a string, using appending or prepending the string. They create monoids that seem to be mirror images of each other.
  • Every monoid is a single object category with a set of morphisms that follow the rules of composition.
  • Morphisms don't technically have to form a set, but in the case of the addition monoid as a category, it does.
  • The elements of a hom-set can be seen both as points in a set (as in, the numbers 1, 2, 3, 4, etc...) and as morphisms (as in, the "adders" +1, +2, +3, +4, etc...)

Challenges:

1. I think the author means that I should draw these. I did that on stream and skipped including them here for filesize reasons.
2. What kind of order is this?
   1. I think this is a partial order, because the inclusion relation cannot provide totality if a set is not fully contained within another and we cannot necessarily provide an order between every pair of sets, but it does provide reflexivity, transitivity, and antisymmetry. These are all of the properties required by a partial order.
   2. I think the same applies for C++ subtyping. I feel like I'm wrong about this, but I don't know what the contradiction is yet.
3. There are two sets for boolean. Booleans under AND with true as the identity element and Booleans under OR with false as the identity element.
4. The identity morphism is and true, the other morphism is and false. There are no other morphisms i think. (and true) and (and false) compose into and false. (and false) and (and true) also composes into and false.
5. The morphisms are +0 % 3 (identity), +1 % 3, +2 % 3.
   • (+1 % 3) + (+1 % 3) is +2 % 3.
   • (+2 % 3) + (+2 % 3) is +1 % 3.
   • (+1 % 3) + (+2 % 3) is +0 % 3 and (+2 % 3) + (+1 % 3) is +0 % 3.