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
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
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
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 multi-parameter 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):
Enough theory - what are some examples of algebras? For the list monad, both
product are list algebras for any numeric type. You can check that they satisfy the algebra laws, i.e.
and similarly for product.
Note that the function
length isn’t a list algebra, since
length (join [,[2,3]]) is
length (fmap length [,[2,3]]) is
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 non-empty lists.
minimum are algebras over the type of non-empty 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
fold is an
f-algebra for any
f that is an instance of
Foldable. This gives algebras over
Tree and many more.
Given any value
a of type
h m = runReader m a is a
h m = evalState m a is a
State s-algebra, and
fst . runWriter is a
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
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?