"All concepts are Kan extensions" (Mac Lane). Given functors K : I → A and D : I → C, the right Kan extension RanKD : A → C is the best approximation of D along K. It answers: how do you extend a functor defined on a subcategory to the whole category? Limits, colimits, and adjunctions are all special cases.
The problem: extending a functor
You have a functor D : I → C that maps a small category I into C. You also have a functor K : I → A that embeds I into a larger category A. You want to extend D to all of A, not just the image of K. The Kan extension is the universal solution: the best functor A → C that approximates D, given K.
Scheme
; Setup: I is a small subcategory, A is the full category.; K embeds I into A. D maps I into values (our target).; Goal: extend D to all of A, not just where K lands.;; Concrete example:; I = {mon, tue} (two days we have data for); A = {mon, tue, wed, thu, fri} (full work week); K embeds mon->mon, tue->tue; D maps mon->10, tue->20 (sales on those days);; Right Kan extension: conservative estimate for wed, thu, fri.; Left Kan extension: liberal estimate.
(define I '(mon tue))
(define A '(mon tue wed thu fri))
; D: the functor we know (defined on I)
(define (D day)
(cond ((eq? day 'mon) 10)
((eq? day 'tue) 20)
(else (begin (display "ERROR: D is only defined on I") (newline)))))
; K: the embedding I -> A (identity on the subcategory)
(define (K day) day)
(display "D(mon) = ") (display (D 'mon)) (newline)
(display "D(tue) = ") (display (D 'tue)) (newline)
(display "D is not defined on wed, thu, fri.") (newline)
(display "Kan extensions fill in those gaps.")
Right Kan extension: the conservative approximation
The right Kan extension RanKD comes with a natural transformation ε : RanKD ∘ K → D. It is universal: for any other functor F with ε' : F ∘ K → D, there is a unique σ : F → RanKD such that ε' factors through ε. In Set, it is computed as an end: RanKD(a) = ∫i Set(A(a, Ki), Di). Read this as: "for each object a in A, consider all morphisms from a into the image of K, and use them to probe D."
Scheme
; Right Kan extension via the end formula (for Set-valued functors):; Ran_K D (a) = ∫_i Set(A(a, K i), D i);; In finite sets, the end is a product over all i in I; of the function space A(a, Ki) -> D(i).;; For our example with discrete I (no non-identity morphisms),; Ran_K D (a) = ∏_i (A(a, Ki) -> D(i));; When a = mon, A(mon, K(mon)) = {id}, A(mon, K(tue)) = {}; So Ran_K D (mon) is determined by D(mon) = 10.; When a = wed, A(wed, K(i)) = {} for all i in I,; so the product over empty hom-sets gives the terminal object.; Model: A has edges mon->tue, tue->wed, wed->thu, thu->fri
(define (hom-A a b)
(define order '((mon . 0) (tue . 1) (wed . 2) (thu . 3) (fri . 4)))
(let ((ia (cdr (assq a order)))
(ib (cdr (assq b order))))
(if (<= ia ib) (list (list a '-> b)) '())))
; Right Kan: for each a, take the min of D(i) over all i; reachable from a. Min = conservative (tightest constraint).; If no i is reachable, return +inf (terminal = no constraint).
(define (ran-K-D a)
(let ((vals (filter number?
(map (lambda (i)
(if (pair? (hom-A a (K i))) (D i) #f))
I))))
(if (null? vals) '+inf (apply min vals))))
(display "Ran_K D:") (newline)
(for-each (lambda (a)
(display " ") (display a) (display " -> ")
(display (ran-K-D a)) (newline))
A)
; mon->10, tue->20 (recovers D), wed/thu/fri->+inf (no constraint)
Python
# Right Kan extension: conservative estimate
I = ["mon", "tue"]
A = ["mon", "tue", "wed", "thu", "fri"]
order = {"mon": 0, "tue": 1, "wed": 2, "thu": 3, "fri": 4}
D = {"mon": 10, "tue": 20}
def hom_A(a, b):
"""Morphisms from a to b in the total order"""return [(a, "->", b)] if order[a] <= order[b] else []
def ran_K_D(a):
"""Right Kan extension: min over reachable D-values"""
vals = [D[i] for i in I if hom_A(a, i)]
returnmin(vals) if vals elsefloat("inf")
for a in A:
print(f" Ran_K D({a}) = {ran_K_D(a)}")
Left Kan extension: the liberal approximation
The left Kan extension LanKD is the dual. It comes with a unit η : D → LanKD ∘ K, and is universal from the other side. In Set, it is computed as a coend: LanKD(a) = ∫i A(Ki, a) × D(i). Where the right extension takes the tightest constraint (end = limit = universal quantifier), the left extension takes the freest construction (coend = colimit = existential quantifier).
Scheme
; Left Kan extension via the coend formula:; Lan_K D (a) = ∫^i A(K i, a) × D(i);; In finite sets with a discrete I, this is a coproduct:; Lan_K D (a) = ∐_i A(K(i), a) × D(i);; When a = fri, A(K(mon), fri) and A(K(tue), fri) are nonempty,; so both D(mon) and D(tue) contribute.; Left Kan = liberal: take the max (loosest bound).
(define (lan-K-D a)
(let ((vals (filter number?
(map (lambda (i)
(if (pair? (hom-A (K i) a)) (D i) #f))
I))))
(if (null? vals) '-inf (apply max vals))))
(display "Lan_K D:") (newline)
(for-each (lambda (a)
(display " ") (display a) (display " -> ")
(display (lan-K-D a)) (newline))
A)
; mon->10, tue->20 (recovers D on I); wed->20, thu->20, fri->20 (liberal: max of reachable values)
Python
# Left Kan extension: liberal estimatedef lan_K_D(a):
"""Left Kan extension: max over D-values that reach a"""
vals = [D[i] for i in I if hom_A(i, a)]
returnmax(vals) if vals elsefloat("-inf")
for a in A:
print(f" Lan_K D({a}) = {lan_K_D(a)}")
# Liberal: extends D by taking the largest contributing value.
Kan extensions as Haskell types
In Haskell, the right Kan extension is an end (universal quantification over a type variable), and the left Kan extension is a coend (existential quantification). These match the end/coend formulas exactly.
Scheme
; Haskell:; newtype Ran k d a = Ran (forall i. (a -> k i) -> d i); data Lan k d a = forall i. Lan (k i -> a) (d i);; Ran: given ANY way to go from a to k(i), produce d(i).; "forall" = end = universal quantifier.;; Lan: there EXISTS some i, a way to go from k(i) to a,; and a value in d(i).; "exists" = coend = existential quantifier.;; Scheme encoding (no types, so we use closures):; Right Kan: a function that, given a->k(i), returns d(i)
(define (make-ran k d)
(lambda (a)
(lambda (a->ki)
; For each i, if a->ki maps a into k(i), return d(i); This is the "best" approximation: works for ALL probes
(d (a->ki a)))))
; Left Kan: a pair of (k(i)->a, d(i)) for some i
(define (make-lan k d i)
(lambda (a)
(list 'lan (lambda (ki) a) (d i))))
; Example: k = list, d = length; Ran: "forall i. (a -> [i]) -> Int"; If you give me any way to turn a into a list, I give you the length.
(define (ran-example a->list)
(length (a->list 'anything)))
(display "Ran with (lambda (x) '(1 2 3)): ")
(display (ran-example (lambda (x) '(123)))) (newline)
(display "Ran with (lambda (x) '(a b)): ")
(display (ran-example (lambda (x) '(a b))))
Limits as Kan extensions
A limit of D : I → C is the right Kan extension of D along the unique functor K : I → 1 (the terminal category with one object). The Kan extension RanKD maps the single object of 1 to the limit of D. The universal property of the Kan extension becomes the universal property of the limit cone.
Scheme
; Limit = Right Kan extension along K : I -> 1;; K collapses everything to a single object *.; Ran_K D (*) = ∫_i Set(1(*, K i), D i); = ∫_i Set(1(*, *), D i) (K i = * for all i); = ∫_i D i; = limit of D;; Example: D maps three objects to sets of numbers.; The limit (= product, since I is discrete) is all tuples.
(define (D-values i)
(cond ((eq? i 'a) '(12))
((eq? i 'b) '(34))
((eq? i 'c) '(5))))
; K : I -> 1 (collapses everything to '*)
(define (K-to-1 i) '*)
; Limit of D over discrete I = product of all D(i)
(define (cartesian-product lists)
(if (null? lists) '(())
(let ((rest (cartesian-product (cdr lists))))
(apply append
(map (lambda (x)
(map (lambda (r) (cons x r)) rest))
(car lists))))))
(define I-objs '(a b c))
(define lim (cartesian-product (map D-values I-objs)))
(display "D(a)={1,2}, D(b)={3,4}, D(c)={5}") (newline)
(display "Limit (product): ") (display lim) (newline)
(display " = Ran_K D (*) where K : I -> 1")
Python
# Limit = Right Kan extension along K : I -> 1fromitertoolsimport product
D_vals = {"a": [1, 2], "b": [3, 4], "c": [5]}
lim = list(product(*D_vals.values()))
print(f"D(a)={{1,2}}, D(b)={{3,4}}, D(c)={{5}}")
print(f"Limit (product): {lim}")
print(" = Ran_K D(*) where K : I -> 1")
Adjunctions as Kan extensions
If L ⊢ R is an adjunction, then L = LanRId and R = RanLId. The left adjoint is the left Kan extension of the identity along the right adjoint, and vice versa. This is Mac Lane's punchline: adjunctions, limits, colimits, ends, coends are all Kan extensions.
Scheme
; Adjunctions as Kan extensions:; L = Lan_R Id (left adjoint = left Kan of Id along R); R = Ran_L Id (right adjoint = right Kan of Id along L);; Recall: L ⊣ R means Hom(L a, b) ≅ Hom(a, R b);; Lan_R Id (b) = ∫^a A(R a, b) × a (coend formula); = ∫^a C(R a, b) × a;; By Yoneda, this equals L(b) when the adjunction exists.;; Verify with product ⊣ exponential:; L(a) = (a, s) R(b) = s -> b
(define s 10) ; fixed state type (a number)
(define (L a) (cons a s)) ; pair with s
(define (R b) (lambda (st) b)) ; constant function (simplified); Lan_R Id should recover L:; "The freest way to approximate Id using R"; Since R(b) = s->b, and we want Lan_R Id (a),; we need: ∃b. Hom(R(b), a) × b = ∃b. Hom(s->b, a) × b; The canonical choice: b = a, the map is "evaluate at s"
(define (lan-R-id a)
; Exists b=a, with map (s->b) -> a given by (f -> f(s)); The value is (a, s) — exactly L(a)
(cons a s))
(display "L(42) = ") (display (L 42)) (newline)
(display "Lan_R Id (42) = ") (display (lan-R-id 42)) (newline)
(display "They agree: the left adjoint IS the left Kan extension.")
The free functor as a left Kan extension
Given a type constructor f (not necessarily a functor), its free functor is the left Kan extension of f along the identity. In Haskell: data FreeF f a = forall i. FMap (i → a) (f i). This freely adds fmap to any type constructor. The existential packages up a value of type f i together with a function i → a, and fmap just composes with that function.
Scheme
; Free functor = Lan_Id f; data FreeF f a = forall i. FMap (i -> a) (f i);; fmap g (FMap h fi) = FMap (g . h) fi;; This gives fmap to any type constructor for free.; A "type constructor" that isn't a functor:; It holds a value but provides no map.
(define (box-new x) (list 'box x))
(define (box-val b) (cadr b))
; Free functor wrapping: store a function and a box
(define (free-f func bx) (list 'free func bx))
(define (free-func ff) (cadr ff))
(define (free-box ff) (caddr ff))
; Wrap a box into the free functor (func = identity)
(define (free-lift bx)
(free-f (lambda (x) x) bx))
; fmap for the free functor: just compose
(define (free-fmap g ff)
(free-f (lambda (x) (g ((free-func ff) x)))
(free-box ff)))
; Extract the final value
(define (free-run ff)
((free-func ff) (box-val (free-box ff))))
; Demo: box has no fmap, but FreeF does
(define b (box-new 5))
(define fb (free-lift b))
(define mapped (free-fmap (lambda (x) (* x 3)) fb))
(define mapped2 (free-fmap (lambda (x) (+ x 1)) mapped))
(display "original box: ") (display (box-val b)) (newline)
(display "after fmap (*3): ") (display (free-run mapped)) (newline)
(display "after fmap (+1) again: ") (display (free-run mapped2))
; fmap composes the functions; the box is never touched.
Python
# Free functor: gives fmap to any type constructorclass Box:
"""A container with no map method."""def __init__(self, val): self.val = val
class FreeF:
"""Left Kan extension: adds fmap to any container."""def __init__(self, func, box):
self.func = func
self.box = box
@staticmethod
def lift(box):
return FreeF(lambda x: x, box)
def fmap(self, g):
f = self.func
return FreeF(lambda x: g(f(x)), self.box)
def run(self):
return self.func(self.box.val)
b = Box(5)
fb = FreeF.lift(b)
mapped = fb.fmap(lambda x: x * 3)
mapped2 = mapped.fmap(lambda x: x + 1)
print(f"original: {b.val}")
print(f"after fmap (*3): {mapped.run()}")
print(f"after fmap (+1): {mapped2.run()}")
Notation reference
Blog / Haskell
Scheme
Meaning
RanKD
(ran-K-D a)
Right Kan extension of D along K
LanKD
(lan-K-D a)
Left Kan extension of D along K
∫i Set(A(a,Ki), Di)
(apply min ...)
End formula (right Kan in Set)
∫i A(Ki,a) × Di
(apply max ...)
Coend formula (left Kan in Set)
Ran k d a = ∀i. (a→k i)→d i
(lambda (a->ki) ...)
Haskell right Kan type
Lan k d a = ∃i. (k i→a, d i)
(list 'lan f val)
Haskell left Kan type
Lim D = Ran!D
(cartesian-product ...)
Limit as right Kan along ! : I→1
FreeF f a = LanId f a
(free-f func bx)
Free functor as left Kan extension
Neighbors
Milewski chapters
🍞 Chapter 16 — Adjunctions (adjunctions are Kan extensions)
🍞 Chapter 15 — The Yoneda Lemma (used in the coend derivation)
Paper pages that use these concepts
🍞 Leinster 2021 — entropy as a functor; Kan extensions appear in change-of-base
The blog post works in Haskell where the end formula becomes forall i. (a -> k i) -> d i and the coend formula becomes the existential data Lan k d a = forall i. Lan (k i -> a) (d i). This page uses a finite poset (the weekday ordering) to make the end/coend computable as min/max. In the real formulas, the end is a limit (equalizer of products) and the coend is a colimit (coequalizer of coproducts). The blog post also derives the codensity monad as the right Kan extension of a functor along itself: Ran m m a = forall i. (a -> m i) -> m i, which is the continuation monad when m is an endofunctor. The free functor construction (LanId f) demonstrates that left Kan extensions freely add structure, while right Kan extensions preserve it conservatively. This asymmetry mirrors the left/right adjoint distinction from Chapter 16.
Ready for the real thing? Read the blog post. Start with the universal property diagrams, then trace how the end/coend formulas implement them.
Mac Lane). Given functors K : I → A and D : I → C, the right Kan extension RanKD : A → C is the best approximation of D along K. It answers: how do you extend a functor defined on a subcategory to the whole category? Limits, colimits, and adjunctions are all special cases.