Functoriality

Bartosz Milewski · 2015 · Category Theory for Programmers, Ch. 8

Every algebraic data type you build from products, coproducts, and function types is automatically functorial. The functor instance writes itself because bimap distributes over sums and products, contramap handles the input side of functions, and dimap handles both sides at once.

Bifunctors: functors of two arguments

A bifunctor maps two categories into a third. In programming, that means a type constructor with two type parameters, where you can map over both independently. The canonical example: the pair type (a, b). Apply one function to the first component, another to the second.

Scheme

; A bifunctor maps two arguments covariantly.
; bimap : (a -> c) -> (b -> d) -> F(a,b) -> F(c,d)

; Pair bifunctor: apply f to first, g to second
(define (bimap-pair f g pair)
  (cons (f (car pair)) (g (cdr pair))))

; Example: double the first, negate the second
(define p (cons 3 7))
(display "original: ") (display p) (newline)
(display "bimap:    ")
(display (bimap-pair (lambda (x) (* x 2))
                     (lambda (x) (- 0 x))
                     p))
(newline)

; bimap id id = id  (functor law)
(display "bimap id id: ")
(display (bimap-pair (lambda (x) x) (lambda (x) x) p))

Coproduct as a bifunctor

The coproduct (tagged union / Either) is also a bifunctor. bimap applies one function to the Left case, the other to the Right case. Together with the product bifunctor, these two give you the building blocks for all algebraic data types.

Scheme

; Either as a bifunctor
; Represent Either as tagged: (left . value) or (right . value)

(define (make-left x) (cons 'left x))
(define (make-right x) (cons 'right x))
(define (left? e) (eq? (car e) 'left))

(define (bimap-either f g e)
  (if (left? e)
      (make-left (f (cdr e)))
      (make-right (g (cdr e)))))

; Apply different transforms to each branch
(define e1 (make-left 42))
(define e2 (make-right 7))

(display "left:  ") (display (bimap-either (lambda (x) (* x 2))
                                           (lambda (x) (+ x 100)) e1)) (newline)
(display "right: ") (display (bimap-either (lambda (x) (* x 2))
                                           (lambda (x) (+ x 100)) e2))
; Left maps the first function. Right maps the second.

Maybe from bifunctors: algebraic data types are functorial

Maybe a = Either () a. The () is a constant (the Const functor), and a is the identity functor. Since Either is a bifunctor and both Const and Identity are functors, the composite is automatically a functor. Every ADT built from sums and products inherits its functor instance for free.

Scheme

; Maybe = Either(Const(()), Identity(a))
; Nothing = Left(())    Just(x) = Right(x)

(define nothing (cons 'left '()))
(define (just x) (cons 'right x))
(define (nothing? m) (and (pair? m) (eq? (car m) 'left)))

; fmap for Maybe comes from bimap-either + const + identity
(define (fmap-maybe f m)
  (if (nothing? m)
      nothing
      (just (f (cdr m)))))

(display "fmap (*2) Just(5):   ") (display (fmap-maybe (lambda (x) (* x 2)) (just 5))) (newline)
(display "fmap (*2) Nothing:   ") (display (fmap-maybe (lambda (x) (* x 2)) nothing)) (newline)

; The functor instance writes itself: bimap id f on Either () a
; Const ignores f. Identity applies f. Sum picks the branch.

Contravariant functors: reversing the arrows

A contravariant functor is a functor from the opposite category. Instead of fmap : (a -> b) -> F a -> F b, you get contramap : (b -> a) -> F a -> F b. The arrows reverse. The canonical example: predicates. If you have a predicate on strings and a function int -> string, you can build a predicate on ints by converting first, then testing.

Scheme

; Contravariant functor: contramap reverses the arrow.
; contramap : (b -> a) -> F(a) -> F(b)
;
; Predicate on a = a -> Bool
; Given (b -> a) and (a -> Bool), get (b -> Bool)
; Just pre-compose!

(define (contramap-pred f pred)
  (lambda (x) (pred (f x))))

; A predicate on strings: is it long?
(define (long? s) (> (string-length s) 5))

; A function: number -> string
(define (show n) (number->string n))

; Contramapped: is the number's string representation long?
(define long-number? (contramap-pred show long?))

(display "long?("hi"):     ") (display (long? "hi")) (newline)
(display "long?("category"): ") (display (long? "category")) (newline)
(display "long-number?(7):      ") (display (long-number? 7)) (newline)
(display "long-number?(1000000): ") (display (long-number? 1000000))
; 7 -> "7" -> not long.  1000000 -> "1000000" -> long.

Comparators: another contravariant functor

Comparators are contravariant too. If you can compare strings, and you have a function person -> string that extracts a name, you can compare people by name. You pull back the comparison through the extraction function.

Scheme

; Comparators are contravariant.
; Comparator on a = a -> a -> ordering
; contramap: (b -> a) -> Cmp(a) -> Cmp(b)

(define (contramap-cmp f cmp)
  (lambda (x y) (cmp (f x) (f y))))

; Compare strings alphabetically
(define (string-cmp a b)
  (cond ((string<? a b) 'lt)
        ((string>? a b) 'gt)
        (else 'eq)))

; People as (name . age) pairs
(define (person-name p) (car p))

; Compare people by name — pulled back through person-name
(define name-cmp (contramap-cmp person-name string-cmp))

(display (name-cmp (cons "Alice" 30) (cons "Bob" 25))) (newline)
(display (name-cmp (cons "Charlie" 40) (cons "Alice" 35)))
; Alice < Bob, Charlie > Alice

Profunctors: contra in first, co in second

The function arrow a -> b is contravariant in a (the input) and covariant in b (the output). A type that behaves this way is a profunctor. The operation dimap takes two functions: one to pre-process the input (going backwards), one to post-process the output (going forwards).

Scheme

; Profunctor: contravariant in first arg, covariant in second.
; dimap : (a' -> a) -> (b -> b') -> P(a,b) -> P(a',b')
;
; For functions: dimap f g h = g . h . f
; f adapts the input (contra), g adapts the output (co).

(define (dimap f g h)
  (lambda (x) (g (h (f x)))))

; A function: string -> number (count chars)
(define (char-count s) (string-length s))

; Pre-process: number -> string (show it first)
; Post-process: number -> string (format the result)
(define adapted
  (dimap number->string
         (lambda (n) (string-append "length=" (number->string n)))
         char-count))

(display (adapted 42)) (newline)
; 42 -> "42" -> 2 -> "length=2"

(display (adapted 1000000)) (newline)
; 1000000 -> "1000000" -> 7 -> "length=7"

; dimap id id h = h  (identity law)
(define same (dimap (lambda (x) x) (lambda (x) x) char-count))
(display "dimap id id: ") (display (same "hello"))
; 5 — unchanged

The Const functor

The Const functor ignores its second type parameter. Const c a always holds a c, regardless of a. Its fmap does nothing: the value doesn't depend on the type parameter, so there's nothing to transform. Const is the "zero" in the algebra of functors. It shows up everywhere in the automatic derivation of functor instances for ADTs.

Scheme

; Const functor: holds a fixed value, ignores the type parameter.
; Const c a = c  (a is phantom)
; fmap f (Const c) = Const c  (f is never applied)

(define (make-const c) (cons 'const c))
(define (const-val c) (cdr c))

(define (fmap-const f c)
  c)  ; ignore f entirely

(define c (make-const 42))
(display "original:   ") (display c) (newline)
(display "fmap (*2):  ") (display (fmap-const (lambda (x) (* x 2)) c)) (newline)
(display "fmap str:   ") (display (fmap-const number->string c)) (newline)
; All three are the same. The Const functor is inert.

; Why does this matter? It's a building block.
; Maybe a = Either (Const () a) (Identity a)
; Nothing carries Const () — fmap can't touch it.
; Just carries Identity — fmap goes straight through.

Putting it together: the functoriality of ADTs

Every algebraic data type is a nested composition of sums (Either), products (pairs), Const, and Identity. Since all of these are functorial, their compositions are too. This is why Haskell can auto-derive Functor: the compiler walks the type structure and assembles fmap from bimap, contramap, and the identity. The only catch: the type parameter must appear in covariant (positive) position. If it appears in a function argument (negative position), you need Contravariant or Profunctor instead.

Scheme

; Summary: the algebra of functors
; bimap  handles products and coproducts (two covariant args)
; fmap   handles single covariant arg (ordinary functor)
; contramap handles single contravariant arg (function input)
; dimap  handles one contra + one co (profunctor)

; A tree is an ADT: Leaf(a) | Branch(Tree(a), Tree(a))
; = Either(Identity(a), Pair(Tree(a), Tree(a)))
; fmap follows the structure:

(define (make-leaf x) (list 'leaf x))
(define (make-branch l r) (list 'branch l r))
(define (leaf? t) (eq? (car t) 'leaf))

(define (fmap-tree f t)
  (if (leaf? t)
      (make-leaf (f (cadr t)))                    ; Identity: apply f
      (make-branch (fmap-tree f (cadr t))         ; recurse left
                   (fmap-tree f (caddr t)))))     ; recurse right

(define tree
  (make-branch (make-leaf 1)
               (make-branch (make-leaf 2)
                            (make-leaf 3))))

(display "original: ") (display tree) (newline)
(display "doubled:  ") (display (fmap-tree (lambda (x) (* x 2)) tree))
; The functor instance follows the sum/product structure automatically.

; Summary: the algebra of functors
; bimap  handles products and coproducts (two covariant args)
; fmap   handles single covariant arg (ordinary functor)
; contramap handles single contravariant arg (function input)
; dimap  handles one contra + one co (profunctor)

; A tree is an ADT: Leaf(a) | Branch(Tree(a), Tree(a))
; = Either(Identity(a), Pair(Tree(a), Tree(a)))
; fmap follows the structure:

(define (make-leaf x) (list 'leaf x))
(define (make-branch l r) (list 'branch l r))
(define (leaf? t) (eq? (car t) 'leaf))

(define (fmap-tree f t)
  (if (leaf? t)
      (make-leaf (f (cadr t)))                    ; Identity: apply f
      (make-branch (fmap-tree f (cadr t))         ; recurse left
                   (fmap-tree f (caddr t)))))     ; recurse right

(define tree
  (make-branch (make-leaf 1)
               (make-branch (make-leaf 2)
                            (make-leaf 3))))

(display "original: ") (display tree) (newline)
(display "doubled:  ") (display (fmap-tree (lambda (x) (* x 2)) tree))
; The functor instance follows the sum/product structure automatically.

Notation reference

Blog / Haskell	Scheme	Meaning
bimap f g	(bimap-pair f g p)	Map both components of a bifunctor
first f = bimap f id	(bimap-pair f (lambda (x) x) p)	Map only the first component
second g = bimap id g	(bimap-pair (lambda (x) x) g p)	Map only the second component
contramap f	(contramap-pred f pred)	Pre-compose: reverse the input arrow
dimap f g h	(dimap f g h)	Pre-compose f, post-compose g
Const c a	(make-const c)	Ignores type parameter a
Identity a	a	Passes type parameter through

Neighbors

Milewski chapters

🍞 Chapter 7 — Functors: structure-preserving maps
(next) Chapter 9 — Function Types: exponentials

Paper pages that use these concepts

🍞 Hedges 2018 — open games use profunctors (contravariant coplay channel)
🍞 Capucci 2021 — parametrised optics generalize profunctors

Foundations (Wikipedia)

Translation notes

The blog post uses Haskell typeclasses (Bifunctor, Contravariant, Profunctor) and C++ templates. This page uses plain Scheme functions, since Scheme has no type system to enforce the laws. The automatic derivation of functor instances for ADTs, which Milewski shows via Const and Identity composition, is demonstrated here by manually following the same decomposition for Maybe and Tree. The blog post also discusses the Writer functor's derivation from Kleisli composition. That's covered in Chapter 4. One subtlety from the blog post worth noting: separate functoriality in each argument is not enough to prove joint functoriality. The commutativity condition (applying first then second equals applying second then first) is required. Categories that violate this are called premonoidal.

Ready for the real thing? Read the blog post. Start with the bifunctor section, then trace how Maybe decomposes into Const + Identity.

← Functors by june.kim Function Types →