Monads as used in functional programming are ‘one way’. The monad type class provides a way to put values into the monad (with return) but no way to get values out.
1 2 3 

If you want to get values out of a monad you have to write a function yourself. Such a function would have a type h :: m a > a
where m
is a particular monad. It’d be nice if there were some guarantees about these functions should behave. We’re stepping outside the jurisdiction of the monad laws, so you don’t get any help there. So what are the relevant laws?
If you put a value into the monad and immediately extract a value, you want to get the same value you put in. In other words you want h (return a) = a
, which is the same as
1


If you have two layers of monad m (m a)
then there are two ways you could get a value out. You could lift h
into the monad with liftM
(or fmap
) to get values out of the inner monad, and then hit the whole thing with h
. Alternatively you could use the monadic join to collapse the two layers of the monad into one, and then apply h
once. It would be nice if you get the same result either way, i.e. if h (join x) = h (fmap h x)
, or
1


Taken together, these two laws are exactly the laws of an algebra over the monad. Categorically, an algebra over a monad M is an object A together with a map h : MA → A such that the following diagrams commute:
Note that the categorical definitions says that you have to specify an object as well as a morphism. In the category Hask objects are types. If we want to specify a type class for algebras, it must be a multiparameter type class where you specify the underlying type as well as the monad  i.e. the algebra doesn’t have to be polymorphic over all types, it is allowed to vary depending on the type of values in the monad.
In terms of do notation, the algebra laws mean that the following program transformation is valid, where xs
has type m (m a)
:
1 2 

Examples
Enough theory  what are some examples of algebras? For the list monad, both sum
and product
are list algebras for any numeric type. You can check that they satisfy the algebra laws, i.e.
1 2 

and similarly for product.
Note that the function length
isn’t a list algebra, since length (join [[1],[2,3]])
is 3
, but length (fmap length [[1],[2,3]])
is 2
.
The function head
is nearly a list algebra, only failing because it isn’t defined for the empty list. In fact it’s an algebra over the type of nonempty lists.
Similarly maximum
and minimum
are algebras over the type of nonempty lists.
More generally, if a
is an instance of the Monoid
type class, then foldr mappend mempty
is a list algebra. This is reflected in the definition of the fold
function in Data.Foldable, which has type
1


showing that fold
is an f
algebra for any f
that is an instance of Foldable
. This gives algebras over Maybe
, Either a
, Tree
and many more.
Given any value a
of type r
then h m = runReader m a
is a Reader r
algebra.
Similarly h m = evalState m a
is a State s
algebra, and fst . runWriter
is a Writer w
algebra.
For the monad of probability spaces, the expectation is an algebra. If P(PA) is a distribution of probability distributions, then it doesn’t matter if we take inner expectations before taking the outer expectation, or if we collapse the entire distribution first and takes its expectation. This is related to the law of iterated expectation. Note that higher moments aren’t algebras, and nor are central moments.
I had hoped that for the parser monad I could define an algebra by
1 2 3 4 5 6 7 8 

However, this fails the algebra laws. In particular, if we have a parser of type Parser (Parser a)
, the outer parser might need to read some of the input string before the inner parser will match correctly, so we can’t just map over the inner parser. So I wonder if there are any algebras for the parser monad?
For the IO monad, the obvious candidate for an algebra is
1


My intuition is that this shouldn’t be an algebra, i.e. it should fail to respect one of the algebra laws. However, I haven’t been able to construct an example where it fails yet. Anyone have any ideas?