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. For monoids and monads it works the laws out on real values, with figures you can drive yourself. 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. Associativity is exactly what makes it safe to split a fold up and parallelize it
• A monad is a functor plus join (flattening), and bind (>>=, flatMap) is nothing more than a name for “fmap, then join”
• The three monad laws say that composition via bind satisfies associativity and the identity law, which is why they look so much like the monoid laws. Indeed, “a monad is a monoid in the category of endofunctors” is a precise restatement
• Associativity for the IO monad shows up as an everyday guarantee: pulling part of a do block out into a function changes neither the order of the effects nor the result
• A natural transformation is a conversion “definable the same way for every type, with no per-object ingenuity”, and both return and join are natural transformations
• 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
• The code is written in Haskell notation, but reading >>= as flatMap carries it over to Scala or Java unchanged

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.

Note that associativity is the law that permits re-bracketing, not the law that permits reordering. Reordering is permitted by commutativity, a separate law that neither category theory nor the monoids below demand. Remembering that function composition and string concatenation both depend on order makes the distinction easy to keep.

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.

In programming, a functor is a type constructor — something that takes a type and returns a type, like Maybe or [] — that also has map. Since the category it maps into is again the category of types and functions, it is strictly speaking a functor from a category to itself: an endofunctor. That “endo” is what makes it possible to build a monad out of one later.

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.

Drawn out it is a square, and the requirement is that both ways round give the same answer.

flowchart LR
  FA["F(A)"] -- "F(f)" --> FB["F(B)"]
  FA -- "η_A" --> GA["G(A)"]
  GA -- "G(f)" --> GB["G(B)"]
  FB -- "η_B" --> GB

Translated into programming, $F$ and $G$ are type constructors like Maybe and [], $F(f)$ and $G(f)$ are their respective fmaps, and $\eta$ is a conversion function across type constructors. So a natural transformation is a conversion function eta for which the following holds.

1
2

-- these two are equal whichever f you pick
fmap f . eta  ==  eta . fmap f

Here are the standard examples.

What they share is that none of them ever looks at the value inside. The only information they use is the shape of the container: Just or Nothing, empty or non-empty, which position. Because the contained type is irrelevant, the same code works for all of them. Conversely, a conversion that peeks inside is not a natural transformation.

1
2
3
4

-- not a natural transformation: it decides the length from the value x
unnatural :: Maybe Int -> [Int]
unnatural (Just x) = replicate x x
unnatural Nothing  = []

Feed unnatural with f = (+1) and Just 3: converting after fmap f gives [4, 4, 4, 4], while converting first and then applying fmap f gives [4, 4, 4]. The square does not close. The figure below lets you check this yourself.

Being able to write a Haskell type as forall a. Maybe a -> [a], with the type variable left free, means the code cannot touch the contents of a. Because it cannot touch them, it has to behave uniformly, and that is why a total function of this shape in Haskell is generally a natural transformation automatically. The property is called parametricity, and the resulting statements are known as free theorems; there are exceptions once undefined or seq come into play, but as a working intuition, “if it can be written polymorphically, it is natural” holds up.

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 programming counterpart of “choosing a basis” is close to “pinning the contained type down to Int”. unnatural above could only be written for Int precisely because it chose a basis.

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

Definition

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. Put the other way round, a monoid is “the laws of a category, viewed with all the objects collapsed into one”. That is the root of why the monad laws below come out in the same shape as the laws of a category.

Checking the Laws on Real Values

In programming, monoids show up everywhere.

Whether the laws hold is quicker to see by putting real values in than by staring at the abstract statement. Taking addition as the example:

1
2
3
4
5

associativity: (3 + 5) + 8 = 8 + 8 = 16
               3 + (5 + 8) = 3 + 13 = 16   -> equal

identity law:  0 + 3 = 3
               3 + 0 = 3                   -> both equal a

Meanwhile, plenty of operations “combine two things into one” without being monoids. Subtraction and the average make the point clearly.

1
2
3
4
5
6
7
8

associativity of subtraction: (3 - 5) - 8 = -10
                              3 - (5 - 8) = 6       -> not equal
identity law for subtraction: 3 - 0 = 3             -> holds on the right
                              0 - 3 = -3            -> fails on the left

associativity of average: avg(avg(3, 5), 8) = avg(4, 8)   = 6
                          avg(3, avg(5, 8)) = avg(3, 6.5) = 4.75  -> not equal
identity for average:     no such value exists

The figure below evaluates associativity and the identity law on the values shown. It also folds the same four values two ways — left to right, and in halves — filling in a round at a time, so you can watch the parallel shape finish a round earlier and then see what breaking associativity actually costs.

Associativity Is What Permits Parallelism

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. Written as Mermaid, the straightforward sequential fold looks like this.

flowchart TD
  L3["((a⊕b)⊕c)⊕d"] --> L2["(a⊕b)⊕c"]
  L3 --> Ld["d"]
  L2 --> L1["a⊕b"]
  L2 --> Lc["c"]
  L1 --> La["a"]
  L1 --> Lb["b"]

Folding in halves instead halves the depth of the tree, and the two sides can go to separate threads or separate nodes.

flowchart TD
  R2["(a⊕b)⊕(c⊕d)"] --> R0["a⊕b"]
  R2 --> R1["c⊕d"]
  R0 --> Ra["a"]
  R0 --> Rb["b"]
  R1 --> Rc["c"]
  R1 --> Rd["d"]

What guarantees that these two trees produce the same value is associativity. Log aggregation and event aggregation can be distributed MapReduce-style precisely because the aggregating function is a monoid. The identity element earns its keep as the value to return when a split comes out empty.

In Haskell you can define it as follows.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Semigroup m where
  (<>) :: m -> m -> m        -- requires associativity only

class Semigroup m => Monoid m where
  mempty :: m                -- adding an identity makes it a monoid

instance Semigroup [a] where
  (<>) = (++)

instance Monoid [a] where
  mempty = []

A structure that satisfies associativity alone is a semigroup; adding an identity element turns it into a monoid. Parallelization only needs associativity, so a semigroup is enough to split the work. The identity is what you need in order to decide what an empty input returns.

Monads

Chaining Values With Context

The monad story starts by reading Maybe Int as “an Int that may fail”, [Int] as “an Int with several candidates”, and IO Int as “a procedure that yields an Int when run”. None of them is a bare value; each is a value with some context attached.

The awkward moment comes when you want to chain functions that return such values. Suppose you want to apply these two in order.

1
2
3
4
5
6

half :: Int -> Maybe Int
half n = if even n then Just (n `div` 2) else Nothing

recip100 :: Int -> Maybe Int
recip100 0 = Nothing
recip100 n = Just (100 `div` n)

half returns Maybe Int while recip100 takes an Int. The types don’t line up, so recip100 . half is not an option.

Why map Alone Is Not Enough

Maybe is a functor, so fmap is available. But applying fmap recip100 to a Maybe Int gives back a Maybe (Maybe Int).

1

fmap half (Just 40)            -- Just (Just 20)      :: Maybe (Maybe Int)

To go one step further you have to lift recip100 through yet another fmap.

1
2

fmap (fmap recip100) (Just (Just 20))
-- Just (Just (Just 5))  :: Maybe (Maybe (Maybe Int))

Every additional step piles on another fmap, and the type puts on another layer of Maybe. That is unusable. What you need is an operation that strips the extra Maybe back off each time. That operation is join (flatten), and a functor equipped with join is a monad.

1
2
3

join :: Maybe (Maybe a) -> Maybe a
join (Just m) = m
join Nothing  = Nothing

The figure below puts “chained with fmap alone” on top and “chained with bind” underneath. They advance a step at a time, together, so you can watch the top row gain a layer at each step while the bottom row does not. Change the input and the type on the bottom row still never moves, whichever step fails.

How bind, flatMap, and join Relate

bind (>>=) is nothing more than “fmap, then join” rolled into one operation.

Conversely join can be built from bind (join m = m >>= id), so either one can be taken as primitive. Drawn out, it is the same triangle as the composition diagram at the very start of the article.

flowchart LR
  M["m :: M a"] -- "fmap f" --> MM["M (M b)"]
  MM -- "join" --> R["M b"]
  M -- "m >>= f" --> R

And flatMap is simply another name for bind. Only the name differs between languages; the job is the same “map, then collapse one level”.

The name flatMap spells the procedure out: map, then flatten. Since flatten is join, the correspondence is flatMap = map + flatten = fmap + join = bind. JavaScript’s [1,2].flatMap(x => [x, x*10]) returns [1, 10, 2, 20] because the result of map, [[1,10],[2,20]], is collapsed one level by concat.

The Pieces of a Monad, and Its Laws

Putting that together, a monad 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.

Why the same shape as the monoid laws? Because if you regard Kleisli morphisms (functions of the form $a \to M\,b$) as the morphisms, bind becomes their composition and return becomes their identity. Kleisli composition can be written out directly.

1
2

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

Take >=> as composition and return as the identity morphism, and the three monad laws become the laws of a category verbatim.

1
2
3

return >=> f  ==  f          -- left identity
f >=> return  ==  f          -- right identity
(f >=> g) >=> h  ==  f >=> (g >=> h)   -- associativity

This category is called 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.”

Working the Laws Out for Maybe

Abstract formulas are hard to internalize, so here they are expanded on the half and recip100 above.

First, left identity. return 40 is Just 40, so:

1
2
3
4
5

return 40 >>= half
  = Just 40 >>= half
  = half 40                -- Just x >>= f collapses to f x
  = Just 20
right-hand side: half 40 = Just 20     -> equal

Next, right identity.

1
2
3
4

Just 20 >>= return
  = return 20
  = Just 20
right-hand side: m = Just 20           -> equal

Finally associativity, on both a succeeding and a failing path.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

succeeding path (m = Just 40)
  (Just 40 >>= half) >>= recip100
    = Just 20 >>= recip100 = Just 5
  Just 40 >>= (\x -> half x >>= recip100)
    = half 40 >>= recip100 = Just 20 >>= recip100 = Just 5   -> equal

failing path (m = Just 7; half fails on an odd number)
  (Just 7 >>= half) >>= recip100
    = Nothing >>= recip100 = Nothing
  Just 7 >>= (\x -> half x >>= recip100)
    = half 7 >>= recip100 = Nothing >>= recip100 = Nothing   -> equal

For Maybe, this is what the three laws are saying.

• Left identity: wrapping in Just and immediately unwrapping is the same as doing nothing
• Right identity: appending a return to the end of the pipeline doesn’t change the result
• Associativity: it makes no difference where the short-circuit checks are grouped; the place it stops is the same

In practice, associativity is the guarantee that “you may extract two of the steps into a helper function”. Building halfThenRecip = half >=> recip100 and writing m >>= halfThenRecip behaves exactly as the original code did.

The Laws for the IO Monad

IO is the one people suspect of breaking the laws, on the grounds that it has side effects. It doesn’t, and the key is how to read IO a.

IO a is a description of a procedure that yields an a when run — not the running itself. So two values of type IO a are equal when “running them produces the same sequence of effects and the same result”. Check the three laws against that standard.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

step :: String -> Int -> IO Int
step tag v = do
  putStr tag
  pure v

m :: IO Int
m = step "A" 1

f, g :: Int -> IO Int
f x = step "B" (x + 1)
g x = step "C" (x * 10)

Expanding the three laws on this m, f, and g:

1
2
3
4
5
6

left identity:  pure 1 >>= f   -> output "B",   result 2
                f 1            -> output "B",   result 2      -> equal
right identity: m >>= pure     -> output "A",   result 1
                m              -> output "A",   result 1      -> equal
associativity:  (m >>= f) >>= g              -> output "ABC", result 20
                m >>= (\x -> f x >>= g)      -> output "ABC", result 20   -> equal

For IO, each law carries a concrete meaning.

• Left identity: pure performs no effect at all, which is why x <- pure v is the same as let x = v
• Right identity: appending a pure to the end of a procedure adds neither an effect nor a result
• Associativity: re-dividing the procedure changes neither the order of the effects nor the result

That third one gets used every time you refactor a do block. do notation is sugar over >>=: do { x <- m; rest } expands to m >>= \x -> do { rest }. So the rewrite below is associativity.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

-- before extracting
main :: IO ()
main = do
  cfg  <- loadConfig "app.yaml"
  conn <- connect cfg
  rows <- query conn "select ..."
  print rows

-- after extracting the first two lines into a function
setup :: IO Connection
setup = do
  cfg <- loadConfig "app.yaml"
  connect cfg

main :: IO ()
main = do
  conn <- setup
  rows <- query conn "select ..."
  print rows

“Pulling a few lines out into a function changes neither the order the logs come out in nor the order the queries hit the database” looks too obvious to state, and it is guaranteed precisely because associativity holds. Write a bind of your own that breaks associativity and that obvious thing stops being true.

What flatMap does for IO reads off the same way. readFile "a.txt" >>= writeFile "b.txt" builds a description that chains “the procedure that reads a file” onto “the procedure that writes what was read”; writing the expression has not made anything happen yet. The contrast with map (fmap) is the same as before: handing fmap a function that returns IO produces IO (IO a), a procedure that returns a procedure. join is what collapses that into a single procedure that runs the outer one and then runs whatever procedure came out.

The Laws for Other Monads

Here is what return and bind do for the main monads, and what the laws are claiming in each case.

Two rows stand out: [] and Writer. In both, the reason associativity holds is the associativity of a monoid.

join for the list monad is concat, that is foldr (++) [] — a fold over the list-concatenation monoid. Because the flattening is itself a monoid fold, the monad law follows from the monoid law.

Writer is even more direct: a Monoid constraint appears in the definition.

1
2
3
4
5
6

newtype Writer w a = Writer (a, w)

instance Monoid w => Monad (Writer w) where
  return x                = Writer (x, mempty)
  Writer (a, w) >>= f     = let Writer (b, w') = f a
                            in  Writer (b, w <> w')

return sets the log to mempty (the monoid identity) and bind joins logs with <> (the monoid operation). So the proof of the monad laws is the proof of the monoid laws for the log.

• Left identity comes from mempty <> w = w
• Right identity comes from w <> mempty = w
• Associativity comes from (w1 <> w2) <> w3 = w1 <> (w2 <> w3)

Writer is where “understand a monoid first, then add bind and you get a monad” is visible in its clearest form.

Everything above can be checked in the figure below, which evaluates both sides of the three laws on the same m, f, and g for whichever monad you pick. IO is modelled as a function returning (list of effects, value) when run.

When the Laws Break

Types lining up is no guarantee the laws hold. The “step counter” in the figure is an implementation that adds 1 to the step count on every bind.

1
2
3
4
5

newtype Counted a = Counted (a, Int)   -- (value, number of binds)

-- return is free; bind charges one step
returnC x                = Counted (x, 0)
Counted (a, n) `bindC` f = let Counted (b, m) = f a in Counted (b, n + m + 1)

The types line up perfectly and both map and flatMap can be written, yet m >>= return has one more step than m, so right identity breaks — and left identity with it. Only associativity survives, and only by accident: either bracketing binds twice.

The real-world example usually cited is JavaScript’s Promise. then looks like flatMap, but because Promise.resolve recursively flattens thenables, a value of type Promise<Promise<T>> cannot be constructed. So when a is itself a promise, Promise.resolve(a).then(f) hands f the resolved value of a rather than a itself, and disagrees with f(a). Left identity fails, which is why Promise is usually described as not strictly a monad. It rarely causes trouble in practice, but it is worth remembering that “having an API that looks like flatMap” and “satisfying the monad laws” are different things.

How Monoids and Monads Connect

The claim that “the monad laws have the same shape as the monoid laws” is not a metaphor. Rewrite join and return as natural transformations and the correspondence becomes exact.

Here is the other standard definition of a monad. A monad is a triple $(T, \eta, \mu)$ of an endofunctor $T$ and two natural transformations,

such that the following two diagrams commute.

Drawing the associativity one out, the claim is that collapsing a three-deep stack of T from either end gives the same thing.

flowchart LR
  T3["T∘T∘T"] -- "μT (collapse from outside)" --> T2a["T∘T"]
  T3 -- "Tμ (collapse from inside)" --> T2b["T∘T"]
  T2a -- "μ" --> T["T"]
  T2b -- "μ" --> T

In Haskell the three lines correspond directly.

1
2
3

join . fmap join   ==  join . join     -- associativity
join . fmap return ==  id              -- identity (right)
join . return      ==  id              -- identity (left)

Lined up against monoids, the correspondence is this table.

The only thing that changes is what plays the role of the “product”: the cartesian product of sets for monoids, composition of functors for monads. The laws demanded are the same shape throughout. The well-known phrase “a monad is a monoid in the category of endofunctors” is this table compressed into one sentence.

Naturality matters here too. Both return :: a -> m a and join :: m (m a) -> m a are polymorphic in a and are written without looking at the contained value. If join were allowed to behave differently per contained type, its interchange with fmap would not be guaranteed and the laws could not be argued across types at all. The naturality condition is what makes the monoid-object argument work.

To summarize, the order goes like this.

1. A monoid is a structure with an associative operation and an identity, which makes a fold safe to split
2. Adding join (flattening) to a functor lets you build bind out of it together with fmap
3. A monad is one where composition via that bind satisfies associativity and the identity law — the same shape of law as a monoid
4. That coincidence can be restated as an exact correspondence by viewing join and return as natural transformations

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.

1
2

calc :: Int -> Int -> Maybe Int
calc a b = half a >>= \r -> recip100 (r + b)

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. 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
• If you write your own Monad instance, don’t settle for the types compiling — check the three laws on concrete values. There is tooling for exactly this: QuickCheck in Haskell, MonadLaws in Cats for Scala
• 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
• Wadler, P. “Theorems for free!”. 1989
• Haskell Wiki. “Typeclassopedia”
• Haskell Wiki. “Monad laws”