kuniga.me > NP-Incompleteness > Monads in Haskell - Part II

28 Jul 2013

In this second post about Monads in Haskell, we’ll talk about the three new types of Monads introduced in the chapter For a Few Monads More, from the Learn You A Haskell for Good: the Writer, the Reader and the State Monads.

The writer monad is useful when we want to attach some kind of logging to our value. The monadic type we’re going to work with takes a value of type `a`

and the “logging” type `w`

.

The definition of the Writer Monad is:

`Monoid`

is a typeclass with a set of common functions that a monoid type must implement, which are, `mempty`

, `mappend`

and `mconcat`

.

The `mempty`

function returns an empty instance of the type `m`

, `mappend`

is any binary function over 2 instances of type `m`

and `mconcat`

is a generalization of `mappend`

, a function over a list of instance of type `m`

. The `Monoid`

typeclass provides a default implementation of this function consisting of a `foldr`

.

For example, the list type `[]`

is can be seen as a monoid with the following implementation:

So going back to the Writer monad definition, we have that the “logging” type must be a monoid type. And we define the monad over the type `(Writer w)`

which can be seem as wapper on the type `a`

.

The `return`

function consists in wrapping an instance of the type a into the type `(Writer w)`

, so the simplest one is to just have an empty instance of type `w`

. Since it’s a monoid, we can use the functiion `mempty`

.

The chain operator `(>>=)`

takes an instance of type a wrapped into the `(Wrapper w)`

and pass it to a function that operates on the type a and wraps the resulting type into `(Wrapper w)`

again. In our implementation of the monad for `(Writer w)`

, we extract the element `x`

, apply `f`

on it and compose a new log message combining the incoming log message and the one returned by function `f`

, using the `mappend`

function.

This implementation is available in the `Control.Monad.Writer`

module. One simple example that uses the Writer Monad is a function that operates over numbers and log them:

Which will return

The state monad when we want to carry some internal state along our computation. One example is a parser code presented in [2], where the authors use the partial parsed code as an internal state.

In the same fashion as the writer monadic type, we have a type that depends on two type parameters, one of them representing the wrapped value and the other the type of the state.

The difference here is that instead of a pair of the two types, our new type is actually a function that receives a value of type s and wraps it into a tuple together with an instance of type a.

The definition of the State Monad is given by:

The implementation of the `return`

function is straightforward, it just returns a function that receives a state and returns a pair of `x`

with this state. This function is then wrapped into the type `State`

.

The chain operator is more involved. To extract the value of type a from a `State`

type, we first need to extract the function `h`

from it (by pattern matching `(State h)`

), and then extracting the value a by providing an state to it. Note that we can assume this state `s`

because this is done within a lambda that receives a state.

After extracting the value a from the first parameter of `(>>=)`

, we can finally apply the function `f`

to it. This will return an instance of `State`

, from which we extract yet another function `g`

that receives an state and returns a pair. We use the state that resulted after applying the state `s`

to function h and return the pair resulting from applying the new state to this function.

The State Monad is also useful when we’re dealing with random number generation. In Haskell you have to keep a reference to the random number generator otherwise it will always generate the same number. The following example uses the random genetor as a state, which makes it simple to generate multiple random numbers:

The Reader Monad [3] is similar to the State monad but in this case we have a state that is immutable, which we can see as an environment. The Reader type is a wrapper of a function that receives the environment `e`

and returns an instance of type `a`

. Since the environment is immutable, there’s no need to return it along with our value.

The definition of the Reader Monad is then:

For the `return`

function, we have an analogous function as for the State Monad, but since in this case the function doesn’t need to return the environment, we return a function that doesn’t care about the parameter.

The chain operator is also a special case of the State Monad chain operator. We first extract the function `g`

via pattern matching, within the lambda function we provide the environment `e`

to `g`

in order to retrieve our value of type `a`

and apply the function `f`

.

The function `f`

will return another function `h`

wrapped inside a Reader instance which we can extract using pattern matching again. This function wrapped back into a Reader instance is essentially the result of the chain operator.