No history yet

Morphisms and Composition

The Rules of the Arrows

In any category, the real action lies not with the objects, but with the arrows connecting them. These arrows, formally called morphisms, are more than just lines in a diagram. They represent structure-preserving transformations, functions, or any other kind of relationship that follows a strict set of rules. For any two objects, AA and BB, in a category, there's a collection of all morphisms from AA to BB. This collection is called a hom-set.

HomC(A,B) or simply Hom(A,B)Hom_\mathcal{C}(A, B) \text{ or simply } Hom(A, B)

Every category must obey two fundamental laws regarding its morphisms: the existence of an identity morphism for each object, and the requirement that composition of morphisms be associative.

  1. Identity: For every object AA, there must be a special morphism called the identity, idA:A→Aid_A : A \to A. When you compose any morphism with an identity morphism, you get the original morphism back. It's the categorical equivalent of doing nothing.

  2. Associativity: When you compose three or more morphisms in a sequence, the order in which you group them for composition doesn't matter. The result is always the same.

f∘idA=fandidB∘f=ff \circ id_A = f \quad \text{and} \quad id_B \circ f = f
h∘(g∘f)=(h∘g)∘fh \circ (g \circ f) = (h \circ g) \circ f

These rules might seem abstract, but they are the bedrock that gives categories their power. Associativity, in particular, ensures that our systems are predictable. It means we can drop the parentheses and just write h∘g∘fh \circ g \circ f, knowing the outcome is guaranteed. This is a property we take for granted in arithmetic and function composition, and category theory elevates it to a core structural principle.

Special Kinds of Arrows

Not all morphisms are created equal. Some have special properties defined by how they interact with other morphisms. Two of the most important types are monomorphisms and epimorphisms. In the familiar category of sets (Set), these correspond to injective (one-to-one) and surjective (onto) functions. But in category theory, we define them more abstractly using a property of cancellation.

A monomorphism is a morphism that is "left-cancellable." If you have two different morphisms that become the same after being composed with a monomorphism, then they must have been the same to begin with.

If f∘g1=f∘g2, then g1=g2\text{If } f \circ g_1 = f \circ g_2, \text{ then } g_1 = g_2

An is the dual concept. It's a morphism that is "right-cancellable." If composing two different morphisms on the right by an epimorphism yields the same result, then those two morphisms were identical all along.

If h1∘f=h2∘f, then h1=h2\text{If } h_1 \circ f = h_2 \circ f, \text{ then } h_1 = h_2

The pinnacle of morphisms is the isomorphism. An isomorphism is a morphism f:A→Bf: A \to B that has an inverse, a morphism g:B→Ag: B \to A, such that composing them in either order gives you the identity morphism.

g∘f=idAandf∘g=idBg \circ f = id_A \quad \text{and} \quad f \circ g = id_B

If an isomorphism exists between two objects, we say they are isomorphic. This is a profound idea: it means the two objects are essentially the same, just with different labels. They are structurally indistinguishable within that category.

From Theory to Code

These abstract concepts have direct, practical applications in functional programming. Consider the category often called Hask, where objects are types (like Int, String, [Bool]) and morphisms are functions between those types (like length: [a] -> Int).

In this world, composition of morphisms is simply function composition. The identity morphism id_A is the identity function id :: a -> a for a given type a. The laws of category theory hold perfectly.

// Scala example
def compose[A, B, C](g: B => C, f: A => B): A => C = {
  a => g(f(a))
}

// Or more simply using the built-in composer
val h = g.compose(f) // same as g ∘ f

// Associativity: (h ∘ g) ∘ f is the same as h ∘ (g ∘ f)
val f: Int => String = _.toString
val g: String => Boolean = _.length > 5
val h: Boolean => String = b => if (b) "long" else "short"

val composed1 = h.compose(g).compose(f)
val composed2 = h.compose(g.compose(f))

println(composed1(123456)) // prints "long"
println(composed2(123456)) // prints "long"

A function that is a monomorphism in Hask is an injective function. An epimorphism is a surjective function. An isomorphism is a bijective function, a one-to-one correspondence between two types.

For example, a function converting a Char to its Int ASCII value is a monomorphism; no two different characters map to the same integer. A function that checks if an integer is even (Int -> Bool) is an epimorphism, as both true and false can be reached.

Understanding these categorical laws helps you reason about your code at a higher level of abstraction. It ensures that when you build complex systems by composing simple parts, the result is predictable, reliable, and mathematically sound.

Let's test your understanding of these core concepts.

Quiz Questions 1/6

What are the two fundamental laws that all morphisms in a category must obey?

Quiz Questions 2/6

In category theory, the collection of all morphisms from an object AA to an object BB is known as a _______.