Composition

On the cover of the awesome book “category theory for programmers”, we can see the visual explanation of what “composition” is about:

Arrows compose, so if you have an arrow from object **X** to object **Y**, and another arrow from object **Y** to object **Z**, then there must be an arrow — their composition — that goes from **X** to **Z**.

Think of arrows, which are also called morphisms, as functions.

• **f** is a function that takes an argument of Type **X** and returns **Y**.
• **g** is a function that takes an argument of Type **Y** and returns **Z**.
• you can compose them by passing the result of **f** to **g**.

In math, such composition is denoted by:

$$g\circ f$$

The essence of a category is composition.

Let’s make this even more explicit by writing some C code. We have one function f that takes an argument of type A and returns a value of type B:

B f(A a);

and another:

C g(B b);

Their composition is:

C g_after_f(A a) {
		return g(f(a));
}

---

Properties of Composition

There are two extremely important properties that the composition in any category must satisfy;

1. Composition is associative
   1. If you have three morphisms, **f**, **g**, and **h**, that can be composed (that is, their objects match end-to-end), you don’t need parentheses to compose them. In math notation this is expressed as:

$$h◦(g◦f)=(h◦g)◦f=h◦g◦f$$

In (pseudo) Haskell:

f :: A -> B
g :: B -> C
h :: C -> D
 
-- h . (g . f) == (h . g) . f == h . g . f

2. For every object A there is an arrow which is a unit of composition 2. This arrow loops from the object to itself. Being a unit of composition means that, when composed with any arrow that either starts at A or ends at A, respectively, it gives back the same arrow. 3. The unit arrow for object A is called idA (identity on A). In math notation, if f goes from A to B then:

$$f◦id\underset{A}{}=f$$

(idA can also be called 1A)

4. When dealing with functions, the identity arrow is implemented as the identity function that just returns back its argument. The implementation is the same for every type, which means this function is universally polymorphic. In C++ we could define it as a template:

template<class T> T id(T x) { return x; }

Nice, now let’s take a look how this identity can be implemented in Go:

package main
 
import "fmt"
 
type Object interface{}
 
type Morphism func(Object) Object
 
func Identity(x Object) Object {
    return x
}
 
func main() {
    f := func(x Object) Object {
        return x.(int) + 1
    }
    id := Identity
 
    // Compose f with id
    composed := func(x Object) Object {
        return f(id(x))
    }
 
    fmt.Println(composed(5)) // Output: 6
}

---

We decompose bigger problems into smaller problems. If the smaller problems are still too big, we decompose them further, and so on. Finally, we write code that solves all the small problems.

And then comes the essence of programming: we compose those pieces of code to create solutions to larger problems. Decomposition wouldn’t make sense if we weren’t able to put the pieces back together.

Category theory is extreme in the sense that it actively discourages us from looking inside the objects. An object in category theory is an abstract nebulous entity. All you can ever know about it is how it relates to other object — how it connects with them using arrows

---

🌱 Back to Garden