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 constructions of this chapter are categorical definitions.