Kyle Miller > Programming > Yet Another Monad Guide

Yet Another Monad Guide

I was tired of seeing all these guides to understanding monads on the Internet, so I wrote another (mainly because I helped teach a class on Haskell and needed some materials). There will be no presents, no monsters, no cookies, but instead some motivating examples and the abstraction which relates them all: the monad type. You can also download monads.hs to run it directly in ghci. Then, you can run any of the example functions from the interpreter (such as ex2).

On this page, monads.hs is modified to be more like literate programming and has more explanation. We start with some imports.

import IO -- (<-- we'll talk about this later)
import Monad -- (<-- contains a function called 'guard')
Before we get into monads, let’s first look at some problems we might want to solve, and see if we can simplify what we’re doing (hint: it’s going to involve discovering monads).

1. Problem 1

Let’s say we want to tag data so we know where it came from (the creator), but we also want to apply functions on the data, keeping the provenance intact.

We can represent tagged data with the following type. 

data TaggedDataType x = TaggedData { creator :: String, innerData :: x }
                        deriving Show
So, if we want to create tagged data, we invoke the constructor: 
ex1 = TaggedData "I made this." (2 + 3)

We can get the data out, too: 

ex2 = do putStr "Stuff in ex1."
         putStr (" creator=" ++ show (creator ex1))
         putStrLn (" innerData=" ++ show (innerData ex1))

Now, let’s say we want to make a function which takes an tagged integer (which is of type TaggedDataType Integer) and adds 5 to it, while keeping creator the same. We can do the following: 

taggedAddFive :: TaggedDataType Integer -> TaggedDataType Integer
taggedAddFive x = TaggedData ((creator x) ++ " Then added 5.") (5 + (innerData x))

For a more complicated example, let’s say we want to make a function which then doubles the tagged value after adding five to it 

taggedAddFiveDoub :: TaggedDataType Integer -> TaggedDataType Integer
taggedAddFiveDoub x = let x2 = taggedAddFive x
                      in TaggedData ((creator x2) ++ " Then doubled.")
                                    (2 * (innerData x2))

We can do better. Let’s make a new function, let’s call it bindTagged because it binds the inside of a TaggedDataType to be an argument to a given function, keeping the creators intact (it’s like making “pipework”): 

bindTagged :: TaggedDataType x -> (x -> TaggedDataType y) -> TaggedDataType y
taggedValue `bindTagged` f = let x2 = f (innerData taggedValue)
                             in TaggedData ((creator taggedValue) ++ (creator x2))
                                           (innerData x2)
We use back quotes (`) so we can use bindTagged as an operator, which is just notational convenience.

With this, we can rewrite our previous two functions as 

taggedAddFive2 :: TaggedDataType Integer -> TaggedDataType Integer
taggedAddFive2 x = x `bindTagged`
                   (\v -> TaggedData " Then added 5." (v + 5))
taggedAddFiveDoub2 x = (taggedAddFive2 x) `bindTagged`
                       (\v -> TaggedData " Then doubled." (v * 2))
The benefit is here is that we do not have to explicitly deal with concatenating the creator strings. Not that bad, but we’ll do better later.

2. Problem 2

Let’s say we are doing computations, but we might run into an error and need to throw an exception. For example, perhaps we have associated lists of type [(Integer, String)] and we want to search for a string given an integer. We could try the following. 

assocSearch :: Integer -> [(Integer, String)] -> String
assocSearch key ((i,s):xs) = if key == i
                             then s
                             else assocSearch key xs
But what if key never appears? We could return a sentinel such as the empty string, but perhaps we want to have associated lists which contain the empty string.

We can create a new datatype. Let’s call it Perhaps to reflect the idea of perhaps having a value. 

data Perhaps x = Yep x | Nope
                 deriving Show
so if we are searching for 5, and we find (5,"a"), we return Yep "a", otherwise Nope. 
assocSearch2 :: Integer -> [(Integer, String)] -> Perhaps String
assocSearch2 key ((i,s):xs) = if key == i
                              then Yep s
                              else assocSearch2 key xs
assocSearch2 _ [] = Nope
We can use this as follows (the argument to ex3 being an integer). 
ex3 k = let al = [(1,"a"), (2,"b"), (3,"c")]
        in case (assocSearch2 k al) of
             Nope -> "Didn't find that key"
             Yep x -> "Found " ++ x
-- ex3 1 ==> "Found a"
-- ex3 5 ==> "Didn't find that key"

Let’s say we also have a function which adds “good” to the end of a string only if it’s not an a, otherwise it’s an error (who knows—perhaps it could be useful). 

not_a :: String -> Perhaps String
not_a s | s == "a"   = Nope
        | otherwise  = Yep (s ++ "good")

And, for whatever reason, we’ve decided it’s necessary to take the output of assocSearch2 and run it through not_a. 

ex4 k = let al = [(1,"a"), (2,"b"), (3,"c")]
        in case (assocSearch2 k al) of
             Nope -> "Didn't find that key"
             Yep x -> case (not_a x) of
                        Nope -> "Boo. It was an a."
                        Yep s -> "Found "++s
-- ex4 2 => "Found bgood"
-- ex4 1 => "Boo. It was an a."

But, this is still a bit ugly. We have to keep nesting these case statements! Let’s make a helper function called bindPerhaps which binds the inside value of a Perhaps to a function only if it is not a Nope, otherwise it just passes on Nope. 

bindPerhaps :: Perhaps x -> (x -> Perhaps y) -> Perhaps y
v `bindPerhaps` f = case v of
                      Nope -> Nope
                      Yep x -> f x

Then, we can rewrite ex4 as ex5. 

ex5 x = let al = [(1,"a"), (2,"b"), (3,"c")]
            ret = (assocSearch2 x al) `bindPerhaps` not_a
        in case ret of
             Nope -> "Didn't find key, or we got an 'a'!"
             Yep s -> "Found " ++ s
-- ex5 2 => "Found bgood"
-- ex5 10 => "Didn't find key, or we got an 'a'!"
-- ex5 1 => "Didn't find key, or we got an 'a'!"
This lets us essentially compose the functions rather than have nested case blocks.

3. Problem 3

Sometimes we want to handle multiple values from a function, such as a square root (the positive and negative roots). One way we can handle this is by returning a list of all possibilities.

multiSqrt x | x > 0   = [ -(sqrt x), sqrt x ]
            | x == 0  = [ 0 ]

Let’s say we want to pass the output of this to a function f. 

ex6 = let f x = 5 + x
      in map f (multiSqrt 4)
But, what if f, too, wants to use the multiSqrt function? 
ex7 = let f x = multiSqrt (10 + x)
      in concat (map f (multiSqrt 4))
Again, we can do better. Let’s define bindMulti to take a function and apply it to every element of a list, concatenating the results. 
bindMulti :: [x] -> (x -> [y]) -> [y]
bindMulti vals f = concat (map f vals)
With this we may rewrite ex7 as 
ex8 = let f x = multiSqrt (10 + x)
      in (multiSqrt 4) `bindMulti` f
So, we only have to write `bindMulti` instead of using both concat and map.

4. Did somebody say monads?

Let’s look at the type signatures of our bind operators and see if we notice a pattern. 

bindTagged :: TaggedDataType x -> (x -> TaggedDataType y) -> TaggedDataType y
bindPerhaps :: Perhaps x -> (x -> Perhaps y) -> Perhaps y
bindMulti :: [x] -> (x -> [y]) -> [y]
They are all of type M x -> (x -> M y) -> M y, where M is some type constructor! (Remember that [x] is shorthand for [] x).

Here’s the secret: a monad is just something which has such a binding operator with the above type, and one other thing we haven’t talked directly about which is something which converts a value into such a monad, hence having type x -> M x. We call such an operator return. For example, we could write 

returnTagged x = TaggedData "" x
returnPerhaps x = Yep x
returnMulti x = [x]

Note that ((returnM a) `bindM` f) is the same as f a.

To abstract this behavior, Haskell has a Monad class. 

class Monad m where
    (>>=)  ...
    return ...

So, let’s turn our objects into Monads. 

instance Monad TaggedDataType where
    (>>=)  = bindTagged
    return = returnTagged

instance Monad Perhaps where
    (>>=)  = bindPerhaps
    return = returnPerhaps

In fact, there already is a monad with the functionality of Perhaps, and that’s 

data Maybe x = Just x | Nothing
And, it turns out lists are already instances of class Monad with the same implementation we gave for bindMulti and returnMulti.

Haskell provides a nice syntax to aid in writing expressions using monads. Instead of writing 

taggedAddFive3 x = x >>= (\v -> TaggedData " Then added 5." (v + 5))
taggedAddFiveDoub3 x = (taggedAddFive3 x) >>= (\v -> TaggedData " Then doubled." (v * 2))
which one invokes with an expression like taggedAddFiveDoub3 (return 2), we can write, as shorthand, 
taggedAddFiveDoub4 x = do v <- taggedAddFive3 x
                          TaggedData " Then doubled." (v*2)
the last expression in a do statement is the return value, which must be of the same type as the first expression.

Likewise, instead of writing 

ex9 x = (assocSearch2 x al) >>= not_a
    where al = [(1,"a"), (2,"b"), (3,"c")]
you could instead choose to name intermediate expressions in a do statement 
ex10 x = do search <- assocSearch2 x al
            ret <- not_a search
            return ret
    where al = [(1,"a"), (2,"b"), (3,"c")]

and, 

ex11 = let f x = multiSqrt (10 + x)
       in do v1 <- (multiSqrt 4)
             f v1

For an awesome example of the list monad letting you deal with multiple values, 

pyth_triples = do x <- [1..100]
                  y <- [1..100]
                  z <- [1..1000]
                  guard (x^2 + y^2 == z^2)  -- 'guard' requires the Monad module
                  return (x,y,z)
For the list monad, one can equivalently use list comprehension notation. 
pyth_triples2 = [(x,y,z) | x <- [1..100], y <- [1..100], z <- [1..1000], x^2 + y^2 == z^2]

5. IO

One of the things which Monads let us do is order expressions. Since IO has side effects, the order in which IO operations execute needs to be explicitly ordered. The IO monad keeps track of the state of IO devices. Incidentally, IO was the motivation for monads in Haskell in the first place.

One constraint with using IO is that, if a value of type X was calculated when using IO, it must in the end be of type IO X. A way to think of this is that, for example, IO String is an IO-derived string. It’s not a normal string, but an IO string.

Let’s make a function which asks for your name, prints it, and returns it. 

getName :: IO String
getName = do putStr "What is your name? "
             x <- getLine
             putStrLn ("Hello, " ++ x)
             return x

Then, executing getName in ghci: 

*Main> getName
What is your name? Kyle
Hello, Kyle
"Kyle"
The final line is the return value. ghci can handle values of type IO String since all interactions are being done from within the IO monad.

Let’s say you want to make a function which then takes someone’s name, and tells a little story based on the argument. This is an error: 

doStory x = (getName) ++ " walked to the store to get some " ++ x ++ "."
since getName returns an IO String, not a String. Instead, one would write 
doStory x = do name <- getName
               return $ name ++ " walked to the store to get some " ++ x ++ "."
since bind takes the IO String from getName and puts the String in name. Running this, 
*Main> doStory "OJ"
What is your name? Kyle
Hello, Kyle
"Kyle walked to the store to get some OJ."
note that the type of the function doStory is String -> IO String.

An aside: when dealing with IO on the terminal, the output to stdout may not have caught up when there’s a request for stdin (due to the output buffer). One solution is to call hFlush stdout. Otherwise, you may choose to alter the buffering for stdout by writing hSetBuffering stdout NoBuffering. Of course, these return a value of type IO () (the empty tuple representing that the function doesn’t have any particular return value).

Modified 22 December 2011
©2017 Kyle Miller
Back to kylem.net