Category

Foundation, type systems/APIs

Publish at: 16 Dec 2025

category theory category-theory morphism homomorphism isomorphism

  ____    _  _____ _____ ____  ___  ____  ___ _____ ____
 / ___|  / \|_   _| ____/ ___|/ _ \|  _ \|_ _| ____/ ___|
| |     / _ \ | | |  _|| |  _| | | | |_) || ||  _| \___ \
| |___ / ___ \| | | |__| |_| | |_| |  _ < | || |___ ___) |
 \____/_/   \_|_| |_____\____|\___/|_| \_|___|_____|____/

Every time you start writing a piece of code, sooner or later you find yourself in the position of splitting that code into parts. The decision of how to split the code might come naturally (with no prior planning), or with detailed planning regarding the method of splitting and the maintainability that comes with it. Nevertheless, splitting always comes to how parts are composed together to produce the final outcome.

Composition can be found everywhere in software development. From simple function call chaining and the identity function that glues things around rough edges, to wiring up modules (linking) or chaining data pipeline transformation steps.

A few examples:

Function composition - Combining two or more functions to produce a new one.

const h = x => g(f(x)); // h is the composition of g and f

Object composition - Delegation or aggregation of objects

const car = { ...engine, ...wheels, ...body };

Class composition - Combining behaviors from multiple classes (opposite to inheritance)

class Walk: ...
class Quack: ...
class Swim: ...
class Duck(Walk, Quack, Swim): ...

Module composition - assembling modules from existing ones

import X from './x';
import Y from './y';

Data processing composition - Passing data through a sequence of processing steps (pipelines)

cat file.txt | grep "error" | sort

There is a common pattern here. We combine smaller pieces of code to build something bigger. What if we could identify and formalize this pattern? This way we could study it and extract more useful properties.

Let’s start with some code to see these ideas in action.

import Prelude hiding ((.))

infixr 9 .
(.) :: (b -> c) -> (a -> b) -> (a -> c)
g . f = \x -> g (f x)

f :: Int -> String
f x = show x

g :: String -> Bool
g s = length s > 2

h :: Int -> Bool
h = g . f  -- Composition

main = print (h 123)  -- Output: True

const compose = (g:(_:string)=> boolean, f:(_:number)=> string) =>
    (x:number) => g(f(x));

const f = (x:number) => x.toString();      // Number -> String
const g = (s:string) => s.length > 2;      // String -> Boolean

const h = compose(g, f);          // Number -> Boolean

console.log(h(123)); // Output: true

Func<A, C> Compose<A, B, C>(Func<B, C> g, Func<A, B> f)
    => x => g(f(x));

Func<int, string> f = x => x.ToString();
Func<string, bool> g = s => s.Length > 2;

var h = Compose(g, f); // Func<int, bool>
Console.WriteLine(h(123)); // Output: True

What’s going on here?

In each language, you can see two key ideas:

Identity: A function that does nothing (id).
Composition: Combining two functions into one (compose or .).

Enter Category #

A category is a structure consisting of:

Objects:
- Abstract entities. In programming, these can often be thought of as types (e.g., Int, String).
Morphisms (Arrows):
- Directed relationships between objects. In programming, these are often functions (e.g., f :: Int -> String).
Composition:
- Morphisms can be composed. If you have a morphism f: A -> B and another g: B -> C, you can compose them to get g ∘ f: A -> C.
- Composition must be associative: (h ∘ g) ∘ f = h ∘ (g ∘ f).
Identity Morphism:
- Every object has an identity morphism id: A -> A that acts as a neutral element for composition:
  - id ∘ f = f and g ∘ id = g.

How do our code examples fit?

Objects: Types like Int, String, or Number.
Morphisms: Functions like f, g, and h.
Identity: The id function.
Composition: The compose function or the . operator. ^[1]

All the code above forms a category because:

Composition is associative.
The identity function acts as a neutral element.

Proof sketch (functions as morphisms):

Associativity

For functions f: A -> B, g: B -> C, h: C -> D and any x ∈ A:
```
((h ∘ g) ∘ f)(x) =
(h ∘ g)(f(x)) =
h(g(f(x))) =
h((g ∘ f)(x)) =
(h ∘ (g ∘ f))(x)
```
Since the two composites agree on every input, they are equal as functions.
Identities

Let id_A : A -> A and id_B : B -> B be identity functions.

For any f: A -> B and any x ∈ A:
- (id_B ∘ f)(x) = id_B(f(x)) = f(x)
- (f ∘ id_A)(x) = f(id_A(x)) = f(x)
Hence id_B ∘ f = f and f ∘ id_A = f by function extensionality (equality by agreeing on all inputs).

Understanding categories helps extract structure behind everyday programming:

Abstraction: You can reason about code at a higher level.
Reusability: Higher-order patterns (functors, monads) build on categories.
Composability: You can build complex systems from simple, composable parts.

OK, maybe not so simple for now. How about an example from geometry?

Objects: Squares and triangles in the plane.
Morphisms: Transformations that map one shape to another, such as rotations, translations, or scaling (as long as the transformation maps a square to a square, or a triangle to a triangle).
- A rotation that turns a square by 90° (maps the square to itself).
- A translation that moves a triangle from one place to another (maps the triangle to itself).
- The identity transformation (does nothing). ^[2]
Category Structure
- Composition: If you rotate a square and then translate it, the result is another transformation (composition of morphisms).
- Identity: The "do nothing" transformation for each shape.

Hopefully it starts to make sense.

Our examples from above in a more formal fashion:

Haskell perspective #

You can think of a category as:

Objects: Types (e.g., Int, String).
Morphisms: Functions between types (e.g., f :: Int -> String).

Identity Morphism

id :: a -> a
id x = x

Composition

(.) :: (b -> c) -> (a -> b) -> (a -> c)
g . f = \x -> g (f x)

Example

f :: Int -> String
f x = show x

g :: String -> Bool
g s = length s > 2

h :: Int -> Bool
h = g . f  -- Composition of g and f

main = print (h 123)  -- Output: True

TypeScript perspective #

You can think of a category as:

Objects: Types (e.g., Number, String).
Morphisms: Functions between those types.

Identity Morphism

// Identity function
const id = x => x;

Composition

// Function composition
const compose = (g, f) => x => g(f(x));

// Example functions
const f = x => x.toString();      // Number -> String
const g = s => s.length > 2;      // String -> Boolean

const h = compose(g, f);          // Number -> Boolean

console.log(h(123)); // Output: true

This forms a category because:

Composition is associative:

compose(h, compose(g, f)) === compose(compose(h, g), f)
Identity function acts as a neutral element:

compose(id, f) === f and compose(f, id) === f

C# perspective #

Objects: Types (e.g., int, string)
Morphisms: Functions (delegates) between those types

Identity Morphism

// Identity function
Func<T, T> Id<T>() => x => x;

Composition

// Function composition
Func<A, C> Compose<A, B, C>(Func<B, C> g, Func<A, B> f)
    => x => g(f(x));

// Example functions
Func<int, string> f = x => x.ToString();
Func<string, bool> g = s => s.Length > 2;

var h = Compose(g, f); // Func<int, bool>
Console.WriteLine(h(123)); // Output: True

This forms a category because:

Composition is associative
Identity function acts as a neutral element

Formal definition #

A category consists of:

A collection of objects (denoted as A, B, C, etc.).
A collection of morphisms (arrows) between objects:
- A morphism f has a domain and a codomain, written as f: A -> B, meaning f maps object A to object B.

Two Key Rules #

Composition:
- If f: A -> B and g: B -> C, then there exists a morphism g ∘ f: A -> C (read as "g after f").
- Composition must be associative:
  - For all f: A -> B, g: B -> C, and h: C -> D, we have:
    - (h ∘ g) ∘ f = h ∘ (g ∘ f).
Identity Morphism:
- For every object A, there exists an identity morphism id_A: A -> A such that, for all suitable f and g:
  - id_B ∘ f = f (when f: A -> B).
  - g ∘ id_A = g (when g: A -> C).

Examples of Categories #

Category of Sets:

Objects: Sets (e.g., {1, 2, 3}, {a, b, c}).
Morphisms: Functions between sets (e.g., f(x) = x + 1).
Composition: Function composition (g ∘ f)(x) = g(f(x)).
Identity Morphism: The identity function id(x) = x.

Category of Types (in Haskell):

Objects: Types (e.g., Int, String).
Morphisms: Functions between types (e.g., f :: Int -> String).
Composition: Function composition (.) in Haskell.
Identity Morphism: The id function in Haskell.

Preordered sets:

Any preordered set is a category. For two given elements p, q of a preordered set, there is a morphism f: p -> q if and only if p <= q. Hence a preordered set is a category in which there is at most one morphism between any two objects.

Note that a category is characterized by its morphisms, and not by its objects.

Homomorphism #

In category theory, "morphism" is the generic term for arrows. The word "homomorphism" is typically reserved for algebraic categories (e.g., Groups, Rings, Modules), where morphisms are the familiar structure‑preserving maps. In the category of sets we usually just say "function".

Isomorphism #

In category theory, we often encounter situations where two objects are "essentially the same" even though they might look different on the surface. An isomorphism captures this notion of categorical equivalence - it's a morphism that can be perfectly "undone" by another morphism going in the reverse direction.

An isomorphism in category theory is a morphism that has a two-sided inverse. Formally, a morphism f: A -> B in a category C is an isomorphism if there exists a morphism g: B -> A such that:

g ∘ f = id_A (left inverse)
f ∘ g = id_B (right inverse)

The morphism g is called the inverse of f, often written as f⁻¹.

An isomorphism is the category‑theoretic equivalent of saying "what goes up must come down" — if you can transform object A into object B via some morphism, and you can also transform B back into A in a way that perfectly cancels out the first transformation, then those objects are isomorphic.

Key Properties #

Uniqueness of Inverse: If a morphism has an inverse, that inverse is unique.
Symmetry: If f: A -> B is an isomorphism with inverse g, then g: B -> A is also an isomorphism with inverse f.
Composition: The composition of isomorphisms is an isomorphism:
- If f: A -> B and g: B -> C are isomorphisms
- Then g ∘ f: A -> C is an isomorphism
- With inverse (g ∘ f)⁻¹ = f⁻¹ ∘ g⁻¹
Identity: Identity morphisms id_A: A -> A are always isomorphisms (with themselves as inverses).

Isomorphic Objects #

Two objects A and B are isomorphic (written A ≅ B) if there exists an isomorphism between them. This means:

They are essentially "the same" from the category's perspective
They have the same categorical properties
Any categorical construction that applies to one applies to the other

-- These types are isomorphic
(A, B) ≅ (B, A)        -- Tuple commutativity
(A, (B, C)) ≅ ((A, B), C)  -- Tuple associativity
A -> (B × C) ≅ (A -> B) × (A -> C)  -- Function distribution
(A × B) -> C ≅ A -> (B -> C)        -- Currying/uncurrying

"Isomorphic" means structurally the same from the perspective of the category.

Monomorphisms and Epimorphisms #

While isomorphisms represent "perfect reversibility", there are two other important classes of morphisms that capture one-sided notions of injectivity and surjectivity from the categorical perspective.

Monomorphism (Mono) #

A monomorphism is a morphism that is "left-cancellable" - it can be cancelled from the left side of a composition. Formally, a morphism m: A → B is a monomorphism if for any object X and any morphisms f, g: X → A:

m ∘ f = m ∘ g ⟹ f = g

Intuition: If two morphisms become equal after composing with m, they must have been equal to begin with. This means m doesn't "collapse" or "merge" distinct inputs.

In Set: Monomorphisms are exactly the one-to-one functions (injective) - no two distinct elements map to the same element.

Notation: Monomorphisms are often denoted with a hooked arrow: m: A ↪ B or simply A ↪ B.

Examples:

-- Injective function (monomorphism)
inj :: Int -> Int
inj x = x * 2  -- No two different inputs give the same output

-- Non-monomorphism
nonMono :: Int -> Bool
nonMono x = x > 0  -- Many inputs map to True, many to False

// Monomorphism: injective function
const inj = (x: number): number => x * 2;

// Not a monomorphism: multiple inputs map to same output
const nonMono = (x: number): boolean => x > 0;

Key Properties:

Every isomorphism is a monomorphism (but not vice versa)
The identity morphism id_A is always a monomorphism
The composition of monomorphisms is a monomorphism
In Set, monomorphisms correspond to subset inclusions (subobjects)

Epimorphism (Epi) #

An epimorphism is the opposite of a monomorphism - it is "right-cancellable". Formally, a morphism e: A → B is an epimorphism if for any object X and any morphisms f, g: B → X:

f ∘ e = g ∘ e ⟹ f = g

Intuition: If two morphisms become equal after composing with e from the right, they must have been equal to begin with. This means e is "comprehensive enough" that it doesn't miss any distinctions in the target object.

In Set: Epimorphisms are exactly the surjective (onto) functions - every element in the codomain is hit by some element from the domain.

Notation: Epimorphisms are often denoted with a double-headed arrow: e: A ↠ B or simply A ↠ B.

Examples:

Haskell

-- Surjective function (epimorphism)
epi :: Int -> Bool
epi x = x > 0  -- Covers all of Bool (both True and False)

-- Non-epimorphism
nonEpi :: Bool -> Int
nonEpi True = 1
nonEpi False = 0  -- Doesn't cover all integers

TypeScript

// Epimorphism: surjective function
const epi = (x: number): boolean => x > 0;

// Not an epimorphism: doesn't cover all numbers
const nonEpi = (b: boolean): number => b ? 1 : 0;

Key Properties:

Every isomorphism is an epimorphism (but not vice versa)
The identity morphism id_A is always an epimorphism
The composition of epimorphisms is an epimorphism
In Set, epimorphisms correspond to surjective functions

Split Monomorphisms and Split Epimorphisms #

A monomorphism m: A → B is split if it has a left inverse - i.e., there exists r: B → A such that r ∘ m = id_A. This means you can "retract" back to A after embedding via m.

Similarly, an epimorphism e: A → B is split if it has a right inverse - i.e., there exists s: B → A such that e ∘ s = id_B. This provides a "section" that picks out a canonical preimage for each element of B.

Important distinction:

In Set, split monomorphisms are injective (and come equipped with a left inverse)
In Set, split epimorphisms are surjective (surjections with a specified right inverse/section)
In general (and in Set without choosing sections), not every monomorphism/epimorphism splits — splitness is a stronger property

Relationship #

Isomorphism
    ↓
    ├─→ Monomorphism (left-cancellable, "injective")
    └─→ Epimorphism (right-cancellable, "surjective")

Isomorphism = Monomorphism + Epimorphism (with a two-sided inverse)
Monomorphism = One-sided "injectivity"
Epimorphism = One-sided "surjectivity"

In Set, we have the familiar:

Mono = Injective function
Epi = Surjective function
Iso = Bijective function (both injective and surjective)

In other categories, these relationships can be more subtle.

Monomorphisms and epimorphisms generalize the concepts of "one-to-one" and "onto" to arbitrary categories, allowing us to reason about injectivity and surjectivity without referring to elements.

Visualizing categories #

Objects: A, B
Morphisms: f: A -> B, g: B -> A, id: A -> A, id: B -> B

- Composition with identity:
  id_B ∘ f = f
  f ∘ id_A = f
  id_A ∘ g = g
  g ∘ id_B = g

- Opposite arrows compose to identities (isomorphism):
  g ∘ f = id_A
  f ∘ g = id_B

┌────┐           ┌────┐
│ A  │ ---f--->  │ B  │
│ ^  │ <---g---  │  ^ │
└-|-─┘           └──|─┘
  | id_A            | id_B
  '---'             '---'

Objects: A, B, C
Morphisms: f: A -> B, g: B -> C, h: A -> C, id: A -> A

- h = g ∘ f (composition of f and g).

A ---f---> B ---g---> C
 \                /
  \-----h--------/


- id a = a (identity)

┌─────┐
│     │
│     ▼
-----A


Isomorphism: f: A -> B with inverse g: B -> A

A ===f===> B
  <===g===

Where:
- g ∘ f = id_A (composition gives identity on A)
- f ∘ g = id_B (composition gives identity on B)
- A ≅ B (A and B are isomorphic)


Isomorphic objects in context:

    D
    │
    │h
    ▼
A ===f===> B ---k---> E
  <===g===

If A ≅ B via f,g then:
- Any morphism h: D -> A corresponds to h': D -> B where h' = f ∘ h
- Any morphism k: B -> E corresponds to k': A -> E where k' = k ∘ f
- Isomorphic objects have the "same shape" categorically


Monomorphism: m: A ↪ B (left-cancellable, "injective")

X ----f---->
            ╲
             ╲
X ----g----> A --m-↪-> B
              ╱
             ╱
X ----h---->

If m ∘ f = m ∘ g, then f = g
(m doesn't collapse distinct morphisms)


Epimorphism: e: A ↠ B (right-cancellable, "surjective")

         ----f----> X
        ╱
       ╱
A --e-↠-> B ----g----> X
              ╲
               ╲
                ----h----> X

If f ∘ e = g ∘ e, then f = g
(e is comprehensive - doesn't miss distinctions)


Relationship between Iso, Mono, and Epi:

      Isomorphism
      A ===f===> B
        <===g===
           │
           ├──────────────┐
           │              │
           ▼              ▼
    Monomorphism    Epimorphism
    A ---m-↪-> B    A ---e-↠-> B
    (injective)     (surjective)

Every isomorphism is both a monomorphism and an epimorphism.

Conclusion #

Categories provide a high-level way to reason about structures and transformations without worrying about implementation details. They emphasize composition, which is at the core of software development. Patterns based on categories enable reusable abstractions for computations.

Source code #

Reference implementation (opens in a new tab)

Notes

Note on totality: throughout the programming examples we model the category whose objects are types and whose morphisms are total functions (think Set). In real languages (e.g., Haskell with bottoms/partiality or exceptions), not every definable function is total. We idealize functions as total so the categorical laws (associativity and identity) hold straightforwardly. · Back
We only allow transformations that send a figure to one of the same shape‑kind (square→square, triangle→triangle). · Back

Enter Category #

Haskell perspective #

TypeScript perspective #

C# perspective #

Formal definition #

Two Key Rules #

Examples of Categories #

Homomorphism #

Isomorphism #

Key Properties #

Isomorphic Objects #

Monomorphisms and Epimorphisms #

Monomorphism (Mono) #

Epimorphism (Epi) #

Split Monomorphisms and Split Epimorphisms #

Relationship #

Visualizing categories #

Conclusion #

Source code #

Notes

References