Functors: map as mathematical structure

A functor is map. `list.map(f)` in Python, `Array.map` in JavaScript, `torch.vmap` in PyTorch - one abstract concept behind all of them. Category theory is the mathematics that names it correctly. And in 2022, Cruttwell et al. proved that backpropagation is also a functor. Fifty years of using the algorithm without knowing its formal definition.

• **PyTorch vmap / JAX vmap**: `torch.vmap(f)` is a functor that lifts f: Tensor -> Tensor to f: Batch<Tensor> -> Batch<Tensor>. JAX is built on functional transformations (vmap, grad, jit) precisely because their functor structure is compatible with automatic differentiation
• **Haskell / Scala / Rust**: Functor, Monad, Applicative are not GoF patterns - they are exact encodings of categorical constructions. GHC applies fusion optimization based on functor laws: chained .map() calls are merged into a single pass with no intermediate lists
• **TypeScript variance**: function parameters are contravariant, return types are covariant. This is not a TypeScript design decision - it is a mathematical necessity following from the definition of a functor
• **Backprop as Functor (Cruttwell 2022)**: backpropagation is a functor between the category of parameterized functions and the category of their derivatives - one of the most unexpected results in applied category theory

What a functor is

In 2022, Cruttwell et al. published "Backprop as Functor". The paper showed that backpropagation is a functor between the category of parameterized functions and the category of their derivatives. Fifty years of using backprop - without knowing its formal definition. Functors were everywhere; the name was just missing.

A functor F: C -> D is a mapping between two categories that carries both objects and morphisms. It carries them without loss: the structure of C must be reflected in D precisely - not approximately, not by analogy, but mathematically exactly, through two laws.

A functor F: C -> D is a pair of mappings: 1. On objects: assigns to each A in C an object F(A) in D 2. On morphisms: assigns to each f: A -> B a morphism F(f): F(A) -> F(B) Both laws must hold: F(id_A) = id_{F(A)} (preservation of identity) F(g o f) = F(g) o F(f) (preservation of composition)

The two laws are not formality. Preservation of identity guarantees that an "empty" action stays empty. Preservation of composition guarantees that two steps in C can be performed through F separately or together - the result is the same. That is the precise meaning of "without loss".

Covariant functor: map in programming

A functor that preserves the direction of arrows is called covariant. If f: A -> B, then F(f): F(A) -> F(B). The arrow goes in the same direction. This is the "ordinary" functor - the one programmers know as `.map()`.

`Array.map`, `Promise.then`, `Option.map`, `torch.vmap`, `jax.vmap` - all covariant functors. PyTorch `vmap` is a functor literally: it takes a function f: Tensor -> Tensor and lifts it to f: Batch<Tensor> -> Batch<Tensor>, preserving all structure. JAX is built on functional transformations precisely because functor structure is compatible with automatic differentiation.

Checking the laws for Array. Identity law: `[1,2,3].map(x => x)` gives `[1,2,3]` - unchanged. Composition law: `arr.map(f).map(g)` equals `arr.map(x => g(f(x)))`. This is not merely convenient - it is exactly the definition of a correct functor. A `.map()` that violates either law is not a functor.

Contravariant functor: the arrow flips

Consider a type that does not produce values of T - but consumes them. A predicate `(t: T) => boolean` takes T as input. A comparator `(a: T, b: T) => number` takes two T values. A serializer `(t: T) => string` consumes T. For such types ordinary map cannot be written - but contramap can. And when contramap is applied, the arrow flips.

A contravariant functor has contramap instead of map. If map takes (A -> B) and turns F<A> into F<B>, then contramap takes (A -> B) and turns F<B> into F<A>. The input function is "reversed". Formally: a contravariant functor from C to D is a covariant functor from C^op to D.

Contravariance is built into the TypeScript type system. Function parameters are contravariant: if `Dog extends Animal`, then `(Animal) => void` is compatible with `(Dog) => void`, but not the other way around. This is not a design quirk - it is a mathematical necessity. TypeScript simply implements category theory at the type level.

Bifunctor and profunctor: two arguments

Some types are parameterized by two arguments: `Either<A, B>`, `Pair<A, B>`, `Map<K, V>`. A bifunctor is a functor of two arguments. In each argument it behaves like an ordinary covariant functor. `bimap(f, g)` transforms both components simultaneously.

A bifunctor B: C x D -> E is a functor from the product category C x D to E. It is functorial in each argument: B(f, id) - functor in the first argument B(id, g) - functor in the second argument B(f, g) = B(f, id) o B(id, g) = B(id, g) o B(f, id)

A special case: the function type `A -> B` is a bifunctor. An unusual one: contravariant in A (the input) and covariant in B (the output). Such a bifunctor is called a profunctor. It describes something that simultaneously consumes one type and produces another. Optics in Haskell (lens, prism, iso) are built on profunctors.

Summary of the hierarchy. Covariant functor: map preserves arrows. Contravariant: contramap reverses them. Bifunctor: bimap over two arguments. Profunctor: dimap - contramap on input, map on output. All of these are different answers to the question "how does a functor relate to the direction of arrows?" And all of them live in every line of TypeScript, Rust, Haskell, and Scala.

Key Ideas

• **Functor** F: C -> D - a mapping between categories preserving identity (F(id_A) = id_{F(A)}) and composition (F(g o f) = F(g) o F(f))
• **Covariant** functor preserves arrow direction: f: A -> B => F(f): F(A) -> F(B). This is Array.map, Promise.then, torch.vmap
• **Contravariant** functor reverses arrows: f: A -> B => F(f): F(B) -> F(A). This is Predicate, Comparator, function parameters in TypeScript
• **Bifunctor** - a functor of two arguments: bimap(f, g) transforms both components (Either, Pair)
• **Profunctor** - bifunctor contravariant in input, covariant in output: dimap. Foundation of lens optics in Haskell

Related Topics

Functors bridge categories and open the path to more advanced constructions:

• Categories: Objects and Morphisms — Foundation: functors are defined on categories
• Natural Transformations — Morphisms between functors - the next level of abstraction

Вопросы для размышления

• What other container types in a familiar language are functors? Check both laws.
• Why is the function type A -> B contravariant in A? How does a consumer differ from a producer in categorical terms?
• If F: C -> D is a functor and G: D -> E is a functor, what is G o F? Is it a functor from C to E?

Связанные уроки

• ct-01 — Categories and morphisms - foundation for functors
• ct-03 — Natural transformations - morphisms between functors
• aa-01-groups-intro — Group homomorphism is a special case of a functor
• la-02-dot-product — Linear maps are functors in the category Vect
• aa-03-homomorphisms
• plt-07-algebraic-types