Haskell: write yourself a Monad in almost no time (3)

If you came here without having read any of the previous posts you may wish to do so here and here.

We just turned our parser into a Monad by adding

instance Monad Parser where
   return = inject
   (>>=) = chain


To see the benefit this gives us let’s return to our parser chain.
We can now express it like this:

mchain1 = do
   a <- item
   b <- item
   return [a,b]


Previously we had written

chain2 = chain item (\a ->
   chain item (\b ->
      inject [a,b]))


We still use the same variables and the same result, but the chaining itself actually got simpler. And the longer the chain, the more we gain with the Monad’s machinery.
And all this without any magic. By saying

instance Monad Parser where
   return = inject
   (>>=) = chain

we turned our Parser into a Monad. All previous code will still work, but in addition to that we can now use the syntactic sugar that Monads provide (do-notation).

Before we analyze that sugar in more detail let’s first have a look at the Monad instantiation of Parser. A Monad instance must provide at least two functions, return and >>=. Since our parser already came equipped with everything necessary, we just had to tell GHC (or whatever you’re using), that it should use the appropriate methods: chain as our implementation of >>= and inject as implementation of return.

While inject is rather straightforward (it just returns its argument as the result of the parse and doesn’t touch the input), chain may eventually require a little more thought to understand. The most interesting part is actually the last line:
(Just a, x) -> parse (f a) x

In case the first parse succeeded we have its result in a and the remaining input in x.
Executing f on the result gives us the parser we then use to parse the remaining input.

So, without using the Monad’s machinery we essentially had to manually build a function f that would give us a parser doing the second parse and combining it with the result of the first parse.
When using the Monad machinery we just make two parses (they’re chained implicitly by the Monad) and return the combined result. No manual function generation!

Note that the values are sort of “extracted” from the parser monad: our chain function determines the value to be “extracted”. The ParseState remains hidden behind the scenes. The return then wraps our values again.
Note, too, that pattern matching can extract the value in very much the same way.
Instead of
parse (do a <- item; "-> use value of 'a' <-") input
you can write
case parse item input of (Just a, _) -> "-> use value of 'a' <-"
In both cases will the parse value be bound to a.

Let’s now make the Monad’s syntactic sugar more explicit:

mchain1 = do
   a <- item
   b <- item
   return [a,b]

is the same as

mchain2 = do
   item >>= (\ a ->
      item >>= (\b ->
         return [a,b]))


which is the same as (substituting our own function names):

mchain3 = do
   item `chain` (\a ->
      item `chain` (\b ->
         inject [a,b]))


which is identical to

mchain4 = do
   chain item (\a ->
      chain item (\b ->
         inject [a,b]))


Compare this to

chain2 =
   chain item (\a ->
      chain item (\b ->
         inject [a,b]))

🙂

[The code for this part can be downloaded here.]