Functors and natural transformations

Lesson 07 handed us a vocabulary: a category is objects plus morphisms that compose associatively and have identities, and types-and-functions form one. It also planted a promise — that functor, monoid, and monad are just named patterns with a law or two. This lesson cashes the first one. A functor is the first named pattern, and it answers a question you have hit a hundred times without naming it: I have a plain function A => B (Lesson 05) and a value sitting inside a context — an Option[A], a List[A], a future result — and I want to apply the function to the inside without tearing the context open by hand. That operation is map, the pattern is the functor, and its two laws are exactly Lesson 07's "lawful = safe to refactor," made specific.

1 · The motivating problem: a function, and a value behind glass

You have a perfectly ordinary pure function from Lesson 05 — say def double(n: Int): Int = n * 2, a morphism Int => Int. And you have a value, but it is not a bare Int; it is wrapped in a context that records something about it:

val maybe: Option[Int] = Some(21)   // context: "this might be absent"
val many:  List[Int]   = List(1, 2, 3)  // context: "there are zero or more of these"

You want to apply double to the value inside. The clumsy way is to break the glass — unwrap, apply, rewrap — and you must handle every shape the context can take:

val doubled: Option[Int] = maybe match {
  case Some(n) => Some(double(n))   // unwrap, apply, rewrap
  case None    => None              // ...and handle the empty case by hand
}

That works, but notice what it costs: you wrote code about the container (the match, the two cases) just to do one thing to the contents. Do it for List and you write a loop; for a future result you write a callback. Each container forces its own boilerplate, and that boilerplate is exactly the kind of tangled control flow Lesson 00 named as a source of complexity. The functor is the observation that all of these are the same operation — "apply a function to the inside, leaving the context intact" — and that the container can implement it once so you never write the unwrap/rewrap dance again.

2 · A functor is a context F[_] plus map

A functor is two things together. First, a type constructor F[_]: not a type by itself, but a one-argument type-level function that, given a type A, produces a type F[A]. Option, List, and (with one type fixed) Either are all type constructors — Option[Int] is a type, Option alone is the constructor. Second, an operation

that takes a value in the context and a plain function A => B, and returns a value in the same context with the function applied inside. In Scala this lives as a method, so you write fa.map(f):

Some(21).map(double)        // Some(42)        — Some stays Some
(None: Option[Int]).map(double)  // None       — None stays None
List(1, 2, 3).map(double)   // List(2, 4, 6)   — length 3 stays length 3

The single most important intuition, the one that separates map from everything else: map changes the values, never the structure. An Option stays the same shape it was — Some stays Some, None stays None; map cannot turn a present value absent or invent one. A List keeps its exact length and order; you get one output element per input element. The context is preserved; only what is inside is transformed. Hold onto that — most beginner errors with functors are an unconscious belief that map can reshape the container, and it cannot.

3 · The two functor laws — and why they let you refactor

"Provides a map method" is not quite enough; map must be well-behaved. A functor is required to satisfy two laws. They look like bookkeeping; they are in fact the whole reason the pattern is trustworthy.

Identity law — mapping the do-nothing function changes nothing:

Composition law — mapping f then g equals mapping their composite once:

Here identity is Lesson 05's x => x, and g ∘ f is Lesson 07's composition — "do f, then g" — which in Scala is f andThen g. Let us actually check them, because an abstract law you have never verified is just a slogan.

List(1,2,3).map(_ + 1)   // List(2, 3, 4)   — first pass
           .map(_ * 2)   // List(4, 6, 8)   — second pass

List(1,2,3).map(x => (x + 1) * 2)   // List(4, 6, 8)

Now Option, where the empty case is the interesting one. For Some(21): Some(21).map(_ + 1).map(_ * 2) is Some(22).map(_ * 2) = Some(44), and Some(21).map(x => (x + 1) * 2) is also Some(44). For None: both routes give None, because map on None never calls the function at all — the composition law holds vacuously and the structure is preserved. The identity law is just as direct: Some(21).map(identity) == Some(21) and None.map(identity) == None.

Why do these dry equations matter? Because the composition law is exactly the license to fuse two maps into one. That is two things at once. It is an optimization: a compiler or you can replace two traversals of a million-element list with one, knowing the result is identical. And it is a refactoring guarantee: you can split one tangled map into two readable ones, or merge two into one, and the program's meaning is unchanged — by law. This is Lesson 07's thesis ("lawful structures are safe to refactor") made completely concrete. A type with a map that violated these laws would be a trap: equivalent-looking edits would silently change behavior.

4 · The category-theory reading, kept light

Lesson 07 said a functor is a structure-preserving map between categories; we can now see that is the very same thing. A functor F does two jobs. It sends each type to a type — A goes to F[A] (objects to objects). And it sends each function to a function — a morphism f: A => B goes to a morphism F[A] => F[B], which is precisely what map(f) is. To call that "structure-preserving," F must respect the two pieces of structure a category has: identities and composition. "Respect identities" is the identity law; "respect composition" is the composition law. So the two laws are not extra fine print bolted onto map — they are the definition of a functor as a map of categories, restated in code. That is the whole bridge from the abstract chapter to the concrete tool.

5 · A Scala Functor trait (a peek at type classes)

So far "functor" has been a property that Option and List happen to have. We can also name the pattern as a thing in the language — a trait capturing "an F[_] that knows how to map" — and then provide an instance per container. This is a preview of type classes (Lesson 14); read it as a sketch of the idea, not the final form.

// "F[_] is a functor" = it can map a plain function through the context.
trait Functor[F[_]] {
  def map[A, B](fa: F[A])(f: A => B): F[B]
}

// Instance: Option is a functor.
val optionFunctor: Functor[Option] = new Functor[Option] {
  def map[A, B](fa: Option[A])(f: A => B): Option[B] = fa match {
    case Some(a) => Some(f(a))   // present: apply inside, rewrap
    case None    => None         // absent: nothing to do; shape preserved
  }
}

// Instance: List is a functor.
val listFunctor: Functor[List] = new Functor[List] {
  def map[A, B](fa: List[A])(f: A => B): List[B] = fa match {
    case head :: tail => f(head) :: map(tail)(f)  // one output per input
    case Nil          => Nil                       // length preserved
  }
}

Writing it out makes the laws visible in the code: each instance has exactly one clause per shape the container can take, and every clause reconstructs the same shape (Some→Some, None→None, a cons-cell per cons-cell). That structural mirroring is why the laws hold. Either[E, _] is a functor in the same way — map transforms the Right and leaves a Left untouched — which is the seed of the typed-failure story in Lesson 11.

6 · Natural transformations: moving between functors, lawfully

map stays inside one functor and changes the element type. The dual move is to change the functor while keeping the element type fixed. A natural transformation is a structure-preserving conversion F[A] => G[A] that works for all A with the same logic. The canonical example converts an Option into a List:

def optionToList[A](oa: Option[A]): List[A] = oa match {
  case Some(a) => List(a)   // one element
  case None    => Nil       // empty list
}

It is "natural" because the rule (None→Nil, Some(a)→List(a)) does not peek at what A is; it depends only on the shapes, so it works uniformly for Option[Int], Option[String], anything. The lawful condition — the naturality condition — says, informally: it does not matter whether you transform the contents first and then convert the container, or convert the container first and then transform the contents. In symbols, optionToList(oa.map(f)) == optionToList(oa).map(f). Check it: for Some(3) and f = (_ * 2), the left side is optionToList(Some(6)) = List(6); the right side is optionToList(Some(3)).map(_ * 2) = List(3).map(_ * 2) = List(6). They agree — the conversion commutes with map, which is what makes it a structure-preserving bridge between the two functors rather than an arbitrary function.

Common mistakes / failure modes

Checkpoint exercise

Where this points next

A functor lets you transform values inside one context, one element at a time, with the shape held fixed. But it gives you no way to combine two values into one — to add the numbers in a list, to concatenate strings, to collapse many results into a single answer. That is a separate, equally fundamental pattern with its own laws. Lesson 09 introduces the monoid: a set with an associative combining operation and an identity element (think +/0, concatenation/"", List/Nil). Its associativity law is what lets a fold collapse a whole structure in any grouping — and, later, in parallel (Lesson 13). A note on the ladder, so you read it accurately: the monad (Lesson 10) does not consume the monoid's combine — it is built from the functor's map plus a new operation, flatMap. What the monad borrows from the monoid is the associativity law: meeting associativity here, on combine, is what makes the monad's third law feel familiar rather than new. Read 08 → 09 → 10 as three named patterns each with a law, not three parts bolted into one machine.

Interview prompts

• What is a functor, in plain terms? (§2 — a type constructor F[_] plus a lawful map[A,B](fa: F[A])(f: A => B): F[B] that applies a function to the value inside a context without disturbing the context's shape.)
• What does map change, and what can it never change? (§2 — it changes only the element values, via the supplied function; it never changes the structure: Some/None stay as they are and a list's length and order are preserved.)
• State the two functor laws and check one on a small value. (§3 — identity: fa.map(identity) == fa; composition: fa.map(f).map(g) == fa.map(g ∘ f). On List(1,2,3) with +1 then *2, both routes give List(4,6,8).)
• Why does the composition law matter in practice? (§3 — it licenses fusing two maps into one (or splitting one into two) without changing meaning: an optimization (one traversal instead of two) and a refactoring guarantee, i.e. Lesson 07's "lawful = safe to refactor".)
• How is a functor "a map between categories"? (§4 — it sends types to types (A => F[A]) and functions to functions (map(f): F[A] => F[B]), and the two laws are exactly "preserves identity" and "preserves composition".)
• What is a natural transformation, and how does it differ from map? (§6 — a uniform conversion F[A] => G[A] for all A that commutes with map (e.g. Option => List): it changes the container with the element type fixed, whereas map keeps the container and may change the element type.)
• You want to drop some elements while transforming a list — is that map? (§2, common mistakes — no; map preserves length and cannot drop, add, or flatten. That is filter or flatMap (Lesson 10), not a functor map.)