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 37))
(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))
The coproduct (tagged union / Either) is also a bifunctor. bimap applies one function to the Left case, the other to the Right case. Together, these two are 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 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. dimap takes two functions: one to adapt the input (going backwards), one to adapt 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
Python
# Profunctor: dimap for functionsdef dimap(f, g, h):
returnlambda x: g(h(f(x)))
char_count = len
adapted = dimap(str,
lambda n: f"length={n}",
char_count)
print(adapted(42)) # 42 -> "42" -> 2 -> "length=2"print(adapted(1000000)) # 1000000 -> "1000000" -> 7 -> "length=7"# dimap id id h = h
same = dimap(lambda x: x, lambda x: x, char_count)
print(f"dimap id id: {same('hello')}") # 5
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, and the key ingredient when auto-deriving 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. Haskell can auto-derive Functor because 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.
Milewski 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. Where the blog derives functor instances for ADTs via Const and Identity composition, this page follows the same decomposition manually for Maybe and Tree. Writer's derivation from Kleisli composition is covered in Chapter 4. A subtlety worth flagging: separate functoriality in each argument does not prove joint functoriality. You also need the commutativity condition (applying first then second equals applying second then first). 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.
Bifunctor