Blog

Functor, Applicative, Monad Part 2

Monads

Monads are the next step on our way to understand how purely functional languages can perform IO. Here is the Monad typeclass:

class Monad m where
  return :: a -> m a
  (>>=) :: m a -> (a -> m b) -> m b

The function return in the Monad typeclass does exactly the same as pure in the Applicative typeclass. The function (>>=) (pronounced "bind") is more interesting. It takes a value wrapped in the Monad and a function, that does something to that value and wraps it in the same Monad. Again we are going to look at Maybe, which is also a Monad.

(Just 3) >>= (\x -> Just (x + 3))
> (Just 6)

Again the functionality of (>>=) depends on the Monad you are using. Just like <*> the bind operator in the Maybe Monad short circuits the computation when the left side is Nothing

Nothing >>= (\x -> Just (x + 3))
> Nothing

The type of bind enables you to actually perform the check for nothing in between the function calls. Lets look at this lispy definition of Lists.

data LispyList = NIL | Cons a (LispyList a)

car :: LispyList a -> Maybe a
car NIL = Nothing
car (Cons x xs) = Just x

cdr :: LispyList a -> Maybe (LispyList a)
cdr NIL = Nothing
cdr (Cons x xs) = Just xs

If you want to combine the functions car and cdr to the in Lisp also available function cadr (which gives you the first of the rest of a list) you run into a problem. The argument type of car doesn't match the output type of cdr. You have to check whether the output is (Just list) or Nothing.

cadr :: LispyList a -> Maybe a
cadr l = let l' = cdr l in
           case l' of
             Nothing = Nothing
             Just xs = car xs

To get the first of the rest of the rest you have to check for Nothing twice:

caddr :: LispyList a -> Maybe a
caddr l = let l' = cdr l in
            case l' of
               Nothing = Nothing
               Just xs = let l'' = cdr xs in
                           case l'' of
                              Nothing = Nothing
                              Just ys = car ys

You get the point. The bind operator in the Maybe Monad does exactly that: check result of first function, if Just x apply function two to x. So you can write cadr like:

cadr l = cdr l >>= car

Note that you actually have to give the argument to the first function so it matches the type of (>>=). The next function follows from that:

caddr l = cdr l >>= cdr >>= car

The problem most people have with Monads is, in my experience, not a problem with Monads in general, but with a specific Monad. If you want a different view on Monads, Brian Beckman does a great job at explaining Monads in terms of Functions and Monoids in this video. 

The basics of Monads are clearly visible in the Maybe Monad but to understand the IO Monad, we have to look at a Monad that gives many people (including sometimes me) a lot of problems: the State Monad.

The State Monad

The State Monad lets you simulate mutable state in Haskell. Lets first take a look at the State type and its Monad instance.

newtype State s a = State { runstate :: s -> (a,s) }

instance Monad (State s) where
   return a = State $ \s -> (a,s)
   m >>= k = State $ \s -> let (a,s') = runstate m s in
                             runstate (k a) s'

In the State Monad you hold a function of type s -> (a,s). The typevariable s represents the type of the state, the typevariable a represents the actual returntype of the function. So a computation in the State Monad turns the current state into a possibly modified state and a result of any type. To better understand the (>>=) implementation we are going to look at an example.

type Stack = [Int]

type StackState a = State Stack a

push :: Int -> StackState ()
push a = State $ \as -> ((), a:as)

pop :: StackState Int
pop = State $ \(a:as) -> (a, as)

The state here is a list of Int's. We call that a Stack and implement the two functions on Stacks: push and pop. Push takes another Int and puts it in the Stack as the new top element. The function that does that (the lambda expression in the definition of push) still needs to return a pair of type (a,s). Because there is no sensible thing to return here we just return () (unit) and the second part is the new stack. The whole thing is then wrapped into the State constructor.

The definition of pop follows the same concept. The function takes the stack, returns the top element as the result and the stack without the top element as the new stack. Again the function needs to be wrapped in the State Monad.

To see how the combination of those functions work we have to untangle the implementation of (>>=). The m on the left side of (>>=) has type (m a). So in the State Monad it holds a function that takes the current State and returns a pair of type (a,s). So the sensible thing to do would be to extract that function and apply it to the current state. That is what happens in the let expression. We get a pair (a,s'). The right side of the (>>=) is a function of type (a -> m b). We just got a value of type a so we apply the function k to a to get out (m b), which is something with a function of type s -> (b,s) inside. This function is again extracted and applied to the new state s'. All of this has to be another function in the State Monad, so it is wrapped in the State constructor.

Now what can we do with this? For example we can remove the second element from the stack like so:

removeSecond :: StackState ()
removeSecond = pop >>= \x -> pop >> push x

The (>>) operator does the same as (>>=) but it ignores the returned value from the left side, so in this case the second element from the stack.

This is how you thread some piece of mutable state from one pure function to another. The implicit side effect of changing the stack when you pop an element of the stack is made explicit by actually returning the changed stack alongside the top element. The details of making sure that the next function gets the new state of the stack is hidden in the implementation of (>>=).

Brandon Simmons does a great job at explaining the State Monad in a bit more detail. I definitely recommend reading his blogpost here:  http://brandon.si/code/the-state-monad-a-tutorial-for-the-confused/

In the next post we will take a look at how this is used to perform IO in Haskell.