Adjunction
Optimization/completion, automatic resource management
_ ____ _ _ _ _ _ ____ _____ ___ ___ _ _ ____
/ \ | _ \ | | | | | \ | |/ ___|_ _|_ _/ _ \| \ | / ___|
/ _ \ | | | |_ | | | | | \| | | | | | | | | | \| \___ \
/ ___ \| |_| | |_| | |_| | |\ | |___ | | | | |_| | |\ |___) |
/_/ \_\____/ \___/ \___/|_| \_|\____| |_| |___\___/|_| \_|____/
You've learned about functors mapping between categories and natural transformations relating functors that go in the same direction. But what happens when we have two functors going in opposite directions? How do we understand their relationship?
This is where adjunctions come into play. An adjunction captures the idea that two functors "fit together" in a particularly tight and natural way, like two pieces of a puzzle that lock perfectly into place.
One important family of adjunctions formalizes the pattern where one functor forgets structure while another freely adds it. Other adjunctions describe currying and universal approximations, and every adjunction induces a monad. Despite their variety, they share the same essential ingredient: a natural correspondence between morphisms in two categories.
Adjunction #
Natural transformations compare functors going in the same direction. An adjunction[2] instead relates a pair of functors going in opposite directions by making morphisms through one correspond naturally to morphisms through the other.
Suppose we have two categories, C and D, and two functors:
F: C -> D,
G: D -> C
An adjunction is described by two natural transformations:
- The unit:
η: IdC ⇒ G ∘ F, which means: for each objectAinC, we get a morphismη_A: A -> G(F(A)) - The counit:
ε: F ∘ G ⇒ IdD, which means: for each objectBinD, we get a morphismε_B: F(G(B)) -> B
These transformations cannot be arbitrary: the unit and counit must satisfy two triangle identities, which guarantee that the round trips behave like identities.
Starting with F(A) in D, applying F to the unit and then the counit is the same as doing nothing:
First Triangle Identity (for F):
F(η_A) ε_{F(A)}
F(A) ----------> F(G(F(A))) ----------> F(A)
\_____________________________________/
id_{F(A)}
Where: ε_{F(A)} ∘ F(η_A) = id_{F(A)}
Starting with G(B) in C, applying the unit and then G to the counit is also the same as doing nothing:
Second Triangle Identity (for G):
η_{G(B)} G(ε_B)
G(B) ----------> G(F(G(B))) ----------> G(B)
\_____________________________________/
id_{G(B)}
Where: G(ε_B) ∘ η_{G(B)} = id_{G(B)}
These conditions ensure that F and G are genuinely linked.
What do these transformations really mean?
In the free–forgetful adjunction discussed below, the right adjoint U forgets structure and the left adjoint F freely adds it. In a general adjunction, however, neither description need apply. Likewise, a unit or counit is simply a morphism of the stated type; it need not be an embedding or a surjection.
Bijection #
Adjunction can also be described in terms of the Hom-set. Because category theory describes objects through their morphisms, the appropriate relationship is a bijection between hom-sets.
A bijection[1], bijective function, or one-to-one correspondence is a function between two sets such that each element of the second set (the codomain) is the image of exactly one element of the first set (the domain). Equivalently, a bijection is a relation between two sets such that each element of either set is paired with exactly one element of the other set.
An adjunction F ⊣ G is defined by a natural bijection of Hom-sets:
Φ(A,B): Hom_D(F(A), B) ≅ Hom_C(A,G(B)), for every A in C, B in D.
This means that every morphism F(A) -> B in D corresponds uniquely to a morphism A -> G(B) in C, and vice versa.
This correspondence is natural in both A and B. That means:
Changing A by a morphism f: A' -> A in C, or B by a morphism g: B -> B' in D, preserves the correspondence. More precisely, the bijection is natural in A (contravariant) and B (covariant).
The bijection is functorial — it interacts correctly with morphisms on both sides.
From this Hom-set bijection, we can actually recover the unit and counit:
The unit η_A: A -> G(F(A)) comes from applying the bijection to the identity morphism id_F(A) ∈ Hom_D(F(A), F(A)).
The counit ε_B: F(G(B)) -> B comes from applying the inverse bijection to the identity morphism id_G(B) ∈ Hom_C(G(B), G(B)).
The Hom-set viewpoint and the unit/counit viewpoint are two equivalent ways of describing the same structure.
Forgetful Functor #
A forgetful functor[3] is a functor that "forgets" or discards some structure while preserving the underlying data. In our case:
U : Monoids -> Sets
The forgetful functor U takes a monoid and discards its identity and combination operations, leaving only the underlying set of values.
For example:
U(Integers under addition)= the set of integersU(Strings under concatenation)= the set of stringsU(Lists under concatenation)= the set of lists
The values remain; only the chosen algebraic operations are forgotten.
Free Functor #
The Free functor[4] goes in the opposite direction:
F : Sets -> Monoids
Given a set X, the functor F constructs the free monoid on X: the set of all finite lists of elements of X. The empty list is the identity and list concatenation is the monoid operation.
This construction adds only what the monoid laws require. It introduces no equations between generators beyond associativity and identity.
Adjunction Connection #
Left adjoint:
A left adjoint is a special relationship between functors. If F is left adjoint to U, written as F ⊣ U, it means:
Hom_Mon(F(X), M) ≅ Hom_Set(X, U(M))
In practical terms, this means:
- Every monoid homomorphism from the list monoid
F(X)to a monoidM - Corresponds exactly to a function from the generators
Xto the underlying setU(M)
Once the destination of each generator is chosen, the destination of every finite list is forced by the monoid operation.
Right adjoint:
A right adjoint is the same relationship viewed from U: a map into the underlying set U(M) determines a unique map from the freely generated object F(X) into M.
In practical terms, this means:
- Every function from a set
XtoU(M)(the "forgotten" version) - Corresponds exactly to a monoid homomorphism from
F(X)(the "freely generated" version) toM
In this example, U is the right adjoint: it forgets the monoid operations and retains the underlying set. Together the two functors form the adjunction F ⊣ U. For any set X and monoid M:
Hom_Mon(F(X), M) ≅ Hom_Set(X, U(M))
In concrete terms, every function that assigns a value in M to each element of X extends uniquely to a monoid homomorphism from lists of X into M.
This natural bijection is the precise sense in which freely adding and forgetting structure fit together.
Universal Property #
For any set X, monoid M, and function α : X -> U(M), there exists a unique monoid homomorphism φ : F(X) -> M such that the following diagram commutes:
α
X ----------> U(M)
\ ↑
η \ / U(φ)
v /
U(F(X))
In plain English: define where each generator goes, and there is exactly one operation-preserving way to interpret every list of generators in the target monoid.
Reflection #
Let F ⊣ U, where F: C -> D and U: D -> C. If the right adjoint U is full and faithful, it identifies D with a full subcategory of C. That subcategory is called reflective, and F is its reflector.
For every object X in C, the unit
η_X: X -> U(F(X))
is the reflection arrow. Its universal property says that any morphism from X to an object of the reflective subcategory factors uniquely through η_X. This makes F(X) the best approximation to X lying in D.
The unit is not generally an isomorphism. It is an isomorphism precisely when X is already, up to isomorphism, in the essential image of U. By contrast, because U is full and faithful, every component of the counit
ε_Y: F(U(Y)) -> Y
is an isomorphism for Y in D.
Imagine a collection containing documents in many formats, with standard-format documents forming the reflective subcategory. The reflector converts any document X into a standard-format document F(X), and the unit X -> U(F(X)) records that conversion. Any map from X to another standard-format document factors uniquely through this unit. If X already has the standard format, the conversion leaves it unchanged up to isomorphism.
Coreflection #
Coreflection is the dual situation. For the same adjunction F ⊣ U, suppose the left adjoint F is full and faithful. It then identifies C with a full coreflective subcategory of D, and U is the coreflector.
For every object Y in D, the counit
ε_Y: F(U(Y)) -> Y
is the coreflection arrow. Any morphism from an object of the coreflective subcategory to Y factors uniquely through ε_Y. Thus U(Y) is the best approximation to Y coming from C.
The counit is an isomorphism precisely when Y is already, up to isomorphism, in the essential image of F. Because F is full and faithful, every component of the unit
η_X: X -> U(F(X))
is an isomorphism for X in C.
Imagine a workshop with finished products and a distinguished class of standard products assembled from canonical kits. For any finished product Y, the coreflector extracts a canonical kit U(Y). Rebuilding that kit produces the standard product F(U(Y)), together with the counit F(U(Y)) -> Y showing how it maps into the original product. Any map from a standard product into Y factors uniquely through this counit. If Y was already a standard product, rebuilding recovers it unchanged up to isomorphism.
Reflection therefore approximates an ambient object by mapping into the reflective subcategory, while coreflection approximates it by mapping out of the coreflective subcategory.
Examples #
Free-Forgetful Adjunction:
For sets and monoids, finite lists provide the free construction. Given a set of generators X, F(X) is the monoid of lists [X]: [] is the identity and (++) is the operation. The forgetful functor U takes a monoid back to its underlying set.
The following example implements the unit, counit, and both directions of the Hom-set correspondence:
import Data.Monoid (Sum(..))
-- F(X): the free monoid generated by a type a.
type FreeMonoid a = [a]
-- F's action on morphisms: rename every generator.
freeMap :: (a -> b) -> FreeMonoid a -> FreeMonoid b
freeMap = map
-- η_X : X -> U(F(X))
-- Include one generator as a one-element word.
unit :: a -> FreeMonoid a
unit x = [x]
-- ε_M : F(U(M)) -> M
-- Evaluate a list of elements using M's monoid operations.
counit :: Monoid m => FreeMonoid m -> m
counit = mconcat
-- Haskell does not encode the homomorphism laws in this wrapper;
-- a MonoidHom value is expected to preserve mempty and (<>).
newtype MonoidHom a m = MonoidHom
{ applyHom :: a -> m
}
-- Hom_Mon(F(X), M) <- Hom_Set(X, U(M))
-- A function on generators extends to all finite words.
extend :: Monoid m => (a -> m) -> MonoidHom (FreeMonoid a) m
extend interpret = MonoidHom (counit . freeMap interpret)
-- Hom_Mon(F(X), M) -> Hom_Set(X, U(M))
-- A homomorphism is determined on generators by singleton words.
restrict :: MonoidHom (FreeMonoid a) m -> a -> m
restrict hom = applyHom hom . unit
data Symbol = A | B | Space
deriving (Eq, Show)
-- Choose where each generator goes in the additive monoid.
weight :: Symbol -> Sum Int
weight A = Sum 1
weight B = Sum 2
weight Space = Sum 0
-- The adjunction gives the unique homomorphism on words.
score :: MonoidHom (FreeMonoid Symbol) (Sum Int)
score = extend weight
word :: FreeMonoid Symbol
word = [A, B, B, A]
exampleScore :: Sum Int
exampleScore = applyHom score word
-- Sum 6
-- The same free monoid can be interpreted in another target monoid.
renderSymbol :: Symbol -> String
renderSymbol A = "a"
renderSymbol B = "b"
renderSymbol Space = " "
render :: MonoidHom (FreeMonoid Symbol) String
render = extend renderSymbol
exampleText :: String
exampleText = applyHom render [A, B, Space, B, A]
-- "ab ba"
-- The extension preserves the monoid structure.
preservesIdentity :: Bool
preservesIdentity = applyHom score [] == mempty
preservesComposition :: Bool
preservesComposition =
applyHom score ([A, B] <> [B, A])
== applyHom score [A, B] <> applyHom score [B, A]
-- Extending and then restricting recovers the original function.
roundTripOnGenerator :: Bool
roundTripOnGenerator = restrict (extend weight) B == weight B
The important step is extend. A function a -> m says only how to interpret individual generators. extend uses mempty for the empty list and (<>) for concatenation, so it determines an interpretation for every list. No other monoid homomorphism can make different choices: preservation of the identity fixes [], and preservation of the operation fixes every longer list from its singleton elements.
Mathematically, extend and restrict witness the bijection when MonoidHom ranges only over functions that preserve mempty and (<>):
Hom_Mon([a], m) ≅ Hom_Set(a, U(m))
The Haskell wrapper documents but does not enforce those laws. Consequently, restrict (extend f) agrees extensionally with f for every function f, while extend (restrict h) agrees extensionally with h only when h is a lawful monoid homomorphism.
Reader-Writer Adjunction #
For a fixed type r, pairing with r is left adjoint to reading from r. No Monoid r constraint is needed:
-- Product functor: pair a value with an r.
newtype Writer w a = Writer (w, a)
-- Exponential functor: read an r to produce a value.
newtype Reader r a = Reader (r -> a)
-- Writer r ⊣ Reader r
-- Hom(Writer r a, b) ≅ Hom(a, Reader r b)
-- Unit: a -> Reader r (Writer r a)
readerWriterUnit :: a -> Reader r (Writer r a)
readerWriterUnit a = Reader (\r -> Writer (r, a))
-- Counit: Writer r (Reader r a) -> a
readerWriterCounit :: Writer r (Reader r a) -> a
readerWriterCounit (Writer (r, Reader f)) = f r
-- Convert the left Hom-set to the right Hom-set.
leftAdjunct :: (Writer r a -> b) -> a -> Reader r b
leftAdjunct f a = Reader (\r -> f (Writer (r, a)))
-- Convert the right Hom-set back to the left Hom-set.
rightAdjunct :: (a -> Reader r b) -> Writer r a -> b
rightAdjunct f (Writer (r, a)) =
let Reader g = f a
in g r
format :: Writer String Int -> String
format (Writer (prefix, n)) = prefix ++ show n
formatted :: Int -> Reader String String
formatted = leftAdjunct format
exampleReaderWriter :: String
exampleReaderWriter =
let Reader run = formatted 42
in run "answer: "
-- "answer: 42"
State Adjunction #
The State monad is not another adjoint in a triple. Instead, it is induced by composing the right and left functors of the product–function adjunction Product s ⊣ Reader s:
newtype Product s a = Product (s, a)
newtype Reader s a = Reader (s -> a)
newtype State s a = State (s -> (a, s))
-- The induced monad is Reader s (Product s a):
--
-- s -> (s, a)
--
-- It is isomorphic to State s a after swapping the result pair.
toState :: Reader s (Product s a) -> State s a
toState (Reader f) = State $ \s ->
let Product (s', a) = f s
in (a, s')
fromState :: State s a -> Reader s (Product s a)
fromState (State f) = Reader $ \s ->
let (a, s') = f s
in Product (s', a)
-- Basic State operations
get :: State s s
get = State $ \s -> (s, s)
put :: s -> State s ()
put s = State $ \_ -> ((), s)
-- Functor instance for State
instance Functor (State s) where
fmap f (State g) = State $ \s -> let (a, s') = g s in (f a, s')
-- Applicative instance for State
instance Applicative (State s) where
pure a = State $ \s -> (a, s)
State f <*> State g = State $ \s ->
let (fab, s') = f s
(a, s'') = g s'
in (fab a, s'')
-- Monad instance for State
instance Monad (State s) where
State g >>= f = State $ \s ->
let (a, s') = g s
State h = f a
in h s'
-- Practical usage
counter :: State Int String
counter = do
n <- get
put (n + 1)
pure ("Count: " ++ show n)
Here Reader s (Product s a) is the composite G(F(a)) of the adjunction. Every adjunction produces a monad from this right-after-left composition; in this case, that monad is State, up to the order of the pair.
Product-Exponential Adjunction #
The Reader–Writer example is the product–exponential adjunction specialized to Haskell types. With a fixed, (a, -) is left adjoint to (a -> -):
-- Product functor: (a, -)
-- Exponential functor: (a -> -)
-- Hom-set bijection: ((a, b) -> c) ≅ (b -> a -> c)
-- Left side: function from pair
pairFunc :: (String, Int) -> Bool
pairFunc (str, n) = length str > n
-- Right side: transpose with the fixed String argument second
curriedFunc :: Int -> String -> Bool
curriedFunc n str = length str > n
productToExponential :: ((a, b) -> c) -> b -> a -> c
productToExponential f b a = f (a, b)
exponentialToProduct :: (b -> a -> c) -> (a, b) -> c
exponentialToProduct f (a, b) = f b a
-- Unit: b -> (a -> (a, b))
pairUnit :: b -> (a -> (a, b))
pairUnit b = \a -> (a, b)
-- Counit: (a, (a -> b)) -> b
pairCounit :: (a, (a -> b)) -> b
pairCounit (a, f) = f a
Ordinary curry uses the order a -> b -> c; the equivalent form above keeps the first product component fixed so that the functor orientation remains explicit.
Visualizing adjunctions #
1. Unit arrow
A -- η_A --> G(F(A))
2. Counit arrow
F(G(B)) -- ε_B --> B
3. Free-Forgetful Adjunction
FORGETFUL FUNCTOR FREE FUNCTOR
───────────────── ────────────
Strip Away Structure Add Minimal Structure
┌─────────────┐ ┌─────────────┐
│ Monoid M │ -- forget --> │ Set │
│ identity: e │ U │ U(M) │
│ combine: · │ │ │
└─────────────┘ └─────────────┘
┌─────────────┐ ┌─────────────┐
│ Set X │ ---- free --> │ List monoid │
│ │ F │ F(X) │
└─────────────┘ └─────────────┘
U : Monoids → Sets F : Sets → Monoids
F ⊣ U (F is left adjoint to U)
Natural Transformations:
η : Id → U ∘ F (unit)
ε : F ∘ U → Id (counit)
Correspondence Diagram
Sets <------------- Monoids
U (Forgetful)
Sets --------------> Monoids
F (Free, Left Adjoint)
4. First Triangle Identity (for F)
F(A)
| \
| \
F(η_A) | \ id
| \
v v
F(G(F(A))) --ε_{F(A)}--> F(A)
ε_{F(A)} ∘ F(η_A) = id_{F(A)}
5. Second Triangle Identity (for G)
η_{G(B)} G(ε_B)
G(B) ----------> G(F(G(B))) ----------> G(B)
\_____________________________________/
id_{G(B)}
G(ε_B) ∘ η_{G(B)} = id_{G(B)}
Conclusion #
An adjunction describes two functors that translate between categories in opposite directions while preserving a natural correspondence between morphisms. It can be presented either as a Hom-set bijection or through a unit and counit satisfying the triangle identities. These are two views of the same structure.
The free-monoid example captures the central pattern. The left adjoint turns a set of generators into lists, adding exactly the structure required by the monoid laws. The right adjoint forgets those operations and returns to the underlying set. A function defined only on generators then extends uniquely to a monoid homomorphism, which is the universal property behind the construction.
Adjunctions are broader than free and forgetful functors. Currying and the product–function relationship exhibit the same kind of correspondence, and their composite induces the State monad. When one of the adjoints is full and faithful, reflection or coreflection identifies a full subcategory and supplies universal approximations to its objects.
The practical signal to look for is uniqueness: when a construction offers the most general object, the best approximation, or a unique structure-preserving extension, an adjunction is often organizing the relationship.
Source code #
Reference implementation (opens in a new tab)