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

26 May 2013

In this post we write some notes about monads and describe the Maybe and List Monad types. My main reference was Chapter 14 from *Real World Haskell* and A Fistful of Monads from *Learn You a Haskell for Great Good!*

I’ve written about typeclasses in an old post (in Portuguese). Haskell defines a typeclass called `Monad`

:

When a type `m`

implements this typeclass it is considered a *monadic type*. Note that `>>`

and `fail`

have default implementation, but it’s possible to override them.

One simplistic way to get a grasp of Monads is to think that the type `m`

is a kind of a box. Then the `return`

function puts the type `a`

inside the box `m`

. Also, the chain operator `(>>=)`

receives a box containing `a`

and a function that takes `a`

and return the type `b`

inside a box.

It’s easier to understand those functions with an example. Let’s consider the simplest monadic type, the Maybe Monad.

The `Maybe`

type can be define as an Algebraic Data Type as follows:

The standard implementation for the `Monad`

typeclass for the type `Maybe`

is the following

In the first implementation for the chain operator, `k`

is a function that receives the value x wrapped inside `Just`

and returns another value wrapped inside `Maybe`

.

Note that `Maybe`

overrides the default implementation for `fail`

.

The chain operator has this name because we can concatenate several functions in a chain. Consider the following example using the Maybe monad:

This chaining of Maybe monads is useful when we need to execute several functions such that if an error occurs, we stop further processing.

If we look at the default definition of the `(>>)`

operator, it basically doesn’t pass the value from the previous function forward, so the function to the right of `(>>)`

doesn’t have an input. For example, we can define a new function `f4`

:

The chaining of the `(>>=)`

operator has an alternative syntax using the keyword do. In this case we need to explicitly deal with the returned values and function parameters and pass to the following function. For the example above we would have:

It’s more verbose, but on the other hand the variables might be both used in the same scope. In the next example, `x`

and `y`

are available to be used in the last function:

If we go with the `(>>=)`

operators, we would have a less elegant solution with nested functions to keep both variables in the same scope:

Lists also implement the `Monad`

typeclass. The standard implementation is the following:

In the analogy of boxes, we may think that the type `[]`

can hold more than one item (of the same type). The return function inserts a single element in the box.

The bind operator receives a list of elements and a function that applies to elements ans return another list (its elements can have a different type).

If we have a function that receives an element and returns a list of one element, we have just a kind of map. For example:

If it returns a list with two or more element, we can identify it’s performing a cartesian product:

Let’s consider an example using with nested functions

For which we get `[(1,'a'),(1,'b'),(2,'a'),(2,'b'),(3,'a'),(3,'b')]`

, or using the `do`

syntax:

If we compare with the list comprehension syntax that gets the same output, we can see how similar they are:

When we implement the Monad typeclass for a given type, Haskell doesn’t have means to check the properties that actually makes the type a Monad. So we have to guarantee it ourselves when declaring our type monadic by verifying the following 3 properties:

**Left identity.** `return x >>= f`

is equivalent to `f x`

In our analogy, it means that if we put our element in the box (`return`

) and apply the operator (`>>=`

), it must extract this element and apply `f`

, which should be the as applying it directly.

**Right identity.** `m >>= return`

is equivalent to `m`

It means that we are sending the element inside a box `m`

and applying the operator `(>>=)`

, which will extract the element and just put it again inside the box (`return`

), so the same thing that entered must come out, in this case, `m`

.

**Associativity.** states that `(m >>= f) >>= g`

is equivalent to `m >>= (\x -> f x >>= g)`

In a expression, the associativity property means that we can execute the operations in a chain in any order (e.g. `(a + b) + c == a + (b + c)`

).

This is partially true here, because if we try to have `(m >>= f) >>= g`

equal to `m >>= (f >>= g)`

, which is not correct because the operator is not symmetric (it requires a monadic type and not a function that returns one).

To solve this problem, we can curry the function applying the first parameter. Since f has type `(Monad m) => a -> m b`

, then `(f x)`

for `x`

of type `a`

, we have the type `m b`

.

In [2], the authors define a new symmetric operator `(<=<)`

that makes it easy to spot the associative law:

Now we can say that `f <=< (g <=< h)`

should be the same as `(f <=< g) <=< h`

.

We must get x from somewhere though and we can do this by wrapping it inside a function, thus `(f >>= g)`

becomes `(\x -> f x >>= g)`

.

Note however that we’re not actually executing the functions in the chain in different order, because we lifted the operation to another function that will only the executed after it has the element from the left of the operator `(>>=)`