A tutorial for writing monad tutorials (part I)

(Somewhere between a parody, a caustic statement on the state of Haskell
monad tutorials and real advice.  My tongue is firmly in my cheek and
apologies to all those I'm about to insult.)

There's been a nasty little thread on the Haskell mailing list today
where a million people have tried to explain monads to a hapless
learner.  Reading the responses, if I were the learner, I'd be confused,
overwhelmed but inspired to learn more about these deeply confusing
magical amazing things that no-one knows how to explain, but everyone
has a story about (how they think) monads clicked for them.

Here's my take on how to explain monads:  (Ah how easy it is for me here
in my ivory tower where I'm right and the world is wrong :p ).

First off, one rule:

1) DONT USE THE WORD 'MONADIC'

It's meaningless.  Utterly meaningless, unless you know what it means.
Which the person you're explaining to won't.  Remember that.  You are
explaining to someone who has been confused by "warm fuzzy things" and
Java.

Ok.  So my approach to explaining 'monads':  

a) Start with something they can can relate to: Everyone suffers through
gang-of-4 stuff nowadays, right? (right?)

In Haskell there are several design patterns for structuring code.
Unfortunately, while the Java people got all the sensible names like
"Visitor", and "strategy" and "factory", the Haskell people were left
with the boring maths books at the back of the library to seek
inspiration from.  So we have "The monoid pattern", "The applicative
pattern", "The foldable pattern", "The arrow pattern" and "The monad pattern".

b) Ground this a bit

So what does a design pattern in Haskell look like?  

Well usually it consists of the general pattern bit:
  * A type class 
  * Some functions in that type class
  * Some useful combinators implemented in terms of the type class

And the instances of the pattern:
  * A data type that is an instance of the type class
  * Some special functions that let you do instance specific things.

c) Example time.  Don't jump straight to monads, tease them a bit first.

So for example.  The "monoid pattern" lets you have a uniform interface
for interacting with data types that can be empty or glued together[1]

The general bit:

  class Monid a where
    mempty :: a
    mappend :: a -> a -> a

And a useful combinator: (e.g. sqaushing a list by gluing all the elements together)

    mconcat :: Monoid a => [a] -> a
    mconcat = foldr mappend mempty

The specific instances: For example, to let you easily Sum numbers:

newtype Sum a = Sum a

instance (Num a) => Monoid (Sum a) where
  {- an empty sum is 0 -}
  mempty = Sum 0
  {- summing two numbers is, er, summing them :) -}
  mappend (Sum x) (Sum y) = Sum (x + y)

And a special function to let you do a Sum specific thing:

fromSum :: Sum a -> a
fromSum (Sum x) = x

So why is this useful?  Well if I have list of numbers, I can easily sum
them now!

sum :: (Num a) => [a] -> a
sum = fromSum . mconcat . (map Sum)

Use another example (Data.Monoid.First is a nice one, [a] could be
trickier as mappend uses a [a] too which is a bit of a pain) if they're
looking lost and confused, to help ground the one design, many
instances, common interface, but datatype specific bit.

Great.  So now you've hopefully explained a design pattern in Haskell to
your audience.  And also filtered out about 50% of people who don't
really care enough.  The next two lines should be obvious:

  So monads are just like that.  Except in the category of endofunctors.

If you do say that, you need a slap.  While it's a cool sentence to
memorize incorrectly and throw out, only two people on #haskell
understand what it means (and I'm smart enought to realise that you're
not one of them.  (and to be fair, neither am I)).

So the monad pattern.
Well anyone who has looked at too many monad tutorials can probably by
rote tell you the general bit:

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

IF AT THIS POINT YOU SAY ***ANYTHING*** ABOUT FAIL BEING A WART YOU HAVE
YOURSELF FAILED.  We don't care about niceness at this point.  You can
only appreciate why fail is bad once you understand what the Monad
pattern is about.  Clouding the issue now isn't helpful.  Giving
knowledge without understanding is dangerous - it leads to wars, and php
programmers.


There are also lots of combinators defined in terms of just 'Monad', we
are going to introduce just one:

when :: Bool -> m () -> m ()
when True x = x
when False x = return ()

Make sure they understand the types that are going on here.  Also
probably need to soothingly remind them that 'return' is not some
syntactic land that Haskell captured during the great language war of
'88, it's just a function, like mappend, it's nothing special.  (Hear
that return, you are NOTHING SPECIAL! YOU ARE IN-FACT QUITE BORING.)


So this is great.  But what does that 'Monad' type class mean or let you
do? Well the problem is, it is very very general, and lets you do lots
of different things.  (In retrospect, don't say that, it doesn't really
say anything).  Lets work through some examples of the instances to see
the kind of things it can do:

Example instance 1: Maybe.

The good 'ol Maybe type.

  data Maybe a = Nothing | Just a

  My favourite example (stolen from elsewhere, probably the Haskell
  wiki), division by zero!

  safeDivide :: Int -> Int -> Maybe Int
  safeDivide x 0 = Nothing
  safeDivide x n = Just (x `div` n)

  
  divide3 :: Int -> Int -> Int -> Maybe Int
  divide3 x y z = case x `safeDivide` y
                    of Nothing -> Nothing
                       Just a  -> a `safeDivide` z

  
Those cases are yukky.  However if we had a function:

  withInsides :: Maybe Int -> (Int -> Maybe Int) -> Maybe Int
  withInsides (Just x) f = f x
  withInsides Nothing _ = Nothing

then we could make it a bit neater:

  divide3 :: Int -> Int -> Int -> Maybe Int
  divide3 x y z = (x `safeDivide` y) `withInsides` (\a -> a `safeDivide` z) 


AT THIS POINT YOU WILL FEEL INCREDIBLY TEMPTED TO SAY 'But look,
withInsides is just >>=.  It's a monad! Isn't that amazing! How useful
and cool is that! Wow!'  But for the love of
whatever-you-do-or-do-not-believe-in PLEASE DON'T.  It turns out that
realising that 

  Maybe Int -> (Int -> Maybe Int) -> Maybe Int  
    can unify with
  m a -> (a -> m b) -> m b                      

  IS NOT SOMETHING THAT MOST PEOPLE CAN DO TRIVIALLY.  You can probably
  only do that because you've seen the pattern so many times you've
  memorised it.  IT TAKES TIME TO SEE IT, AND IT TAKES EVEN LONGER WITH
  SOMEONE GUSHING IN YOUR EAR ABOUT HOW YOUR EXAMPLE SHOWS YOU WHAT YOU
  WANT IT TO SHOW YOU!


Right, I'm off to the pub now.  I'll try and carry this on later.  Just
a note of where I was heading with this little bit of it.

  safeDivide :: (Monad m) => Int -> Int -> m Int
  safeDivide x 0 = fail "Can't divide by zero"
  safeDivide x n = return (x `div` n)


[1] Yes I've butchered the definition of Monoid here.  I don't care.
Data.Map butchers it's definition of Monoid too. "instance (Ord k) =>
Monoid (Map k v)" HA! It should be "instance (Ord k, Monoid v) => Monoid
(Map k v)".