Maths - Category Theory - Monad

A monad is an important concept in mathematics. It is a pattern that occurs in many branches of mathematics. To take just one example, in vector spaces, imagine that we want to calculate the result of doing a sequence of finite rotations of a solid body in 3D space. Each finite rotation is an endofunction from vector space to itself and the results of any sequences of rotations can be calculated using two algebras: an algebra which represents the 3D transformations as elements (such as matrix or quaternion) and combines them using multiplication and an algebra that calculates the movement of points given any 3D transformation.

In general a monad can relate an algebraic theory to function composition.

It also has applications outside mathematics. In computing, for instance in the language Haskell, a monad can convert imperative code into pure functional code.

The power of this monad concept is not always apparent (to me at least) from the definition so, after giving the technical definition, we will look at various ways to approach this topic to get a more intuitive understanding.

Technical Definition

A monad T = <T,η,µ> on a category C consists of

  • an endofunctor T on C
    • T: C → C
  • and two natural transformations:
    • a unit η: 1 → T
    • a multiplication µ: T² → T

Natural transformations are explained on this page.

monad concept

These natural transformations must obey the following axioms, that is the following diagrams must commute:

associative square:   unit triangles:
monad square   monad triangle
The associative square says that we can multiply on the right first (IdT×µ) or on the left first (µ×IdT) and the result is the same.   The unit triangles say that we can insert the unit on the right first (IdT×η) or on the left first (η×IdT) and in each case when we multiply we get back to where we started..

Note that in these diagrams:

  • 'x' means do natural transformations in parallel. (see bifunctor)
  • 'T' is a functor (shown in red) In some text books IdT is denoted T (shown in blue). Denoting an identity by the name of the object is a common convention and there should be no ambiguity if we know something is an object, functor or natural transformation.

Monad in terms of Components

When working with monads, especially if we are modeling them in a computer program, it can be complex to model natural transformations with a form like:
(x -> y) -> (z -> w) so it can be more practical to model in terms of the components at 'a'.

In the above diagrams points represent functors and arrows represent natural transformations. However we can go back to more conventional diagrams by taking the component at 'a'. This means that:

So, for example, the endofunctor for a list monad generates a sequence of types: a, List a, List List a ... list endo functor

The axioms become:

monad square

  monad triangle

Note that:

The functors become the nodes of the diagram and the natural transformations become the arrows.

Ways to think about Monads

It seems to me that any really powerful idea in mathematics has many ways to approach it and we only feel that we have an intuitive understanding of the concept when we can understand several of these approaches. We could look a monads as:

We will look at each of these in more detail later.

First lets look at how the concept can be built up from the concept of an endofunction.

Monad from Endofunction

An endofunction is a function whose codomain is equal to its domain. That is a function from a type to the same type. cross product

For example:

•doubleIt(int a):int = 2*a
•addthree(int a):int = a+3

These functions both have type int->int, that is: they are endofunctors.

One advantage of this is that we can chain together a sequence of such functions, effectively allowing us to compose fragments of computation in many ways.

Natural Transformations

The above endofunctor can be made even more powerful by adding two 'natural transformations'. These are mappings between the endofunctors.

So, in the above example:

Multiplication

The first natural transformation that we want to add is called 'multiplication' (although this does not correspond to the multiplication of the underlying type 'int').

Imagine that we enhance the above endofunctor by adding the following:

doubleItandaddthree(int a):int = 2*a+3

We now have a relationship within the endofunctor

doubleItandaddthree = doubleIt • addthree

where: • means do the left hand side first then do the right hand side.

This has type: (int->int) • (int->int) -> (int->int)

but we can Curry '•' into '->' .

So we have a new operation called 'multiplication' although it has different properties from the multiplication of the underlying type 'int'.

Unit

We also want to add a second natural transformation which introduces this function:

donothing(int a):int = a

That is a function that does nothing (it maps 1 to 1 and 2 to 2 and so on) but that has a signature of: int->int so it is not a natural transformation.

'Unit' is a natural transformation with signature:

()->(int->int)

That is it introduces our donothing function from something without any parameters.

Again, this 'unit' natural transformation is not the same as the identity element of either of the operations of the underlying 'int' type.

Monad

So, in the above example, we have used endofunctors to introduce a completely new algebra from a known one (int).

More Complicated Monads

The examples that we have given so far are a simple type of monad where the endofunctor takes us back to exactly the same type (which is what we expect with an endofunction). Now we consider a more general monad where the endofunctor maps, not back to the same type, but to a different (but related) type.

So here we are generalising the situation by lifting up from endofunctions to endofunctors.

List Example

A simple example of this is 'List' (at least programmers call it 'list', mathematicians may call it 'word') which is a functor which maps:

Applying the functor twice would map int to List List int, that is, a list of lists. The multiplication µ can, for instance, be 'flatten' which just removes the inner brackets, that is, it flattens the structure.

Generalising

It is not necessary to stay with the situation where our composed functions map from a type back to the same type. endofunction
We can instead have a whole sequence of types formed by an endofunctor. We still have an infinitely composible sequence but each type in the sequence is a different type. endofunctor

An example of this is the 'list' monad:

list monad

Monad in Terms of Sets

As when we started looking at category theory, on this page, we can start looking at the concept of monads in terms of sets and then generalise to categories.

monad set 1 We start with a set which contains elements such as a,b & c, it may also contain subsets which themselves consist of elements like these and subsets of subsets and so on.
monad set Imagine that we have some mapping 'm' that maps say a->a' (or in a different notation a -> m a)
monad set Now imagine that b and c are also compatible with this mapping so we can add similar maps b->b' and c->c' and so on.
monoid set

It would be useful to be able to avoid the need to iterate over the elements and map them individually. We can map the whole set as a complete object provided that:

M {a,b,c} = {m a,m b,m c}

Usually in mathematical terminology we don't make a distinction between M and m, we use the same symbol regardless of whether we are mapping elements or whole subsets.

monad set

We can add two functions:

  • unit: maps 'a' to a set (a subset inside the main set) containing a.
  • join: maps 'a set containing a' to a.

So 'unit' and 'join' are inverses.

monad set In the same way that we can use 'M' to map elements or whole sets we can use 'unit' and 'join' to map elements, sets or mappings. So here 'unit' and 'join' represent mappings of mappings. In fact they are natural transformations.

In Terms of Components

Above I tried to draw the monad to show the endofunctor external to C. We might get a clearer impression if we draw the components like this: monad concept 2

So C is a category with components (objects or, if C is a set, elements) such as x.

  • T is an endofunctor from C to C
  • T² is T applied twice round the loop.
  • 1 is a particular case of T which does not change C (isomorphism)

 

The two natural transformations are:

name:
symbol:
unit
η: 1 → T
where η is the lower case greek letter: Eta
multiplication or join
µ: T² → T
where µ is the lower case greek letter: Mu

When programming in Haskell µ is called 'join' instead of 'multiplication'.

Note that, in some cases η is the inverse of µ, although it only goes from higher powers to T, it does not go back to 1.

Monads and Algebras

This is explained on this page. monad algebras

Examples of Monad

Vector Space: {formalℜ-linear combinations ∑ λi vi } V
(explaned on this page)
monad vector space
   
   

 

monad example In this example F is the forgetful functor which removes the structure from a group and makes it into a set, G adds structure to a set to make it into a free group.
   

x

Example

category C

and its endofunctor

Kleisli Eilenberg-Moore

monoid

(see this site)

monoid endofunctor
objects: N
arrows: succ

monoid kleisli
objects: N
arrows: N->succ N

objects: succ
arrows: succ->succ

finite group

(see Saunders Mac Lane 2nd ed p141)

  group endofunction  

vector space

(see this page)

vector space endofunctor   product combines transformations such as rotation

list

µ = flatten

objects: X,TX,TTX...
arrows: T
objects: X,TX,TTX...
arrows: X->T X

objects: T
arrows: T -> T T

applying µ gives: T -> T

program program endofunctor    

cat on set

(see this site)

     
       
       
       

Applications of Monad for Programming

In a purely functional computer language such as Haskell, the result of calling a function must depend only on the function called and its parameters (as a mathematical function does) the result must not depend on anything external such as input/output (IO) or some variable or system state. In practice this is too limiting as a computer program would not be much use without Input/Output and passing a system state into lots of function calls seems very tedious. A monad allows us to do these things, to some extent, while most of the program still has the benefits of being purely functional.

A part of an imperative (non-functional) program might look like this:

int x,y,z;
x = funct1(1,2);
y = funct2(x);
z = funct3(x,y,5);
x = funct4(y);

where x,y and z are variables which can change their value. In a purely functional program, variables can't change like this and so we need to do everything by functional composition like this:

funct3(funct1(1,2),funct2(funct1(1,2)),5);

Not exactly readable, to try to make it easier to work with function composition Haskell defines the following typeclass:

class  Monad m  where
    (>>=)  :: m a -> (a -> m b) -> m b
    (>>)   :: m a -> m b -> m b
    return :: a -> m a
    fail   :: String -> m a

Where 'm' is a type constructor, that is 'm a' takes a given type and returns another type.

If 'm' were [] that is List and 'a' were char then 'm a' would be [char] a list of characters. This could be applied recursively so 'm m a' would be [[char]].

If 'm' were * -> * that is a function and 'a' were char then 'm a' would be 'char -> char' a function from character to character. This could be applied recursively so 'm m a' would be:
(char -> char) -> (char ->char).

So how is this related to the mathematical concept of monads discussed above? It may help if we replace '>>=' with a related function 'join' as follows:

join             :: (Monad m) => m (m a) -> m a
join x           =  x >>= id

Where 'id' is the identity function:

id               :: a -> a
id x             =  x

So now:

return join maps type:
m (m a) to m a to m (m a)
join return maps type:
a to m a to a

So map and join are our natural transformations.

monad program

Monad and Monoid

For me, so far, the explanation that comes closest to tie together monads in category theory and monads in Haskell is that monads are a monid whose objects have the type a->m b. I can see that these objects are very close to an endofunctor and so the composition of such functions are related to an imperative sequence of program statements. Also functions which return IO functions are valid in pure functional code until the inner function is called from outside.

This id element is 'a -> m a' which fits in very well but the multiplication element is function composition which should be:

(>=>) :: Monad m => (a -> m b) -> (b -> m c) -> (a -> m c)

This is not quite function composition, but close enough (I think to get true function composition we need a complementary function which turns m b back into a, then we get function composition if we apply these in pairs?), I'm not quite sure how to get from that to this:

(>>=) :: Monad m => m a -> (a -> m b) -> m b

Monad and Adjunction

Every monad arises from some adjunction, in fact typically from many adjunctions. Two constructions, the Kleisli category and the category of Eilenberg-Moore algebras, are extremal solutions of the problem of constructing an adjunction that gives rise to a given monad.

monad adjoint

The example about free groups can be generalized to any type of algebra in the sense of a variety of algebras in universal algebra. Thus, every such type of algebra gives rise to a monad on the category of sets. Importantly, the algebra type can be recovered from the monad (as the category of Eilenberg-Moore algebras), so monads can also be seen as generalizing universal algebras. Even more generally, any adjunction is said to be monadic (or tripleable) if it shares this property of being (equivalent to) the Eilenberg-Moore category of its associated monad. Consequently Beck's monadicity theorem, which gives a criterion for monadicity, can be used to show that an arbitrary adjunction can be treated as a category of algebras in this way.

Example

On the adjunction page (see example 1 here) we looked at an example using a preodered set (illustrated using a directed graph). So, can we turn this into a monad?

example Here is F (shown on the left) and G (shown on the right).
example So GF and GF2 are as shown here.

 

The Kleisli Category of a Monad

I would like to link together all the different category theory explanations: endofunctor+2 natural transformations, Kleisli category, a monoid whose objects are monoids and so on. For me the thing that seems to link all these explanations is that they are two level. That is, normally we treat category objects as black-boxes where we imply their properties from their outside interactions, but here there seems to be a need to go one level inside the objects to see what's going on? We can explain monads without this but only if we accept apparently arbitrary constructions.

Monad using String Diagrams

more about string diagrams on this page

Because there is only one object, it is not shown on the string diagram. So, in this case, crossing over the line means going once round the endofunctor 'T'.

  Category Diagram String Diagram
A monoid is an endofunctor with two natural transformations and axioms shown below. monoid string diagram  
The first natural transformation μ monad string diagram monad string diagram
The other natural transformation η monad string diagram monad string diagram
The left unit triangle monad string diagram monoid string diagram
The right unit triangle monad string diagram monoid string diagram
The associatively square. monoid string diagram monoid string diagram

 


metadata block
see also:
Correspondence about this page

Book Shop - Further reading.

Where I can, I have put links to Amazon for books that are relevant to the subject, click on the appropriate country flag to get more details of the book or to buy it from them.

flag flag flag flag flag flag The Princeton Companion to Mathematics - This is a big book that attempts to give a wide overview of the whole of mathematics, inevitably there are many things missing, but it gives a good insight into the history, concepts, branches, theorems and wider perspective of mathematics. It is well written and, if you are interested in maths, this is the type of book where you can open a page at random and find something interesting to read. To some extent it can be used as a reference book, although it doesn't have tables of formula for trig functions and so on, but where it is most useful is when you want to read about various topics to find out which topics are interesting and relevant to you.

 

Terminology and Notation

Specific to this page here:

 

This site may have errors. Don't use for critical systems.

Copyright (c) 1998-2016 Martin John Baker - All rights reserved - privacy policy.