Functors — λ-calculus

Consider a list of natural numbers and a list of strings. Their element types differ, but the list structure and its structural operations remain the same. Let $\mathtt{T}$ denote the element type: the $\mathtt{List}$ constructor takes it and produces the concrete type $\mathtt{List\;T}$ . Therefore, the kind of $\mathtt{List}$ is $\mathtt{* \to *}$ .

A C++ programmer may reasonably point out that the templates $\mathtt{std::vector}\langle \mathtt{T} \rangle$ and $\mathtt{std::list}\langle \mathtt{T} \rangle$ already abstract over the element type, while iterators and ranges let the same algorithms work with different structures, such as lists and trees. Those algorithms, however, abstract over the traversal interface of an existing object rather than over a type constructor that preserves the shape of a context.

Haskell takes the next step. Both $\mathtt{List}$ and $\mathtt{Tree}$ have kind $\mathtt{* \to *}$ , so the $\mathtt{Functor}$ type class can abstract over the constructor $\mathtt{f}$ itself. The $\mathtt{fmap}$ operation takes a function $\mathtt{a \to b}$ , transforms values inside $\mathtt{f\;a}$ , and returns $\mathtt{f\;b}$ while preserving the shape of the context. This is polymorphism not only over the element type but also over the context constructor. C++ can emulate it with templates and overloads, but the language has no direct standard counterpart to type classes and uniform higher-kinded polymorphism. The type class itself is declared as follows:

class Functor f where
  fmap :: (a -> b) -> f a -> f b   -- apply a function inside context f

In this declaration, $\mathtt{f}$ is a variable for a type constructor of kind $\mathtt{* \to *}$ , not for a concrete type. The class specifies the common shape of $\mathtt{fmap}$ , while each instance defines how its context is preserved. The standard instances for lists and $\mathtt{Maybe}$ work as follows:

instance Functor [] where
  fmap _ []       = []
  fmap g (x : xs) = g x : fmap g xs

instance Functor Maybe where
  fmap _ Nothing  = Nothing
  fmap g (Just x) = Just (g x)

As we can see, a $\mathtt{Functor}$ implementation depends on the context constructor but not on the concrete type of its elements. Now let us place the number 2 in a context. We begin with the key idea: a value in a context.

A plain value 2, a value in the context Just 2, and the empty context Nothing — **Fig. 2.3.** A plain value and a value in the $\mathtt{Maybe}$ context: the “box” may contain a value ( $\mathtt{Just\;2}$ ) or be empty ( $\mathtt{Nothing}$ ).

A context lets us define the rules for exceptional cases once and then apply ordinary functions without scattering checks throughout an algorithm. More powerful abstractions built on this idea can chain computations and specify execution strategies, but $\mathtt{Functor}$ itself guarantees only transformation through $\mathtt{fmap}$ . Suppose a JavaScript computation returns $\mathtt{undefined}$ instead of a value. We then have to write an $\mathtt{if}$ ; if the result is passed onward, such checks begin to spread through the algorithm. Haskell represents absence explicitly with $\mathtt{Maybe}$ : its $\mathtt{Functor}$ instance leaves $\mathtt{Nothing}$ unchanged and applies the function to the value inside $\mathtt{Just}$ . Mapping over an empty list likewise returns an empty list. An ordinary function can be applied directly to a plain value; a value in a context would first have to be unpacked by hand. $\mathtt{fmap}$ takes care of that:

fmap applies a function inside a context: Just 2 becomes Just 5, Nothing remains Nothing, and a list is mapped element by element — **Fig. 2.4.** $\mathtt{fmap}$ applies a function to the value inside a context while preserving the context itself: an empty box stays empty, and a list is mapped element by element.

fmap (+3) (Just 2)   -- Just 5
fmap (+3) Nothing    -- Nothing

$\mathtt{fmap}$ has an infix synonym: $g \mathbin{\mathtt{<\$>}} x$ $= \mathtt{fmap}\;g\;x$ .

Every instance must obey two laws: identity and composition.

fmap id == id                     -- identity
fmap (g . h) == fmap g . fmap h   -- composition

These laws mean that $\mathtt{fmap}$ changes values but not the shape of the context: it neither rearranges a list nor turns $\mathtt{Just}$ into $\mathtt{Nothing}$ . They also state that mapping two functions in sequence is equivalent to mapping their composition.

The main instances:

-- Maybe: the value may be absent
fmap (+3) (Just 2)       -- Just 5

-- A list: zero or more values; fmap = map
fmap (+3) [1, 2, 3]      -- [4, 5, 6]

-- Either e: only Right is mapped
fmap (+3) (Right 2)      -- Right 5
fmap (+3) (Left "oops")  -- Left "oops"

A functor is a mapping between categories that preserves $\mathtt{id}$ and composition. In the usual model of Haskell, functors are endofunctors on the category of types and functions, and the $\mathtt{fmap}$ laws correspond exactly to the functor axioms.