Categories

There is a branch of mathematics — category theory — and it fits what we are discussing like nothing else, so we simply have to talk about it a little. The idea at its core is defiantly simple: forget what lies inside mathematical structures and look only at the connections between them. The theory works with just two kinds of entities. The first are objects: $A, B, C, \dots$; what they actually are, the category does not care. The second are morphisms, also known as arrows: each has a source and a target, $f : A$ $\to B$.

Arrows can be glued together: for example, for $f : A$ $\to B$ and $g : B$ $\to C$ the composition $g \circ f : A$ $\to C$ is defined. Then come two axioms. First: composition is associative, $h \circ (g \circ f)$ $= (h \circ g) \circ f$. Second: every object has an identity arrow $\mathrm{id}_A : A$ $\to A$, neutral with respect to composition: $f \circ \mathrm{id}$ $= \mathrm{id} \circ f$ $= f$. Objects, arrows and two axioms — that is what a category is.

In Haskell this pattern is captured in a type class — $\mathtt{Category}$ from the $\mathtt{Control.Category}$ module:

class Category cat where
  id  :: cat a a
  (.) :: cat b c -> cat a b -> cat a c

-- the class laws are exactly the category axioms:
f . id == f
id . f == f
(f . g) . h == f . (g . h)

Here $\mathtt{cat}$ is the arrow itself, parameterised by source and target (kind $*$ $\to *$ $\to *$). Frankly, the most all-embracing instance of a category is $Hask$: objects are Haskell types, morphisms are functions between them, composition is $\mathtt{(.)}$ from the Prelude, the identity is $\mathtt{id}$:

instance Category (->) where
  id x = x
  (g . f) x = g (f x)

show   :: Int -> String      -- a morphism Int -> String
length :: String -> Int      -- a morphism String -> Int

length . show :: Int -> Int  -- their composition is a morphism too

The real value of category theory for us is that every construction we discussed in this chapter can be stated in its language very cleanly and crisply:

• monoid — a category with a single object: the morphisms are the elements of the monoid, $(\mathbin{\mathtt{<>}})$ is the composition, $\mathtt{mempty}$ is the identity;
• functor — a mapping from category to category: objects go to objects, arrows go to arrows, and identity and composition are preserved (these are exactly the $\mathtt{fmap}$ laws); our functors map $Hask$ into itself, which is why they are called endofunctors — the prefix “endo-” is Greek for “within”: a functor from a category into that very category;
• applicative functor — a monoidal functor: besides arrows it also carries pairs across, $\mathtt{liftA2}\;(,)$ glues $(f\,a,\;f\,b)$ into $f\,(a,\,b)$, and $\mathtt{pure}$ provides the unit;
• monad — the category of Kleisli arrows $a$ $\to m\,b$ with composition $(\mathbin{\mathtt{>=>}})$ and identity $\mathtt{pure}$;
• Foldable — a fold into a category with a single object: $\mathtt{foldMap}$ carries the elements of the structure into a monoid and glues them there;
• Traversable — swapping two endofunctors around: $\mathtt{sequenceA} \mathbin{\mathtt{::}} t\,(f\,a)$ $\to f\,(t\,a)$.

The point about the monad can be touched with your hands: the Kleisli category is a newtype wrapper with a $\mathtt{Category}$ instance:

newtype Kleisli m a b = Kleisli { runKleisli :: a -> m b }

instance Monad m => Category (Kleisli m) where
  id                    = Kleisli pure
  Kleisli g . Kleisli f = Kleisli (f >=> g)

-- the familiar half — now as a Kleisli arrow:
half :: Kleisli Maybe Int Int
half = Kleisli (\x -> if even x then Just (x `div` 2) else Nothing)

quarter :: Kleisli Maybe Int Int
quarter = half . half          -- an ordinary dot glued effectful arrows together

runKleisli quarter 12   -- Just 3
runKleisli quarter 6    -- Nothing   (3 is odd — the second halving failed)

Checking the $\mathtt{Category}$ laws for this instance means checking the monad laws: the identity $\mathtt{pure}$ and the associativity of $(\mathbin{\mathtt{>=>}})$ we have already seen in the section on Kleisli arrows. A monad and its Kleisli category can be recovered from each other: they are one construction written down in two ways.

We arrived at Haskell along the path of the λ-calculus: terms, reductions, types. But one could come from the other side as well: the typed λ-calculus and cartesian closed categories are one and the same subject in two languages. Then types are objects, programs are morphisms, and the monoids, functors and monads of this chapter are not Haskell inventions but notions of category theory, carried over into code almost verbatim.