Chris Taylor

Mainly math and haskell

Getting Values Out of Monads

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
class Monad m where
    return :: a -> m a
    (>>=)  :: m a -> (a -> m b) -> m b

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
h . return = id

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
h . join = h . fmap h

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 : MAA such that the following diagrams commute:

$$ \newcommand{\ra}[1]{\kern-1.5ex\xrightarrow{\ \ #1\ \ }\phantom{}\kern-1.5ex} \newcommand{\ras}[1]{\kern-1.5ex\xrightarrow{\ \ \smash{#1}\ \ }\phantom{}\kern-1.5ex} \newcommand{\da}[1]{\bigg\downarrow\raise.5ex\rlap{\scriptstyle#1}} \newcommand{\dda}[1]{\searrow\raise.5ex\rlap{\scriptstyle#1}} \begin{array}{c} \begin{array}{c} A & \ra{\eta_A} & MA \\ & \dda{\textrm{id}_A} & \da{h} \\ & & A \end{array} & \qquad & \begin{array}{c} M(MA) & \ra{\mu_A} & MA \\ \da{Mh} & & \da{h} \\ MA & \ra{h_\phantom{A}} & A \end{array} \end{array} $$

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):

1
2
h $ do x <- xs       =   h $ do x <- xs
       return (h x)             x

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
sum (return x) == x                   -- for any x :: a
sum (join xs)  == sum (fmap sum xs)   -- for any xs :: [[a]]

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 non-empty lists.

Similarly maximum and 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

1
fold :: (Foldable f, Monoid m) => f m -> m

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
str :: String -- any string that can be parsed

right :: Either a b -> b
right (Left _)  = error ""
right (Right b) = b

h :: Parser a -> a
h p = right (parse p "" str)

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
unsafePerformIO :: IO a -> a

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?