You are what you map into

Here's a small example, no math required. Suppose I hide an integer in a box. You can't open the box. But you can hand me any function Int => R (for whatever R you like) and I'll apply it to the hidden value and hand back the result.

Can you figure out which integer is in the box? Of course. Hand me the identity function x => x and I'll have no choice but to tell you. Or hand me x => x.toString if you want it as text. Or x => x > 0 if you only care about its sign.

The point: a black box that promises "I'll apply any function you give me to my hidden value" is the value. There's no extra information. There's no less either. The two are equivalent.

That's the whole intuition. Now we'll see why it's interesting.

To talk about "all arrows out of an object", category theory has a name. Pick a fixed object A. For any other object B, the collection of arrows from A to B is called the hom-set, written Hom(A, B) or sometimes C(A, B).

Now let B vary. As you change B, the hom-set changes too. So Hom(A, -) is a thing that takes an object and produces a set. That's a functor — the hom-functor:

Hom(A, -)  :  C  →  Set

For programmers, this is way less scary than it sounds. Substitute "types" for objects and "functions" for arrows:

• Hom(A, B) is the type A => B (the set of functions from A to B).
• Hom(A, -) is the type constructor B => (A => B) — give it any B, get back the type of functions A → B.

Yes, that's the function-type construction from Chapter 9. The hom-functor is "give me a target type, I'll give you the type of arrows into it from my fixed source."

Here it is, in code-shape. Pick any functor F (any F[_] with a working map). Then:

forall r. (A => r) => F[r]   ≅   F[A]

Read it slowly. On the right: a plain F[A], the thing you've been working with since Chapter 4. On the left: a function — and a very generic one. It says "give me any continuation A => r, and I'll produce an F[r]. For any r at all."

The lemma claims these two are the same. Equivalent. Interchangeable.

In plain English: if you can build an F[r] from any function A => r — uniformly in r — you actually have an F[A] hiding inside you.

This should feel shocking on first read. The left side looks enormous; it's making a promise about every type r simultaneously. The right side is a single concrete value. The Yoneda lemma says: the only way to fulfill that gigantic promise (parametrically — no peeking at r) is to already have an F[A] ready to map over.

Both directions are short. Let's walk them.

If you've got an fa: F[A] in hand, building the giant function is easy. For any k: A => r, just fa.map(k). Done. That's an F[r].

liftYoneda(fa)  =  [r] => (k: A => r) => fa.map(k)

This is the magical-feeling direction. You're handed a thing that promises, for any r, "give me A => r, I'll give you F[r]." How do you wring an F[A] out of it?

Specialize. Pick r = A. Now the promise reads: "give me A => A, I'll give you F[A]." So hand it the identity function x => x. Out pops your F[A].

lowerYoneda(y)  =  y[A](x => x)

The secret: the type forall r. (A => r) => F[r] is so generic — it can't look at r, can't invent values of r, can't do anything r-specific — that the only way to satisfy it (with a free theorem doing the heavy lifting) is to internally hold an F[A] and map the continuation over it. There's no other inhabitant.

Here's the lemma in pictures. Pick a value (we'll use the simplest functor, Identity — so F[A] = A). The left card is the value itself, 42. The right card is its Yoneda form: λ k. k(42) — a thing that's waiting for any observer function.

Now pick any observation. Apply it to both sides. The results match. That's the lemma — every observation factors through the value, and the Yoneda form just delays applying it.

A bigger consequence of the lemma is the Yoneda embedding. It says: send each object A to its hom-functor Hom(-, A). This sends the category into the category of functors.

The embedding is faithful and full — meaning two objects are isomorphic if and only if their hom-functors are. So:

A ≅ B  ⟺  Hom(-, A) ≅ Hom(-, B)

One-paragraph plain take: to know an object completely, it is enough to know how every other object maps into it. The "inside" of the object doesn't matter — what defines it is its pattern of incoming arrows. (Or, dually, its pattern of outgoing arrows; we'll see that in a moment.)

This is what justifies a whole class of programming tricks where you replace a data type with "the way to consume it" or "the way to produce it" and lose nothing. You see this in CPS, in church encodings, in free monads, in difference lists. All of them are Yoneda in disguise.

Three places programmers meet Yoneda without knowing it:

Apply the lemma to the identity functor (F[A] = A) and you get:

A  ≅  forall r. (A => r) => r

That's continuation-passing style. A plain value is "a thing that takes a continuation and feeds it the value." Every CPS transform you've ever seen — whether in a compiler or a node-callback API — is using this one specific instance of Yoneda.

Concatenating xs ++ ys on cons-lists walks the entire xs. Build a chain a ++ b ++ c ++ d and you re-walk earlier results over and over — quadratic time.

Trick: represent a list [a, b, c] as the function tail => [a, b, c] ++ tail. Now concatenation is function composition — instant. To get a real list back, apply to [] at the end.

That's the Yoneda transform for List. You replaced the list with "the way to prepend onto a tail" — same information, dramatically better algorithmic behavior.

The "Free monad" construction (you'll see this in cats-free, in Haskell's free package) uses a Yoneda trick to delay doing the map. Instead of mapping immediately when you call fmap, it stores up the function and only applies it when the program is finally interpreted. That's a real-world performance win in tree-shaped programs — and the construction is literally Yoneda f a wrapped around a free structure.

Any time you replace a data type with "the way to consume it" — Church encoding of natural numbers, Boehm-Berarducci encoding of lists, a class with a single visitor method — you're walking the Yoneda embedding. The data is gone; in its place is its pattern of outgoing arrows. The two are equivalent.

Worth doing once concretely. Start with 42. Chain three observations: +1, then ·2, then toString. In ordinary code we'd write ((42 + 1) * 2).toString. In CPS, each step receives the previous result and passes it forward to the next.

This is exactly the Yoneda lemma for the identity functor: 42 as "a thing that calls its continuation with 42".

One short paragraph and we're done. Flip every arrow and you get the dual lemma. Using Hom(-, A) (arrows into A) instead of Hom(A, -):

exists r. (r => A, F[r])  ≅  F[A]

Same content, mirrored. Where Yoneda gives you the "delayed map" representation, Co-Yoneda gives you the "map waiting to happen" representation: a pair of an F[r] and an unfinished arrow r => A. It's the construction behind reflection-free fmap in libraries like kan-extensions.

A Yoneda type, the two conversions, and a tiny CPS example. Notice how short lowerYoneda is — that's the identity trick in action.

You've now seen the most-cited result in category theory, and you've seen it as a programmer trick: replace any value with the pattern of its outgoing arrows and lose nothing. Next chapter pushes one level deeper — to the relationship that nearly every important construction in this whole series is secretly an instance of.