Two Derivatives: Zippers and Automatic Differentiation

The problem: navigating an immutable structure

Immutability (Chapter 5) means there’s no such thing as walking to the middle of a list and mutating it in place. Every “move to this position and change it” has to rebuild something. Done naively, that’s expensive — reaching the third element of a list, changing it, and reassembling the whole thing means re-walking the first two elements on the way there and rebuilding everything on the way back.

The zipper is Haskell’s answer: a data structure that remembers where you are, so moving one step, or editing the focused element, is genuinely O(1) — no re-walking required.

data ListZipper a = ListZipper [a] a [a]
--                              ^    ^  ^
--                          prefix  focus  suffix
--                        (reversed)

goRight :: ListZipper a -> Maybe (ListZipper a)
goRight (ListZipper ls x (r:rs)) = Just (ListZipper (x:ls) r rs)
goRight _                        = Nothing

goLeft :: ListZipper a -> Maybe (ListZipper a)
goLeft (ListZipper (l:ls) x rs) = Just (ListZipper ls l (x:rs))
goLeft _                        = Nothing

update :: a -> ListZipper a -> ListZipper a
update x' (ListZipper ls _ rs) = ListZipper ls x' rs

goRight peels one element off the suffix and pushes the old focus onto the (reversed) prefix; goLeft does the exact mirror image. update replaces the focus directly, with no rebuilding of anything on either side. Every operation here is O(1) — the entire point of the structure.

The surprising part: this shape is a derivative

Here’s where it gets genuinely strange. In 2001, Conor McBride noticed something that looks, at first glance, like numerology: if you write a data type’s shape as a polynomial — the way combinatorialists already did, purely for counting purposes — and take its literal calculus derivative, the result is exactly the type of “that structure, but with one hole where a single element used to be.”

Write List a as an equation the way Base Camp’s data declarations already suggest: a list is either empty, or one element followed by another list —

$L(a) = 1 + a \cdot L(a)$

Solved as an ordinary equation, $L(a) = \frac{1}{1-a} = 1 + a + a^2 + a^3 + \cdots$ — which is just a fancy way of saying “a list is a choice of length 0, or 1, or 2, …, each with that many elements.” Now take the derivative with respect to $a$, using nothing but ordinary first-year calculus:

$L'(a) = \frac{1}{(1-a)^2} = L(a) \times L(a)$

That’s the ListZipper. List a × List a is precisely ListZipper’s prefix-and-suffix pair — the derivative of a list’s polynomial, worked out with the ordinary quotient rule, lands exactly on the shape a hand-designed zipper needed. Not an analogy — the same type, up to relabeling.

Automatic differentiation: taking “derivative” seriously the other way

If a type’s derivative is a real, useful thing to compute, what about an ordinary function’s derivative — the calculus kind? Automatic differentiation (AD) computes exact derivatives of real functions, not by symbolic manipulation (which can blow up into unreadable expressions) and not by numerical approximation (which is only ever approximately right) — but by structurally propagating derivative information alongside every ordinary arithmetic operation, using nothing but the chain rule, applied mechanically.

The simplest version pairs every value with its own derivative, in a type sometimes called a dual number:

data Dual = Dual Double Double   -- value, derivative

instance Num Dual where
  fromInteger n              = Dual (fromInteger n) 0
  (Dual x x') + (Dual y y')  = Dual (x + y) (x' + y')
  (Dual x x') * (Dual y y')  = Dual (x * y) (x' * y + x * y')   -- the product rule!
  negate (Dual x x')         = Dual (negate x) (negate x')

var :: Double -> Dual
var x = Dual x 1   -- "seed" a variable: d/dx of x is 1

diff :: (Dual -> Dual) -> Double -> Double
diff f x = let (Dual _ d) = f (var x) in d

f :: Num a => a -> a
f x = x*x + 3*x

ghci> diff f 5
13.0

Every arithmetic operation is overloaded to carry a derivative alongside its ordinary result, combined by exactly the rule calculus already gives for that operation — *’s Num instance above is the product rule, written down verbatim as Haskell. Calling f (var 5) doesn’t just compute f(5) = 40; it computes f(5) and f'(5) = 13 simultaneously, correctly, with no approximation error, purely because ordinary function application threads the (value, derivative) pair through every + and * in f’s body automatically.

Where this lands: backpropagation

That last sentence is the entire reason automatic differentiation matters far beyond Haskell. A neural network’s training step needs the derivative of one number (the loss) with respect to millions of parameters — forward-mode AD, run once per parameter, would be millions of times slower than necessary. Reverse-mode AD flips the direction: one forward pass computes the output while recording every operation performed, then one backward pass propagates derivatives from the output back toward every input simultaneously, using the chain rule in reverse.

That backward pass, applied to a neural network specifically, is backpropagation — not a separate algorithm bolted onto deep learning, but reverse-mode automatic differentiation, applied to exactly the kind of large, many-input, one-output function a trained network’s loss represents. Every major deep learning framework’s “autograd” engine — PyTorch’s, TensorFlow’s, JAX’s — is, underneath its Python API, doing structurally the same thing this chapter’s Dual type did by hand: propagating exact derivatives through ordinary arithmetic operations, mechanically, via the chain rule, just in the reverse direction and at a scale of millions of parameters rather than one.

Two ideas, one word, both entirely serious: a type’s derivative tells you the shape of a one-hole context inside it, precisely enough to build an efficient navigation structure by calculation rather than trial and error; a function’s derivative, computed the same structural way rather than approximated, is the exact mechanism every modern neural network learns by. Neither is a metaphor borrowed from the other — they’re the same operation, showing up in two different corners of the same language.