Ceci n'est ce pas une Haskell Monad Tutorial

With apologies to the great surrealist painter Magritte, this really isn't a Haskell Monad Tutorial (HMT), or is it?

If you are reading this, you are probably aware that the blogosphere is littered with HMTs. The progression usually goes like this:

A programmer...

1. undertakes to learn Haskell, 
2. struggles for some period of time with understanding Monads, 
3. suddenly has that "ah-ha" moment, and 
4. writes a tutorial (convinced that they can finally explain it to the beginner better than anyone else who has gone before could).

In my case, I choose to diverge from this pattern (slightly):

I...

1. took it upon myself to learn Haskell
2. struggled with Monads for some time
3. kind of slowly and grudgingly eventually "got" monads, but not with any kind of dramatic "eureka!", more like a "oh... right... ok" kind of feeling (which was remarkably anti-climactic considering how much hair I'd pulled out over this), and 
4. am writing not so much a tutorial as a: "Here's what I did to understand it. Hope it helps."

I am not going to talk about Monad laws, IO, or Maybe. I am not even going to try to concoct a flowery definition of what it is (like "contanier" or "computational context"). I am just going to give two examples, which I wrote, specificially with a view to clarifying my own understanding (as per the suggestion of Brian Beckman, see video link below).

If this helps you, great. I wrote this to help me, and it served that purpose. It's called "learn by doing" (practical, rather than theoretical). I therefore must also suggest that you try this yourself, rather than just expect to get it by reading this. I'm willing to concede that there are probably serious problems with these definitions, given that I am not a schooled Haskell programmer, and don't know a lot about the conventions that serious people follow.

I'd like to start by throwing down a few references which were helpful to me in my understanding:

• Brian Beckman: Don't Fear the Monads (video)
• Greg Meredith: Intro to Monads (video)
• Learn You a Haskell for Great Good (best "book" for beginners)
• James Iry's blog: One Div Zero

Now, those folks really know what they're talking about. Look to them for a real education. But, if you still want to see my rudimentary examples, here they are...

The two examples I implemented: the identity monad (the simplest of all!), and the state monad (because I really wanted to understand this for a project that I'm working on). Implementing the identity monad really helped me, because it's just so simple, yet has all the necessary properties of a "real" monad. State was far more difficult, mainly because of the fact that the monad wraps a function, rather than a value (although we know that these are the same thing in Haskell!), but once I cracked this, it really did "all make sense."

The Identity Monad

First, we need a type and type constructor (by Haskell convention I will use the same expression for both, which for this example is "Id").

 newtype Id a = Id a deriving Show  

Note: the "deriving Show" bit is there just in case I want to print these to the console. It could have just been:

Then I'm going to need a function to extract the value from the "Id" thingy:

 runId :: Id a -> a  
 runId (Id x) = x  

Simple enough, so far?

Note: this could also have been acheived using Haskell's "record syntax" as follows (saving the trouble of writing the extra function):

 newtype Id a = Id { runId :: a } deriving Show  

Now, the Monad bit. Don't blink, or you might miss it!

 instance Monad Id where  
  return a = Id a  
  m >>= f = f (runId m)  

Identity monad... done!

I'm not going to explain this in any great detail. You've probably read about "return" and "bind (>>=)" elsewhere. In bind: "m" is the monadic value, "f" is a function (a -> mb) and the bit on the right of the equals just says "run f on the value inside of m."

Some functions that operate on Id thingies:

 idPlusBar :: Id String -> Id String  
 idPlusBar x = do  
  y <- x  
  z <- Id (y ++ "bar")  
  return z  

This function operates on Id Strings appends "bar" to the value.

Note: the function above could be written more simply as:

 idPlusBar x = Id $ (runId x) ++ "bar"  

but I included it in long form for illustration purposes.

Here are a couple that operate on Id Ints:

 idPlusTwo :: Id Int -> Id Int  
 idPlusTwo x = Id $ (runId x) + 2  
 idTimesThree :: Id Int -> Id Int  
 idTimesThree x = Id $ (runId x) * 3  
 idComposed :: Id Int -> Id Int  
 idComposed = idPlusTwo . idTimesThree  

Now, here's a function ("main" in this case, as I can run this from the command line), which uses HUnit (you'll need to "import Test.HUnit") to test some assumptions:

 main = do  
  putStrLn "running tests"  
  -- Id String tests  
  let x = Id "foo"  
  let test1 = TestCase $ assertEqual "String foo" "foo" $ runId x  
  let test2 = TestCase $ assertEqual "String foobar" "foobar" $ runId $ idPlusBar x  
  -- Id Int tests  
  let y = Id 3 :: Id Int  
  let test3 = TestCase $ assertEqual "Int 3" 3 $ runId y  
  let test4 = TestCase $ assertEqual "Int 5" 5 $ runId $ idPlusTwo y  
  let test5 = TestCase $ assertEqual "Int 11" 11 $ runId $ idComposed y  
  -- run tests  
  let tests = TestList [ TestLabel "foo" test1  
     ,TestLabel "foobar" test2  
     ,TestLabel "int 3" test3  
     ,TestLabel "int 5" test4  
     ,TestLabel "int + *" test5  
    ]  
  runTestTT tests  

So far, none of this is too challenging. You may have noticed that there's absolutely no point to any of it, however. That's OK! The idea was just to get used to wrapping stuff up and operating on it. The first version of "idPlusBar" is interesting because it illustrates how things work in "do-notation."

If you've got this monad loaded up into ghci, you can see this, too:

 *Main> let x = Id "foo"  
 *Main> x  
 Id "foo"  
 *Main> idPlusBar x  
 Id "foobar"  
 *Main> let f x = x >>= \a -> Id (a ++ "bar")  
 *Main> f x  
 Id "foobar"  

where "f" doesn't use "do", but rather "bind" directly.

Now, if you're still with me, we shall leave the tidy, simple world of identity, and enter the mysterious wonderment that is "state."

The first part of this excercise involved coming up with a super simple case where I needed to have a state parameter of some kind and a bunch of functions that depended on it. I elected to make the State an "Int" and the value the functions operate on a List of Ints. The key is that in order to be sequenced correctly the state would have to be passed from one function to the next. The functions use the state int to transform the lists, and to add complication (and make it easy to prove it's working properly) I will increment the state with each function that gets executed.

As you probably know, you can do it by "threading the state" and not using monads at all. Let's try that first:

 addS :: Int -> [Int] -> [Int]  
 addS s xs = map (+ s) xs  
 timesSminus1 :: Int -> [Int] -> [Int]  
 timesSminus1 s xs = map (* (s-1)) xs  
 addStimes2 :: Int -> [Int] -> [Int]  
 addStimes2 s xs = map (+ (s*2)) xs  

where s::Int is the 'state' and the list is the thing to be transformed

Now we can sequence these functions, and "manually" increment the state:

 allS :: Int -> [Int] -> [Int]  
 allS s xs = let as = addS s xs;  
   s' = s+1;  
   as' = timesSminus1 s' as;  
   s'' = s'+1;  
   in addStimes2 s'' as'  

It's already easy to see, even with this simple example, that this has the potential to become quite cumbersome. It's also obvious that the incrementing of the state is going to get awfully repetitive and should be abstracted in some way.

Enter the state monad...

 type S = Int  
 newtype St s a = St { runState :: S -> (S, a) }  
 instance Monad (St s) where  
  return value = St $ \state -> (state, value)  
  monadSt >>= func = St $ \state->let (state', value) = runState monadSt state  
      in runState (func value) (state'+1)  

Note: this is not a generic state monad, but one which works exclusively on Ints and increments the state with each function execution (in "bind").

Here are our functions again, using the monad:

 addS' :: [Int] -> St Int [Int]  
 addS' xs = St $ \state -> (state,map (+ state) xs)  
 timesSminus1' :: [Int] -> St Int [Int]  
 timesSminus1' xs = St $ \state -> (state,map (* (state-1)) xs)  
 addStimes2' :: [Int] -> St Int [Int]  
 addStimes2' xs = St $ \state -> (state,map (+ (state*2)) xs)  
 allS' :: [Int] -> St Int [Int]  
 allS' xs = do  
   as <- addS' xs  
   as' <- timesSminus1' as  
   as'' <- addStimes2' as'  
   return as''  

The last function in particular is quite clean compared to its non-monadic cousin.

Once again, we'll use HUnit to test some assumptions...

 main = do  
  putStrLn "running tests"  
  -- set up some values to use  
  let xs = [1,2,3]  
  let state1 = 3  
  let state2 = 4  
  let state3 = 5  
  -- threading state tests  
  let test1 = TestCase $ assertEqual "increment by s" [4,5,6] $ addS state1 xs  
  let test2 = TestCase $ assertEqual "times (s-1)" [3,6,9] $ timesSminus1 state2 xs  
  let test3 = TestCase $ assertEqual "increment by s*2" [11,12,13] $ addStimes2 state3 xs  
  -- put it together in allS  
  let test4 = TestCase $ assertEqual "the lot" [22,25,28] $ allS state1 xs  
  -- state monad tests  
  let test1' = TestCase $ assertEqual "m increment by s" [4,5,6] $ snd $ (runState $ addS' xs) state1  
  let test2' = TestCase $ assertEqual "m times (s-1)" [3,6,9] $ snd $ (runState $ timesSminus1' xs) state2  
  let test3' = TestCase $ assertEqual "m increment by s*2" [11,12,13] $ snd $ (runState $ addStimes2' xs) state3  
  -- monadic state passing in allS'  
  let test4' = TestCase $ assertEqual "m the lot" [22,25,28] $ snd $ (runState $ allS' xs) state1  
  -- run tests  
  let tests = TestList [ TestLabel "test1" test1  
     ,TestLabel "test2" test2  
     ,TestLabel "test3" test3  
     ,TestLabel "test4" test4  
     ,TestLabel "m test1'" test1'  
     ,TestLabel "m test2'" test2'  
     ,TestLabel "m test3'" test3'  
     ,TestLabel "m test4'" test4'  
     ]  
  runTestTT tests  

The real eye-opening thing here is that allS' doesn't take a state parameter at all. That's because allS' is returning a state monad (a function from state to state,value). So, we pass the state to the function (or value) which is returned by this function. This is the trick... and it is a little bit like magic!

So,

allS' takes the list ("xs") and returns the monad. runState extracts the function from the monad (\s -> (s,a)), and we pass the initial state to that. That in turn returns the state,value pair, so we take the "snd" value of the tuple.

This is it again:

 snd $ (runState $ allS' xs) state1  

Nice, huh?

So, our function doesn't have to mess around with state at all. It's all handled in the monad's bind function, including the incrementing of the state's value with each function call.

Once again, I would just add that the most striking thing in all this is its simplicity (a trait I've come to expect from Haskell). It seems that monads weren't that complicated after all.

Now, what are these Monad Transformer things?