Maths - Category Theory - List and Set Monads

For a more theoretical approach see this page.

List Monad

We can introduce a functor which takes any type and turns it into a list of that type. list
We can draw this as an endo-functor. list

List - Natural Transformations

The unit transform creates a single valued list list unit
The natural way to create a mult transform is a transform which flatterns a list of lists into a flat list. list mult

Lists Form a Free Monoid

list as free monoid Lists form a free monoid, that is, this diagram commutes.

This concept can be extended to other free structures see [R.M. Burstall and P.J. Landin, "Programs and their proofs, an algebraic approach", Machine Intelligence 4(1969)]

Lists as monads

map :: (x -> y) -> (M x -> M y)

This map applies function (x -> y) to every element of M



map is an example of a functor:

map :: (x -> y) -> (M x -> M y)
map :: f -> M f

That is, we can use M to represent the result of mapping elements and the result of mapping a function of elements. So M is a functor, a higher order function.

As usual we will call the two natural transformations 'unit' and 'join' and so adding these to the map gives:

  [] notation   M notation
map :: (x -> y) -> [x] -> [y]   map :: (x -> y) -> (M x -> M y)
unit :: x -> [x]   unit :: x -> M x
join :: [[ x ]]-> [x]   join :: M ( M x) -> M x

List Monads in Haskell

The class (defines type) of any monad is:

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

The definition depends on what type, in this case the list monad can be defined like this:

instance Monad List where
  return x = [x]
  xs >>= f = concatMap f xs


[ t | q ]


defined by rules:


Equivalence between comprehensions and monads

Monad Comprehension  
map :: (x -> y) -> (M x -> M y) [ t | x <- u] = map(λ x -> t) u  
unit :: x -> M x [ t | /\ ] = unit t  
join :: M ( M x) -> M x [ t | (p,q) ] = join [[ t | q] | p]  

Sets as monads

We can generalise to set notation

Monad Comprehension  
mapset :: f x = { f x | x∈ x }
mapset :: f x = [ f x | x <- x ]
unitset :: x = { x } unitset :: x = [ x ]  
= U
= [ x | x <-
, x <- x ]


U = union
x element of set
= set of x
= set of set of x

comprehension notation:

[ (x,y) | x <- x , y <- y ]set


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-2017 Martin John Baker - All rights reserved - privacy policy.