Functional Languages and Category Theory

When learning a functional language you inevitably run into words like monad, functor, and monoid. Trace their etymology and most of them lead back to category theory, a branch of mathematics. You can write functional code without knowing category theory itself, but knowing where the terminology comes from and which laws must hold lets you derive a library’s API rather than memorize it.

This article organizes the basic elements of category theory systematically, then summarizes which category-theoretic concept each characteristic of functional languages corresponds to. Finally, it looks at how design changes when you think about algorithms functionally.

Conclusions

• A category is a collection of objects and morphisms in which composition of morphisms satisfies associativity and the identity law
• The types of a functional language roughly correspond to the objects of a category, and functions roughly to its morphisms. Thanks to this correspondence, properties of function composition can be discussed as laws of category theory
• A functor is a structure-preserving map from a category to a category; in programming it appears as a type that has map
• A monoid is an algebraic structure with an “associative binary operation” and an “identity element”; list concatenation and numeric addition are all concrete examples of monoids
• A monad is a functor plus flatten (a composable bind) — a framework for handling “computations with context” such as failure, asynchrony, and state in the form of function composition
• When you think about algorithms functionally, loops often become folds, sequential processing becomes function composition, and exception handling becomes propagation via monads

Prerequisites

• Intended reader: someone who has encountered the words monad and functor in Haskell, Scala, or a library like TypeScript’s fp-ts
• Assumed knowledge: a basic intuition for sets and functions. No specialist knowledge of category theory or abstract algebra is assumed
• Aim: not to rigorously prove the axioms of category theory, but to be able to explain the design decisions of functional languages in the language of category theory

Foundations of Category Theory

Categories, Objects, Morphisms

A category consists of the following elements.

• A collection of objects. Here we write them as $A, B, C$
• A collection of morphisms (arrows). A morphism from object $A$ to object $B$ is written $f: A \to B$
• Composition of morphisms. Given $f: A \to B$ and $g: B \to C$, the composite $g \circ f: A \to C$ is defined
• An identity morphism $\mathrm{id}_A: A \to A$ for each object $A$

Looking only at objects and morphisms, this closely resembles sets and functions, but category theory doesn’t ask about the “contents” of an object. An object may be a set, a type, or a state of a state machine. What matters is the structure itself: how morphisms can be composed.

flowchart LR
  A((A)) -- f --> B((B))
  B -- g --> C((C))
  A -- "g∘f" --> C

Kinds of Morphisms (Monomorphisms, Epimorphisms, Isomorphisms)

Some people, hearing “morphism,” will think of injections, surjections, and bijections. But those are properties of functions in the category of sets (Set), at a different level of abstraction from “morphism” in general category theory.

Category theory doesn’t look inside objects. From composition of morphisms alone, concepts corresponding to injective, surjective, and bijective can be defined. They are called the following.

• Monomorphism: $f: A \to B$ is called a monomorphism when, for any $g, h: X \to A$, $f \circ g = f \circ h$ implies $g = h$. In Set this corresponds to being injective
• Epimorphism: $f: A \to B$ is called an epimorphism when, for any $g, h: B \to X$, $g \circ f = h \circ f$ implies $g = h$. In Set this corresponds to being surjective
• Isomorphism: $f: A \to B$ is called an isomorphism when there exists $g: B \to A$ satisfying $g \circ f = \mathrm{id}_A$ and $f \circ g = \mathrm{id}_B$. In Set this corresponds to being bijective

Monomorphisms, epimorphisms, and isomorphisms are all defined without looking at the objects themselves — only through composition of morphisms and equality. When this article simply writes “morphism,” it does not restrict to properties like being monic. It’s used as a word for correspondences between objects in general. The explanations of functors and natural transformations are likewise not restricted to monomorphisms, epimorphisms, or isomorphisms.

Laws of Composition: Associativity and the Identity Law

To be a category, composition of morphisms must satisfy the following two laws.

Associativity is the law that changing the order of composition doesn’t change the result.

The identity law is the law that composing with an identity morphism changes nothing.

Requiring only these two is what sets category theory’s level of abstraction. The category of sets and functions (Set), of course, but also the category of types and functions, or a category of state transitions, can all be handled with the same toolkit as “categories” as long as they satisfy these two laws.

Functors

A functor is a “structure-preserving map” from one category $\mathcal{C}$ to another category $\mathcal{D}$. It maps objects to objects and morphisms to morphisms, and must satisfy the following two laws.

In other words, a functor is a map with the property that “mapping before composing and mapping after composing give the same result.” Thanks to this property, you can trust the behavior of composition on the far side of a functor too.

Natural Transformations

A natural transformation is a transformation between two functors $F, G: \mathcal{C} \to \mathcal{D}$: a collection of morphisms $\eta_A: F(A) \to G(A)$ that stay coherent whichever object $A$ of $\mathcal{C}$ you pick. For any morphism $f: A \to B$, the following diagram is required to commute.

Natural transformations tend to feel highly abstract to beginners, but in programming they appear as “uniform, implementation-independent functions that convert one type into another.” For example, Maybe a -> [a] (a function that turns a value into a single-element list if present, and into an empty list otherwise) is one instance of a natural transformation.

Why Call It “Natural”?

The name “natural transformation” carries the meaning that it “can be defined uniformly, the same way, without per-object ingenuity.” Historically, Eilenberg and Mac Lane introduced the term in a 1945 paper. They used the word for correspondences determined without relying on a basis.

For instance, consider a vector space $V$, its dual space $V^*$, and its double dual $V^{**}$.

An isomorphism from V to V^* does exist, but you have to choose a basis. The map from V to V^{**}, by contrast, can be defined without choosing a basis, and the diagram commutes for linear maps as well. Being definable without choosing a basis is where the name “natural transformation” comes from.

The Relationship Between Functional Languages and Category Theory

The Category of Types and Functions

The type system of a functional language can roughly be translated into the language of category theory as follows.

In Haskell, this “category with types as objects and functions as morphisms” is sometimes called Hask. What matters here is that the holding of associativity and the identity law for function composition is directly reflected in the design of Haskell’s . (the composition operator) and id themselves.

Pure Functions and Referential Transparency

To implement, as functions, the properties that morphisms of a category must satisfy, the following properties are indispensable.

• Pure function: always returns the same output for the same input, and has no side effects
• Referential transparency: replacing an expression with the result of evaluating it doesn’t change the meaning of the program as a whole

If you try to treat a function with side effects as a morphism of a category, the result of composition varies with execution order and external state, and associativity and the identity law stop holding. A functional language’s emphasis on pure functions isn’t mere preference — it’s a precondition for making function composition a mathematically trustworthy operation.

Monoids

A monoid is an algebraic structure consisting of the following.

• A set $M$
• A binary operation $\oplus: M \times M \to M$
• An identity element $e \in M$

The laws it must satisfy are these two.

This can also be seen as a category with just one object. Composition of morphisms corresponds to the binary operation, and the identity morphism to the identity element.

In programming, monoids show up everywhere.

In Haskell you can define it as follows.

1
2
3
4
5
6
7

class Monoid m where
  mempty  :: m
  mappend :: m -> m -> m

instance Monoid [a] where
  mempty  = []
  mappend = (++)

The advantage of a monoid is that you can aggregate in parallel regardless of how the elements are arranged. Because associativity is guaranteed, splitting or parallelizing the evaluation order of a fold doesn’t change the result. It’s thanks to this law that log aggregation and event aggregation can be designed to parallelize easily.

Monads

A monad is a functor (a type on which map works) plus an operation that flattens nested context. It consists of the following three elements.

• A type constructor $M$ (Maybe, Either e, [], IO, etc.)
• return (pure): $a \to M\,a$
• bind (>>=): $M\,a \to (a \to M\,b) \to M\,b$

The laws it must satisfy are the following three, which have the same shape as the monoid laws.

In fact, a monad can be organized as a category with “types as objects and Kleisli morphisms (functions of the form $a \to M\,b$) as morphisms.” In this view, return is the identity morphism, and composition using bind is composition of morphisms in the Kleisli category. It’s no coincidence that the monad laws look the same as the monoid laws: a monad is precisely “the laws of a category that the identity and composition in the Kleisli category must satisfy.”

As a concrete example, representing a computation that may fail with Maybe lets you write error propagation as function composition, as follows.

1
2
3
4
5
6
7
8

safeDivide :: Int -> Int -> Maybe Int
safeDivide _ 0 = Nothing
safeDivide x y = Just (x `div` y)

calc :: Int -> Int -> Int -> Maybe Int
calc a b c =
  safeDivide a b >>= \r1 ->
  safeDivide r1 c

The moment a Nothing appears mid-way, all subsequent computation short-circuits as Nothing. Rather than writing out if err != nil { return err } after each step, think of bind as handling that branching for you all at once.

What Changes When You Think About Algorithms Functionally

Building on the above, here’s what changes when you rethink an algorithm written imperatively in functional terms.

1. Loops Become Folds

In imperative code you often compute a sum or maximum with a for loop and a mutable accumulator, but in functional code you express it as a fold over a list.

1
2

sumList :: [Int] -> Int
sumList = foldr (+) 0

(+) and 0 are exactly the operation and identity of the monoid described above. If what you’re folding over is a monoid, you can safely split and parallelize the computation.

2. Sequential Processing Becomes Function Composition and Pipelines

Processing that applies several steps in order can be written as function composition rather than a sequence of assignments and temporary variables.

1
2

process :: String -> String
process = normalize . validate . parse

As long as each function is pure, you don’t have to worry about the implementation or execution order of other steps when swapping out or testing an intermediate step. That’s because associativity of composition is guaranteed.

3. Divide and Conquer Meshes Naturally with Immutable Data

In divide and conquer, you split the input into subproblems, solve each recursively, and combine them. In functional languages data is often immutable, so there’s no worry about subproblems rewriting each other’s state. Algorithms that “split, solve recursively, and combine,” like merge sort, are a good fit with this immutability.

1
2
3
4
5
6

mergeSort :: Ord a => [a] -> [a]
mergeSort []  = []
mergeSort [x] = [x]
mergeSort xs  = merge (mergeSort left) (mergeSort right)
  where
    (left, right) = splitAt (length xs `div` 2) xs

4. Exception Handling Becomes Propagation via Monads

Imperative code often handles the exceptional path by throwing exceptions or checking error return values, but in functional code, putting it on a monad like Maybe or Either lets you separate the happy-path logic from error propagation. Each function expresses in its type only that it “might fail,” and leaves the propagation mechanism itself to bind. Thanks to this separation, the algorithm’s own code can concentrate on “what to compute” rather than “how to report the failures that might occur.”

Caveats

• Not every concept of category theory is directly useful in practice. Laws like the monad laws are useful mainly as criteria for judging the reliability of a library’s implementation
• In languages with lazy evaluation or side effects (including Haskell’s IO), gaps can arise between category theory’s ideal model and actual execution order and performance characteristics. It’s better to keep theory and implementation separate in your thinking
• A monad is a “mechanism for chaining computations with context,” and it doesn’t always reduce complexity. Forcing a monad onto simple processing can sometimes make it harder to read instead
• Whether to introduce category theory terminology is best judged against your team’s background knowledge. You can explain how to use map and flatMap without the terminology

References

• Mac Lane, S. “Categories for the Working Mathematician”. Springer, 1971
• Bartosz Milewski. “Category Theory for Programmers”. 2018
• Wadler, P. “Monads for functional programming”. 1995
• Haskell Wiki. “Typeclassopedia”