So far functions have been arrows between objects. What happens when a function itself can be an object in the category — something you can pass around, store, return? You get the categorical home of every functional language.
Every chapter so far has treated functions as movement — arrows connecting objects. Now the camera pulls back and a function becomes a thing in its own right. In Scala, (Int => String) is a type just like Int. You can put one in a list. Return one. Save one for later. We've been doing it for years. The question this chapter answers is: what makes a category support that move?
Here's the road map:
eval arrow — the only thing you can do with a function-as-object once you have one.In Scala you can write val parse: String => Int = _.toInt and from that point on, parse is just a value. You can stuff it in a List[String => Int], hand it to another function, pull it back out. The type String => Int is as real and first-class as Int itself. Haskell is the same — moreso.
So categorically, what is that type? It's not an arrow — there's no fixed pair of source and target it sits between when you're holding it as a value. It's an object. An object that remembers which arrow it represents. For each pair of objects A and B in a "nice enough" category, there might be another object — call it BA — whose elements are exactly the arrows from A to B.
That's the whole idea. The rest of the chapter just makes it precise.
Here's a magic isomorphism — one of the most useful facts in functional programming dressed up as a one-line equivalence:
(A, B) => C ≅ A => (B => C)
Read it: "a function of two arguments is the same as a function of one argument that returns a function of one argument." Either way of writing it carries exactly the same information. You can turn one into the other with no loss.
Scala calls the conversion .curried / Function.uncurried. Haskell goes the other way — every function is curried by default, and uncurry is the rare move. But it's the same isomorphism either direction.
Hit the toggle and watch the same function change costume.
Now we can name the object whose elements are arrows. For two objects A and B, the exponential object BA is "the type of all arrows from A to B." Other notations you'll see: [A, B], A ⇒ B, or — programmer-friendly — just (A => B).
Why "exponential"? Because for finite sets, it's literal arithmetic. The number of functions from a set with |A| elements to a set with |B| elements is |B||A|. You pick, independently, one output in B for each of the |A| inputs. That's exponentiation, plain.
Tiny example, callback to Chapter 2: how many functions Bool => Bool are there? Two inputs, two choices of output each, 22 = 4. They are: id, not, const(true), const(false). That's the entirety of BoolBool.
Drag the sliders to count, and for small cases enumerate every single function.
BA — base is the output, exponent is the input. That's the same order as the cardinality formula |B||A|. But the type spelled out reads input first: A => B. Same thing, opposite reading order.If BA is the object whose elements are all the functions from A to B, there has to be a way to use one. That's the eval arrow:
eval : BA × A → B
Read it: "take a function and a value of its input type, return the result of applying." In Scala that's the very last thing in (f, a) => f(a). In Haskell it's the ($) operator: f $ x = f x, or equivalently uncurry id.
eval is what makes function types useful. Without it, you'd have an object full of functions and no way to call any of them.
Time to gather what we've collected. A category is called cartesian closed — a CCC, in the literature — when it has three things:
1 — basically Unit from Chapter 2).The "closed" in the name is the third bullet — a category is closed when it's closed under taking function types. Make a function space; it's still in the category.
Why care? Because of one absurdly large fact, which I'll just state and let you sit with:
The lambda calculus is the internal language of any cartesian closed category.
That sentence connects logic, type theory, and category theory into a single object. Every typed lambda calculus term is a morphism in some CCC; every CCC supports a typed lambda calculus. The Curry–Howard–Lambek correspondence.
The programmer's take is simpler: Scala and Haskell live in (or close to) a CCC. That is why currying, partial application, and higher-order functions all just work. You're not getting away with anything — the category gives you those moves for free, by definition.
Let's pin it down with the most boring example imaginable. add(a, b) = a + b. Two integers in, one out.
The uncurried form takes a pair: add: (Int, Int) => Int. Call add(3, 4) and you get 7.
The curried form takes one argument at a time: addC: Int => Int => Int. Call addC(3) and you get back a function — specifically the function y => 3 + y. Call that with 4 and you finally get 7.
Two routes, same destination. That's the isomorphism. And the moment you have the curried form, you also have partial application for free: val addThree = addC(3). You've baked the first argument in and kept the rest of the function for later. This is one of the most useful single moves in all of programming.
f.curried and Function.uncurried(g). Haskell: curry and uncurry from Prelude. Haskell functions of multiple arguments are already curried — you have to opt out with uncurry to get the tupled form.Side by side. Notice Scala has to opt in to currying with .curried; Haskell makes you opt out with uncurry. Same isomorphism, different default.