Do-notation considered harmful

12Dec06

16:20:11 [Botje] monads have to be the singly most tutorialized feature _EVER_

16:20:17 [monochrom] Why would such a mathematical, abstract tool attract so many popular science authors who do not explain the tool in its mathematical, abstract term?

(from #haskell@irc.freenode.net)

Monads are certainly the single most visible feature of Haskell. Being the standard tool to tackle the awkward squad (input/output, concurrency, exceptions, and foreign-language calls) and producing side-effects in general, every Haskell programmer needs to face monads at some point, and yet the very need to do so appears, for many people, to be a hair shirt to be worn in the name of purity and referential transparency.

There is, of course, a host of reasons for this uneasiness about monads — from its dark and unwieldly name, straight from the depths of category theory to the very culture shock between the imperative world (where side-effects are trivial and abstraction is fragile and bolted-on) and the functional world (where abstraction is trivial and side-effects require deep mathematics). Nevertheless, I feel there’s an important barrier to understanding monads: its very syntactic sugar.

Do-notation gives monadic programming a pseudo-imperative feel. Monadic IO, the way it’s first presented by the popular tutorials, feels like a bolted-on quasi-imperative mode to Haskell, added as an afterthought due to the need to communicate with the outside, time-indexed world. Do-notation — and the fact that it’s introduced in the context of IO — obscures the fact that monads are implemented quite simply in Haskell itself as a type-class and correspond to a simple algebraic structure that models many useful computational phenomena.

The treasure chest is, of course, in the Haddock documentation for Control.Monad, but to unlock it we first need to un-do do-notation.

There are simple rules for converting function definitions between do and “bind” notation; these can be simply explained, and are documented elsewhere. What I’m interested in doing here is not exploring the syntactic conversion, but restating the basic lessons about IO in terms of bind-notation — so the monadic structure can be more clearly seen.

The two most important IO operations are probably putStr and getLine. These are roughly equivalent in functionality to print and read in Lisp/Scheme, PRINT and INPUT in Basic and so on. Haskell being a purely-functional, typeful language, these operations are probably expressed as functions whose type is worth examining.

We first examine the type of putStr:

putStr :: String -> IO ()


(We take that the reader already knows how to read a type declaration). Evidently. putStr has to be something that takes a string as an argument. The result of that function could be read as “Outside World” — in fact, if it wasn’t such a verbose expression, OutsideWorld could be a synonym to IO. Let’s examine the type of getLine now.

getLine :: IO String


getLine takes no arguments and is merely a string from the outside world. Being an outsider string, we can’t do much with this string, though — which is where monads come along. Once monadic structure is added to the IO problem, we can use some simple functions to act on the variable, non-referentially transparent, value of getLine.

The first of such function is “bind” — named as the infix operator >>= for convenience. Its type is

(>>=) :: forall a b . m a -> (a -> m b) -> m b


“Bind” takes a monadic value (in our example, an IO String), a function that goes from a pure value (in our case, String) to a monadic value, and returns a monadic value. An example of its use follows:

shout = getLine >>= (putStr . map toUpper)


The first argument to bind is a monadic value of type IO String, and the second argument is the function (putStr . toUpper), which takes a string and produces an IO “coin” IO (). As expected, the type of “shout” is an outside-world value — that is, an IO “coin”:

shout :: IO ()


The second basic function that defines a monad is return. Its type is

return :: (Monad m) => a -> m a


For example, the type of

superTwo = return "Two"

is trivially

superTwo :: (Monad m) => m String


These two functions define entirely a monad; all other useful monadic functions can be defined from them. To characterize a proper monad, the following three mathematical properties should apply:

1. (return x) >>= f == f x
2. m >>= return == m
3. (m >>= f) >>= g == m >>= (\x -> f x >>= g)

We can, therefore, define monads entirely in Haskell — which shows that it’s really not a bolted-on feature, but an abstract mathematical structure that exploits Haskell’s ease with expressing abstract mathematical structures such as rings, borelians, quaternions… and monads:

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


Instances of monad you’ve probably already worked with in basic Haskell learning are cons-lists ([a]), Maybe and, yes, IO. The way “bind” and “return” are defined for each specific instance can be found in a monad tutorial. Not wanting to write yet another monad tutorial, we stick to the IO monad from now on.

From (>>=) and return such that the aforementioned properties apply many useful operations can be constructed — extensively documented at the Haddock documentation for Control.Monad. For our purposes, we need to study one more function — a variant of “bind” that discards the result of its first argument (the computation to which it’s being applied) so that we can simply sequence unrelated operations. The type of this function is

(>>) :: (Monad m) => m a -> m b -> m b


From our description, it’s trivial to construct (>>):
x >> y = x >>= (\_ -> y)


This is how, for example, we sequence two putStr operations (remember that putStr isn’t interested in the () result of a previous putStr):

example = putStr "Print me! \n" >> putStr "Print me too! \n"

We can now construct a simple example of monadic IO in the bind notation:

greet = getLine >>= (putStr . ("You're "++) . (++" years old! \n")) >> putStr "Congratulations! \n"


Here, the “contents” of the String inside the IO String are used inside of the function

\x-> ((putStr . ("You're "++) . (++" years old! \n")) >> putStr "Congratulations! \n") x.

This, in turn, is interpreted as

(\x-> ((putStr . ("You're "++) . (++" years old! \n")) x) >>= (\_ -> putStr "Congratulations! \n")


which just sequences the two printing actions. This mathematical structure describing sequencing happens to have, in Haskell, syntactic sugar that allows you to side-step the complicated juggling of parens, lambda abstractions and point-free expressions and notate sequencing in pseudo-imperative (not quasi-imperative) form:

greet = do {
age <- getLine;
putStr ("You're "++age++"years old! \n");
putStr ("Congratulations! \n");
}


Despite its imperative appearance, this is emphatically not imperative code setting a variable: we merely have convenient syntax for storing the result of monadic computations (here, reading from the “outside world”) in a symbol so we can later manipulate it without passing the argument forward through ever-larger lambda expressions.

Now that the gentle reader is aware of the superficial, throwaway nature of do-notation, he can proceed with his study of basic Haskell or monads. More importantly, he can later understand what do-notation means when he’s dealing with useful, nontrivial instances of this mathematical structure like monadic parsers.

In fact, as a matter of intellectual discipline and sanity, I’d recommend that bind notation was used in every “toy”, learning project the aspiring Haskell programmer cooks up in his path until the necessary pile of ever-larger functions really exceeds his mental stack space. While not absolutely essential to get the simple IO problems done, understanding the fundamental difference between sequencing and side-effects as in a traditional imperative language and the combination of IO functions via the bind operator is of utmost importance in the process of learning to think in Haskell and ditching the “robot with a detailed recipe” model of programming.

Filed under: For newcomers, How to teach Haskell, Mathematics and Haskell   |  21 Comments