A functor F is representable if F(a) is isomorphic to Hom(r, a) for some object r. That means every container of type F is secretly a function from r. tabulate turns a function into the container; index turns the container back into a function. Round-trip: tabulate (index s) = s. This is memoization, stated categorically.
The hom-functor: functions as a functor
Fix a type r. The set of all functions r -> a depends on a functorially: given f : a -> b, you get (r -> a) -> (r -> b) by post-composing. This is the reader functor, also called the hom-functor Hom(r, -). A representable functor is one that's naturally isomorphic to this reader for some choice of r.
Scheme
; The reader functor: (r -> a) is functorial in a.; fmap f g = f . g (post-compose);; Fix r = Symbol. A "reader" is a function from symbols to values.
(define (fmap-reader f g)
(lambda (r) (f (g r))))
; g : symbol -> number (a lookup table)
(define (lookup key)
(cond ((eq? key 'x) 1)
((eq? key 'y) 2)
((eq? key 'z) 3)
(else0)))
; f : number -> string
(define (show-doubled n)
(number->string (* n 2)))
; fmap show-doubled lookup : symbol -> string
(define mapped (fmap-reader show-doubled lookup))
(display "lookup 'x: ") (display (lookup 'x)) (newline)
(display "mapped 'x: ") (display (mapped 'x)) (newline)
(display "mapped 'y: ") (display (mapped 'y)) (newline)
; Post-composition: lookup first, then transform the result.
Stream: an infinite container represented by Integer
An infinite stream holds one value for every natural number. That means a stream of a is the same information as a function Integer -> a. The representing object is Integer. tabulate builds a stream by calling the function at 0, 1, 2, ...; index walks the stream to the n-th element.
Scheme
; Stream: infinite list, represented by Integer.; Stream(a) โ (Integer -> a);; tabulate : (Integer -> a) -> Stream(a); index : Stream(a) -> Integer -> a; Represent a stream as a thunk-based pair: (head . tail-thunk)
(define (stream-cons h t) (cons h t))
(define (stream-head s) (car s))
(define (stream-tail s) ((cdr s)))
; tabulate: turn a function into a stream
(define (tabulate f)
(stream-cons (f 0)
(lambda () (tabulate (lambda (n) (f (+ n 1)))))))
; index: turn a stream back into a function
(define (stream-index s n)
(if (= n 0)
(stream-head s)
(stream-index (stream-tail s) (- n 1))))
; Build a stream of squares: n -> n^2
(define squares (tabulate (lambda (n) (* n n))))
(display "squares[0]: ") (display (stream-index squares 0)) (newline)
(display "squares[1]: ") (display (stream-index squares 1)) (newline)
(display "squares[4]: ") (display (stream-index squares 4)) (newline)
(display "squares[10]: ") (display (stream-index squares 10))
; Each element is computed lazily on demand.
Python
# Stream represented by Integerclass Stream:
def __init__(self, head, tail_fn):
self.head = head
self._tail = tail_fn
def tail(self):
return self._tail()
def tabulate(f):
return Stream(f(0), lambda: tabulate(lambda n: f(n + 1)))
def index(s, n):
while n > 0:
s = s.tail()
n -= 1return s.head
squares = tabulate(lambda n: n * n)
for i in [0, 1, 4, 10]:
print(f"squares[{i}]: {index(squares, i)}")
The round-trip: tabulate and index are inverses
A functor is representable when tabulate and index are inverses. That means two laws hold: tabulate (index s) = s (build a stream from its own indexing function and you get the same stream) and index (tabulate f) = f (index into a tabulated function and you get back the original function). This is the natural isomorphism between F and Hom(r, -).
Scheme
; Round-trip laws:; 1. index (tabulate f) n = f n; 2. tabulate (index s) = s;; Law 1: tabulate a function, then index into it.; You should get the original function back.
(define (f n) (* n (+ n 1))) ; n -> n*(n+1)
(define tabulated-f (tabulate f))
(display "f(0) = ") (display (f 0))
(display " index(tabulate(f), 0) = ")
(display (stream-index tabulated-f 0)) (newline)
(display "f(5) = ") (display (f 5))
(display " index(tabulate(f), 5) = ")
(display (stream-index tabulated-f 5)) (newline)
(display "f(9) = ") (display (f 9))
(display " index(tabulate(f), 9) = ")
(display (stream-index tabulated-f 9)) (newline)
; Law 2: index a stream to get a function, tabulate it back.; We can verify element-wise.
(define roundtrip (tabulate (lambda (n) (stream-index squares n))))
(display "squares[7] = ") (display (stream-index squares 7))
(display " roundtrip[7] = ") (display (stream-index roundtrip 7))
; Same values: the isomorphism holds.
Memoization: the computational meaning
Representability is memoization. A function r -> a computes a value on every call. tabulate converts it into a data structure that stores all the results. index retrieves them. The function and the data structure carry the same information, but the data structure trades space for time. Milewski: "a representable functor is a memoized function."
Scheme
; Memoization as representability.; The function computes. The stream stores.; tabulate = memoize. index = lookup.; An "expensive" function
(define call-count 0)
(define (expensive n)
(set! call-count (+ call-count 1))
(* n n n)) ; cube; Without memoization: every call recomputes
(set! call-count 0)
(display "expensive(5): ") (display (expensive 5)) (newline)
(display "expensive(5): ") (display (expensive 5)) (newline)
(display "calls: ") (display call-count) (newline)
; With tabulate: compute once, store in stream
(set! call-count 0)
(define cubes (tabulate expensive))
(display "cubes[5]: ") (display (stream-index cubes 5)) (newline)
(display "cubes[5]: ") (display (stream-index cubes 5)) (newline)
(display "calls: ") (display call-count) (newline)
; In a lazy language, the second access reuses the stored value.; In Scheme, we recompute โ but the structure is the same.; The point: tabulate IS memoization.
Python
# Memoization = tabulatefromfunctoolsimport lru_cache
call_count = 0def expensive(n):
global call_count
call_count += 1return n ** 3# Without memo
call_count = 0print(f"expensive(5): {expensive(5)}")
print(f"expensive(5): {expensive(5)}")
print(f"calls: {call_count}")
# With memo (Python's built-in tabulate)
call_count = 0
memo_expensive = lru_cache(maxsize=None)(expensive)
print(f"memo(5): {memo_expensive(5)}")
print(f"memo(5): {memo_expensive(5)}")
print(f"calls: {call_count}")
# Second call: 0 extra calls. That's tabulate.
Not every functor is representable
The list functor is not representable. A function r -> a always produces a value for every input, but a list can be empty. There's no representing object r such that [a] is isomorphic to r -> a for all a. Representable functors must have a fixed "shape" determined by the representing object. Lists have variable length, so they fail.
Scheme
; List is NOT representable.; Why? A function (r -> a) always returns a value for every r.; But a list can be empty โ no value to return.;; Suppose we try: what is Rep for List?; A list of length 3 looks like (Integer<3 -> a).; A list of length 0 looks like (Void -> a).; The "shape" changes โ there's no single fixed r.; Contrast with Stream:; Every stream has exactly the same shape: one slot per integer.; tabulate always produces an infinite stream.; That fixed shape is what makes it representable.; Pair is representable too: Rep = Bool (two slots)
(define (tabulate-pair f)
(cons (f #t) (f #f)))
(define (index-pair p b)
(if b (car p) (cdr p)))
(define p (tabulate-pair (lambda (b) (if b "left""right"))))
(display "pair: ") (display p) (newline)
(display "index #t: ") (display (index-pair p #t)) (newline)
(display "index #f: ") (display (index-pair p #f)) (newline)
; Round-trip check
(define (g b) (if b 1020))
(display "g(#t)=") (display (g #t))
(display " index(tabulate(g), #t)=")
(display (index-pair (tabulate-pair g) #t))
fmap for free
If a functor is representable, you get fmap for free. To map f over a container: index it into a function, post-compose f, then tabulate the result. This is the reader functor's fmap transported through the isomorphism.
Scheme
; fmap from tabulate and index:; fmap f s = tabulate (f . index s);; No need to pattern-match on the data structure.; The isomorphism does the work.
(define (fmap-rep f s)
(tabulate (lambda (n) (f (stream-index s n)))))
; Stream of naturals
(define nats (tabulate (lambda (n) n)))
; fmap: double every element
(define doubled (fmap-rep (lambda (x) (* x 2)) nats))
(display "nats[0..4]: ")
(let loop ((i 0))
(if (< i 5)
(begin (display (stream-index nats i)) (display " ")
(loop (+ i 1)))))
(newline)
(display "doubled[0..4]: ")
(let loop ((i 0))
(if (< i 5)
(begin (display (stream-index doubled i)) (display " ")
(loop (+ i 1)))))
; fmap through the isomorphism โ no direct recursion on Stream.
Python
# fmap via tabulate/indexdef fmap_stream(f, s):
return tabulate(lambda n: f(index(s, n)))
nats = tabulate(lambda n: n)
doubled = fmap_stream(lambda x: x * 2, nats)
print("nats[0..4]: ", [index(nats, i) for i inrange(5)])
print("doubled[0..4]:", [index(doubled, i) for i inrange(5)])
Notation reference
Blog / Haskell
Scheme
Meaning
C(a, -)
(lambda (x) (a -> x))
Hom-functor / reader functor
Rep f
Integer (for Stream)
Representing object
tabulate :: (Rep f -> a) -> f a
(tabulate f)
Function to container
index :: f a -> Rep f -> a
(stream-index s n)
Container to function
tabulate . index = id
(tabulate (lambda (n) (stream-index s n)))
Round-trip law (container)
index . tabulate = id
(stream-index (tabulate f) n) = (f n)
Round-trip law (function)
Neighbors
Milewski chapters
๐ Chapter 7 โ Functors: the concept representable functors generalize
๐ Chapter 9 โ Function Types: exponentials, the Hom-set as a type
๐ Chapter 12 โ Limits and Colimits: universal constructions
The blog post uses Haskell's Representable typeclass with an associated type Rep f. This page uses plain Scheme functions, since Scheme has no type system to enforce the isomorphism laws. Streams are implemented with thunks for lazy tails, approximating Haskell's lazy evaluation. The memoization example doesn't truly cache in Scheme (no lazy thunks), but the structure is identical: tabulate builds the lookup structure, index retrieves from it. The blog post also discusses the logarithmic interpretation (if F(a) = a^r then r = log F) and the connection to the Yoneda lemma (every natural transformation from a hom-functor to F corresponds to an element of F(r), but representability requires this correspondence to be an isomorphism, not just a mapping).
Ready for the real thing? Read the blog post. Start with the hom-functor review, then trace the Stream instance through tabulate and index.
Representable functor