User:Michiexile/MATH198/Lecture 7

Last week we saw what an adjunction was. Here's one thing we can do with adjunctions.

Now, let Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle U} be a left adjoint to Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle F} . We set Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle T = UF} . Then we have natural transformations

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mu: UFUF -> UF}

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mu_X = U \epsilon_{FX}}

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \iota: 1 -> UF}

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \iota_X = \eta_X}

such that Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mu} is associative and Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \iota} is the unit of Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mu} .

These requirements remind us of the definition of a monoid - and this is not that much of a surprise. To see the exact connection, and to garner a wider spread of definitions.

Algebraic objects in categories[edit]

We recall the definition of a monoid:

Definition A monoid is a set Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle M} equipped with an operation Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mu: M\times M\to M} that we call composition and an operation Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle e: 1\to M} that we call the identity, such that

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle M \circ 1_M \times M = M \circ M \times 1_M} (associativity)
Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle M \circ 1_M \times e = M \circ e\times 1_M = 1_M} (unity)

If we have a monoidal category - a category Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle C} with a bifunctor Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \otimes: C\times C\to C} called the tensor product which is associative (up to natural isomorphisms) and has an object Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle I} acting as a unit (up to natural isomorphisms) for the tensor product.

The product in a category certainly works as a tensor product, with a terminal object acting as a unit. However, there is often reason to have a non-commutative tensor product for the monoidal structure of a category. This makes the category a cartesian monoidal category.

For, say, abelian groups, or for vector spaces, we have the tensor product forming a non-cartesian monoidal category structure. And it is important that we do.

And for the category of endofunctors on a category, we have a monoidal structure induced by composition of endofunctors: Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle F\otimes G = F\circ G} . The unit is the identity functor.

Now, we can move the definition of a monoid out of the category of sets, and define a generic monoid object in a monoidal category:

Definition A monoid object in a monoidal category Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle C} is an object Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle M} equipped with morphisms Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mu: M\otimes M\to M} and Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle e: 1\to M} such that

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle M \circ 1_M \otimes M = M \circ M\otimes 1_M} (associativity)
Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle M \circ 1_M \otimes e = M \circ e\otimes 1_M = 1_M} (unity)

As an example, a monoid object in the cartesian monoidal category Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle Set} is just a monoid. A monoid object in the category of abelian groups is a ring.

A monoid object in the category of abelian groups, with the tensor product for the monoidal structure is a ring.

And the composition Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle UF} for an adjoint pair is a monoid object in the category of endofunctors on the category.

The same kind of construction can be made translating familiar algebraic definitions into categorical constructions with many different groups of definitions. For groups, the corresponding definition introduces a diagonal map Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \Delta: G\to G\times G} , and an inversion map Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle i: M\to M} to codify the entire definition.

One framework that formalizes the whole thing, in such a way that the definitions themselves form a category is the theory of Sketches by Charles Wells. In one formulation we get the following definition:

Definition A sketch Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle S = (G, D, L, K)} consists of a graph Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle G} , a set of diagrams Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle D} , a set Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle L} of cones in Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle G} and a set Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle K} of cocones in Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle G} .

A model of a sketch S in a category Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle C} is a graph homomorphism Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle G\to C} such that the image of each diagram in Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle D} is commutative, each of the cones is a limit cone and each of the cocones is a colimit cocone.

A homomorphism of models is just a natural transformation between the models.

We thus define a monad in a category Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle C} to be a monoid object in the category of endofunctors on that category.

Specifically, this means:

Definition A monad in a category Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle C} is an endofunctor Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle T: C\to C} equipped with natural transformations Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mu: T^2\to T} and Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \eta: 1\to T} such that the following diagrams commute:

We can take this definition and write it out in Haskell code, as:

class Functor m => MathematicalMonad m where  
  return :: a -> m a
  join   :: m (m a) -> m a

-- such that
join . fmap return = id               :: m a -> m a
join . return      = id               :: m a -> m a
join . join        = join . fmap join :: m (m (m a)) -> m a

Those of you used to Haskell will notice that this is not the same as the Monad typeclass. That type class calls for a natural transformation (>>=) :: m a -> (a -> m b) -> m b (or bind).

The secret of the connection between the two lies in the Kleisli category, and a way to build adjunctions out of monads as well as monads out of adjunctions.

Kleisli category[edit]

We know that an adjoint pair will give us a monad. But what about getting an adjoint pair out of a monad? Can we reverse the process that got us the monad in the first place?

There are several different ways to do this. Awodey uses the Eilenberg-Moore category which has as objects the algebras of the monad Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle T} : morphisms Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle h: Tx \to x} . A morphism Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f: (\alpha: TA\to A)\to (\beta: TB\to B)} is just some morphism Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f:A\to B} in the category Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle C} such that Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f\circ\alpha = \beta\circ T(f)} .

We require of Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle T} -algebras two additional conditions:

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 1_A = h\circ\eta_A} (unity)
Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle h\circ\mu_A = h \circ Th} (associativity)

There is a forgetful functor that takes some Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle h} to Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle t(h)} , picking up the object of the Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle T} -algebra. Thus Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle U(h:TA\to A) = A} , and Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle U(f) = f} .

We shall construct a left adjoint Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle F} to this from the data of the monad Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle T} by setting Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle FC = (\mu_C: T^2C\to TC)} , making Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle TC} the corresponding object. And plugging the corresponding data into the equations, we get:

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 1_{TC} = \mu_C\circ\eta_{TC}}
Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mu_C\circ\mu_{TC} = \mu_C\circ T\mu_C}

which we recognize as the axioms of unity and associativity for the monad.

By working through the details of proving this to be an adjunction, and examining the resulting composition, it becomes clear that this is in fact the original monad Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle T} . However - while the Eilenberg-Moore construction is highly enlightening for constructing formal systems for algebraic theories, and even for the fixpoint definitions of data types, it is less enlightening to understand Haskell's monad definition.

To get to terms with the Haskell approach, we instead look to a different construction aiming to fulfill the same aim: the Kleisli category:

Given a monad Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle T} over a category Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle C} , equipped with unit Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \eta} and concatenation Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mu} , we shall construct a new category Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle K(T)} , and an adjoint pair of functors Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle U,F} factorizing the monad into Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle T=UF} .

We first define Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle K(T)_0 = C_0} , keeping the objects from the original category.

Then, we set Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle K(T)_1} to be the collection of arrows, in Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle C} , on the form Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle A\to TB} .

The composition of Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f: A\to TB} with Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle g: B\to TC} is given by the sequence Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle A\to^f TB\to^{Tg} T^2C\to^{\mu_C} TC}

The identity is the arrow Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \eta_A: A\to TA} . The identity property follows directly from the unity axiom for the monad, since Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \eta_A} composing with Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mu_A} is the identity.

Given this category, we next define the functors:

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle U(A) = TA}
Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle U(f: A\to TB) = TA\to^{Tf} T^2B\to^{\mu_B} TB}

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle F(A) = A}
Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle F(g: A\to B) = A\to^{\eta_A} TA\to^{Tg} TB}

This definition makes Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle U, F} an adjoint pair. Furthermore, we get

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle UF(A) = U(A) = TA}
Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle UF(g: A\to B) = U(Tg\circ\eta_A) = \mu_B\circ T(Tg\circ\eta_A)}

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle =\mu_B\circ T^2g \circ T\eta_A} , and by naturality of Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mu} , we can rewrite this as

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle =Tg \circ \mu_A\circ T\eta_A = Tg\circ 1_{TA} = Tg} by unitality of Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \eta} .

We've really just chased through this commutative diagram:

Hence, the composite Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle UF} really is just the original monad functor Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle T} .

But what's the big deal with this? you may ask. The big deal is that we now have a monad specification with a different signature. Indeed, the Kleisli arrow for an arrow f :: a -> b and a monad Monad m is something on the shape fk :: a -> m b. And the Kleisli factorization tells us that the Haskell monad specification and the Haskell monad laws are equivalent to their categorical counterparts.

And the composition of Kleisli arrows is easy to write in Haskell:

f :: a -> m b
g :: b -> m c

(>>=) :: m a -> (a -> m b) -> m b -- Monadic bind, the Haskell definition

kleisliCompose f g :: a -> m c
kleisliCompose f g = (>>= g) . f

Examples[edit]

Some monads in Haskell are:

The List monad[edit]

Lists form a monad, with the following (redundant) definition:

instance Monad [] where
  return x     = [x]

  [] >>= _     = []
  (x:xs) >>= f = f x : xs >>= f

  join [] = []
  join (l:ls) = l ++ join ls

As it turns out, the lists monad can be found by considering the free and forgetful functors between sets and monoids. Indeed, the lists are what we get from the Kleene star operation, which is the monad we acquire by composing the free monoid functor with the forgetful functor.

Error handling[edit]

We can put a monadic structure on a coproduct Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle A+B} so that the monadic bind operation performs computations Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle A+B\to A'+B} until some computation fails, returning an error, typed Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle B} , after which we bypass any further computations, just carrying the error out of the entire computation.

The endofunctor here is Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle +B} . So the monad is given from a way to go from Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle A+B+B\to A+B} . Doing this is easy: in Haskell terms, we just remove the constructor differences between the two copies of Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle B} floating around. Mathematically, this is just using the functoriality of the coproduct construction on the inclusion maps into Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle A+B} .

For our example, we shall return the first value of Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle B} to ever occur, thus making our join operator look like this:

join :: (Either b (Either b a)) -> Either b a
join (Left y) = Left y
join (Right (Left y)) = Left y
join (Right (Right x)) = Right x

This gives us a Haskell monad defined by:

instance Monad (Either b) where
  return x = Right x

  Left y  >>= _ = Left y
  Right x >>= f = f x

Additional reading[edit]

http://blog.sigfpe.com/2006/08/you-could-have-invented-monads-and.html (one of the least dramatic monads tutorials out there)
http://www.disi.unige.it/person/MoggiE/ftp/lc88.ps.gz (Moggi: Computational lambda-calculus and monads, one of the papers that started the interest in monads. Logic, dense reading.)
http://www.haskell.org/haskellwiki/Research_papers/Monads_and_arrows (good catalogue over further reading on monads)

Homework[edit]

Full marks will be given for 4 out of the 7 questions.

Prove that the Kleisli category adjunction is an adjunction.
Prove that the Eilenberg-Moore category adjunction is an adjunction.
Given monad structures on Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle S} and Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle T} ,
The writer monad
W is defined by
- data Monoid m => W m x = W (x, m)
- fmap f (W (x, m)) = W (f x, m)
- return x = W (x, mempty)
- join (W (W (x, m), n)) = W (x, m `mappend` n)
1. (2pt) Prove that this yields a monad.
2. (2pt) Give the Kleisli factorization of the writer monad.
3. (2pt) Give the Eilenberg-Moore factorization of the writer monad.
4. (2pt) Is there a nice, 'natural' adjunction factorizing the writer monad?