Motivations for Monads

It has become an habit to write articles to myself (no one are visiting this site). But writing posts is good anyhow. To force yourself to describe something often makes you improve your own understanding.

The purpose of this article is to try to make a motivation and explanation on why monads are useful in many languages and almost necessary on Haskell. The conclusion are mostly drawn from the video clip by Brian Beckman below. There are certainly much, much better explanations for monads than this one. This is mainly for me.

Brian motivates monads from the concept of function composition. Function composition is the way functions in Haskell can be combined (or composed) to create higher level functions. Brian think this is a very important concept to permit difficult problems to be solved by methodically divide the problem in smaller functions which is combined in higher order functions which finally make it easy to solve the problem.

The main difference from this aspect compared with imperative programs (which also is divided in smaller functions and objects to solve complex problems) might be the clean expressibility of compositions in a functional language. The strict type system of Haskell also makes composition more safe to use.

Some examples of function composition is shown below. Assume that s contains the previous paragraph.

words is a simple functions which divide a string into words.

> words s
["The","main","difference", ...]

Using function composition is easy to combine words with length which count the elements in a list.

> (length . words) s
47

What if you want to reverse each word but keep the order of the words.

> unwords $ map reverse $ words s
"ehT niam ecnereffid ..."

Lets filter out the words below 3 characters

> unwords $ filter ((<3) . length) $ (words) s
"is in to be of in a of to"

Its also easy to name these higher order functions to simplify its use in new situations.

> let tiny_word = ((<3) . length)
> let keep_tiny_words = unwords . filter tiny_word . words
> keep_tiny_words s
"is in to be of in a of to"

The last example is not as succinct in a typical imperative language as e.g. Java.

The definition for function composition is as follows.

(.) :: (b -> c) -> (a -> b) -> (a -> c)
f . g = \x -> f (g x)

This means that the composition of f and g is the same as first applying g to the argument of the composed function and the apply f on that result. Application is applied from right to left. In tiny_words words is first applied to the input string then filter and last unwords.

So, functional composition is a very powerful way to combine functions into higher order functions.

f :: b -> c
g :: a -> b
f . g = \a -> f (g a) :: a -> c

For monads we define a similar composability for monadic functions. A monadic function takes a value of a regular type and return value of a monadic type.

f :: a -> M b
g :: b -> M c

But, what is a monadic type? A monadic type is just a type that is an instance of the Monad type class i.e. it defines a set of pre-defined functions. Maybe, IO and [] is just some examples of types that implement Monad type class.

A popular way to interpret monadic values is to say they are regular values with a "context". For Maybe the context is a value which may have failed. For IO it is the state of IO with the "outside" world. For [] it is any number of regular values.

How do we define composition for monadic functions. Normal function composition doesn't make sense for monadic functions because the output from a monadic function is monadic value which can't be fed into another functions, which expects a regular value.

We want something like this. We want to compose two monadic functions into a new monadic function.

(bind) :: (a -> M b) -> (b -> M c) -> (a -> M c)

Written on separate rows this becomes.

(a -> M b) -> (b -> M c) ->
(a ->               M c)

So, how can we achieve something that is composable? If we decide to compose the monadic values instead of the monadic functions it might be possible. If we take the monadic value of type Mb we can bind it with a monadic function to create a new monadic value of type M c. When doing this we have achieved the equivalent of composing two monadic functions but we have done it on the monadic values instead.

The bind function for monadic values are specified as >>= and is defined as follows.

(>>=) :: M b -> (b -> M c) -> M c

Compared with normal function composition which combines two functions into one, monadic composition combine a monadic value with a monad transformation to create a new monadic value.

This allows a monadic function to be applied to a monadic value to create a composed monadic value.

let add_one e = return $ (e+1)
let sub_one e = return $ (e-1)
let add_sub e = return $ (if e < 0 then e-1 else e+1)

> Just 0 >>= add_one >>= add_sub >>= sub_one
Just 1
> Just 0 >>= sub_one >>= add_sub >>= add_one
Just (-1)

Note that monadic composition is performed from left to right (opposite to function composition).

What is the corresponding function composition for monadic types? Functions for monadic types map between two different monadic values. A functions that takes a monadic value and bind to a monadic function is just that.

> :t \m -> (m >>= add_one)
\m -> (m >>= add_one) :: (Monad m, Num b) => m b -> m b

These functions can be composed just as normal functions. Note that they behave just as normal function composition (with non-monadic values), where functions are applied from right to left.

> (\m -> (m >>= add_one)) . (\m -> (m >>= add_sub)) . (\m -> (m >>= sub_one)) $ (Just 0)
Just (-1)
> (\m -> (m >>= sub_one)) . (\m -> (m >>= add_sub)) . (\m -> (m >>= add_one)) $ (Just 0)
Just 1

In this way monads can be combined both as monadic values and and as functions on monadic values.

Monadic functions (a -> M b) can also be composed using a special kleisli composition operator (>=>).

> (>=>) :: Monad m => (a -> m b) -> (b -> m c) -> a -> m c
> Just 1 >>= (add_one >=> add_sub >=> sub_one)
> Just 1

Now we have a number of different ways to compose monadic functions.

Relation to functor

If you have join around monadic 'bind' can be expressed from fmap and join.

:t (>>=)
(>>=) :: Monad m => m a -> (a -> m b) -> m b

:t (=<<)
(=<<) :: Monad m => (a -> m b) -> m a -> m b

:t fmap
fmap :: Functor f => (a -> b) -> f a -> f b

:t join
join :: Monad m => m (m a) -> m a

As you can see bind =<< is similar to fmap if you restrict type b in map function a -> b to a monadic value m b.

fmap :: Functor f, Monad m => (a -> m b) -> f a -> f (m b)

You just need to join the resulting value f (m b) to m b

import Control.Monad

bind :: Monad m => m a -> (a -> m b) -> m b
bind a f = join $ fmap f a

Now we have implemented bind using fmap and join.

:t bind
bind :: Monad m => m a -> (a -> m b) -> m b

So you can think of bind as a set of fmap's collapsed together.

References