From Adjunctions to Monads

I thought I would share one of my favorite constructions in Haskell, namely that adjoint functors give rise to monads. Although it’s a trivial result in category theory how it manifests in Haskell is quite lovely.

A Functor in Haskell maps objects and morphism (i.e. functions) in a subcategory of Hask to objects and morphisms of another category.

class Functor f where
  fmap :: (a -> b) -> f a -> f b

And satisfies the functor laws:

fmap id = id
fmap (a . b) = (fmap a) . (fmap b)

In commutative diagrams we draw objects as points and morphisms as arrows. In a string diagrams we invert this and draw morphisms as points and objects as lines.

Functor composition is defined for \(F : \mathcal{A} \rightarrow \mathcal{B}\), \(G : \mathcal{B} \rightarrow \mathcal{C}\) as \(G \circ F : \mathcal{A} \rightarrow \mathcal{C}\), and is drawn with parallel lines.

newtype FComp f g a = C { unC :: f (g a) }

instance (Functor f, Functor g) => Functor (FComp f g) where
  fmap f (C x) = C (fmap (fmap f) x)

Generally the composition of functors \(F \circ G\) is written simply as \(FG\). Composition diagrammatically allows us to collapse adjacent segments in our string diagram.

The identity functor ( \(\text{Id}\) ) is the functor that maps each morphism and object to itself.

newtype Id a = Identity { unId :: a }

instance Functor Id where
    fmap f x = Identity (f (unId x))

Composition with the identity functor forms an identity relation:

\[ F \circ \text{Id}_B = F \\ \text{Id}_A \circ F = F \]

As witnessed by the expressions:

left :: Functor f => FComp f Id a -> f a
left (C a) = fmap unId a

right :: Functor f => f a -> FComp f Id a
right a = C $ fmap Identity a

We’ll follow the convention to omit the identity functor, and it is shown as a dotted line in subsequent string diagrams.

A natural transformation in our context will be a polymorphic function associated with two Haskell functor instances f and g with type signature (Functor f, Functor g) => forall a. f a -> g a. Which could be written with the following type synonym.

type Nat f g = forall a. f a -> g a

The identity natural transform mapping a functor \(F\) to itself is written \(1_F\) and in Haskell is just (id). The composition of natural transformations follows the associativity laws, shown below:

The final interchange law states that we can chase the natural transformations through the functors horizontally or compose natural transformation between functors vertically and still arrive at the same result.

\[ (\alpha \beta) \circ (\alpha' \beta') = (\alpha \alpha') \circ (\beta \beta') \]

type NatComp f f' g g' = forall a. f' (f a) -> g' (g a)

vert :: (Functor f, Functor f', Functor g, Functor g') =>
         Nat f' g' -> Nat f g -> NatComp f f' g g'
vert a b x = a (fmap b x)

horiz :: (Functor f, Functor f', Functor g, Functor g') =>
          Nat f' g' -> Nat f g -> NatComp f f' g g'
horiz a b x = fmap b (a x)

By the interchange law horiz and vert must be interchangable under composition. For natural transformations a, b, a', b' in Haskell we have the equation:

(a . b) `vert` (a' . b') == (a `horiz` a') . (b `horiz` b')

A diagram example for a natural transformation \(\eta : 1_\mathcal{C} \rightarrow {FG}\) between the identity functor and the composition functor of \(FG\) would be drawn as:

An isomorphism \(F \cong G\) implies that composition of functors is invertible in that \(F G = \text{Id}_C\) and \(G F = \text{Id}_D\). An adjoint \(F ⊣ G\) between a pair of functors \(F : D \rightarrow C\) and \(G : C \rightarrow D\) is a weaker statement that there exists a pair of associated natural transformations \((F, G, \epsilon, \eta)\) with:

\[ \epsilon : FG \rightarrow 1_\mathcal{C} \\ \eta : 1_\mathcal{D} \rightarrow FG \]

Such that the following triangle identities hold:

\[ (\epsilon F) \circ (F \eta) = 1_F \\ (G \epsilon) \circ (\eta G) = 1_G \]

These are drawn below:

In terms of the categories \(C,D\) an adjoint is in some sense a “half-isomorphism” or “almost inverse” but some structure is lost in one direction.

\(\eta\) and \(\epsilon\) are also referred to respectively as the unit and counit.

In Haskell we have the following typeclass which unfortunately requires a functional dependency in order for type inferencer to deduce which fmap is to be used:

class (Functor f, Functor g) => Adjoint f g | f -> g, g -> f where
  eta     :: a -> g (f a)
  epsilon :: f (g a) -> a

There are also two other natural transformations (\(\phi, \psi\)) which together with the adjoint functor pair form an adjunction. The adjunction can be defined in terms of the adjoint pair and this is most convenient definition in Haskell

\[ \psi \epsilon = 1_F \\ \phi \eta = 1_G \]

phi :: Adjoint f g => (f a -> b) -> a -> g b
phi f = fmap f . eta

psi :: Adjoint f g => (a -> g b) -> f a -> b
psi f = epsilon . fmap f

Notably \(\phi\) and \(\psi\) form an isomorphism between the set of functions (a -> g b) and (f a -> b) which is the same relation as the above triangle identities. Alternatively \(\eta\) and \(\epsilon\) can be expressed in terms of \(\phi\) and \(\psi\).

phi eta = id
psi epsilon = id 

From the Haskell Prelude we have the canonical adjoint namely curry and uncurry:

\[ \text{curry} \quad ⊣ \quad \text{uncurry} \]

instance Functor ((,) a) where
  fmap f (x,y) = (x, f y)

instance Functor ((->) a) where
  fmap f g = \x -> f (g x)

Which we can construction an Adjoint instance from these two functor instances:

instance Adjoint ((,) a) ((->) a) where
  eta x y = (y, x)
  epsilon (y, f) = f y

We can check that the triangle equalities hold for this definition by showing both \((\epsilon F) \circ (F \eta)\) and \((G \epsilon) \circ (\eta G)\) reduce to the identity natural transformation ( id ).

a0 :: (a -> (b -> c)) -> a -> (b -> c)
a0 f = \f -> fmap (epsilon . fmap f) . eta
a0 f = fmap (\(y, f) -> g f y) . eta
a0 f = \x y -> f x y

a1 :: ((a, b) -> c) -> (a,b) -> c
a1 f = epsilon . fmap (fmap f . eta)
a1 f = epsilon . fmap (\x y -> f (y, x))
a1 f = \(x, y) -> f (x, y)

We know a Monad is an endofunctor \(T : C \rightarrow C\) with two natural transformations \((T, \mu, \eta)\) with the usual laws:

\[ \mu \circ T \mu = \mu \circ \mu T \\ \mu \circ T \eta = \mu \circ \eta T = 1_T \\ \]

The geometric intuition is that the monad laws are reflected as topological properties of the string diagrams. Both \(\mu\) and \(\eta\) exhibit reflection symmetry and that we topologically straighten out \(\eta\) to yield the identity functor.

In Haskell we can normally construct the Monad type class from an Endofunctor and (\(\mu, \eta\)) or join and return.

class (Functor t) => Monad t where
  eta :: a -> (t a)
  mu  :: (t (t a)) -> (t a)

  (>>=) :: t a -> (a -> t b) -> t b
  ma >>= f = mu . fmap f

return = eta
join = mu

What is not immediately apparent though is that every adjoint pair of functors gives rise to a monad \((T, \mu, \eta)\) over a category \(C\) induced by the composition of the functors to give rise to a endofunctor and natural transformations in terms of the unit and counit of the underlying adjunction:

\[ \begin{align} T &= G \circ F & : &C \rightarrow C \\ \mu &= G \epsilon & : &T^2 \rightarrow T \\ \end{align} \]

class Adjoint f g => Monad f g where
  muM :: g (f (g (f a))) -> g (f a)
  muM = fmap epsilon

  etaM :: a -> g (f a)
  etaM = eta

  (>>=) :: g (f a) -> (a -> g (f b)) -> g (f b)
  x >>= f = muM (fmap (fmap f) x)

The geometric intution for this is clear:

From the Monad we can then construct the Kleisli category in the usual way.

class (Adjoint f g, Category c) => Kleisli c f g where
  idK :: c x (g (f x))
  (<=<) :: c y (g (f z)) -> c x (g (f y)) -> c x (g (f z))

instance Monad f g => Kleisli (->) f g where
  idK = eta
  g <=< f = muM . fmap (fmap g) . f

instance Kleisli c f g => Monoid (c a (g (f a))) where
  mempty  = idK
  mappend = (<=<)

In retrospect this is trivial, but importantly leads us to the more important question: Can we recover an adjunction from a monad. The answer is Yes…