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.

About these ads


15 Responses to “Do-notation considered harmful”

  1. 1 Matley

    Cool post. I am new to Haskell and I start only now to understand fully the monads, thanks to this article.

    You also convinced me that do-notation is harmful for a haskell beginner as ‘ instead of quote is for a lisp newbie.

  2. 2 Matthew

    Good points.

    Personally, one of my greatest pet peeves about haskell is the (relative) inelegance of composing monads. Almost all the code I’ve seen that uses monad transformers looks kinda hacky. I think the haskell folks need to think long and hard either about improving the semantics somehow to make monads more easily composable, or creating some kind of improved syntax to make layering monads look and feel less fugly.

    My other main irritation with haskell is the massive over-use of strings of ascii symbols for meaningful operators / functions. It makes code start to look like line noise. It seems lots of haskell libraries add their own three or even four-character operator symbols to the already over-full namespace, and it JUST WON’T DO, you hear me! *cough* In other languages these things are mainly just used as punctuation, and that’s the way it should be!

  3. 3 Ben Franksen

    “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…”

    Should be “(putStr . map toUpper)” as in the code block preceding the paragraph.

    (no need to add this comment to the page)

  4. 4 Ben Franksen

    “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.”

    I have to disagree with the assessment that “this is [...] not imperative code”. To the contrary, I think that it is imperative code /par excellence/. To see this, it helps to remember that the first use of monads in computing science was to give formal semantics to imperative (and other ‘effectful’) language constructs. Such a semantics more or less amounts to a translation into some other (simpler) language, which is usually purely functional and often call-by-name. What monads in Haskell give you and ordinary imperative languages don’t, is that here you can see the semantics at work, and furthermore you can work /with/ the semantics e.g. by writing your own control structures as higher-order functions. Basically, with monads computational effects become expressable as embedded (sub-)languages.

    I agree, however, that the do-notation can be misleading, insofar as it is tailored to imperative effects. If the monad happens to express some other form of effectful computation (e.g. backtracking as in Prolog) then do-notation is not a great help and can even obscure the meaning.

  5. 5 Derek Elkins

    Actually, do notation is hardly necessary, about the only thing it really saves on is refutable patterns.


    do
    a


    m >>= \a ->
    f a >>= \b ->
    return (a+b)

    A bit uglier, but not any more complex, in particular, the parens are not necessary so you do not have to deal with matching a bunch of them.

  6. 6 Derek Elkins

    (now with 50% less bad HTML formatting)
    Actually, do notation is hardly necessary, about the only thing it really saves on is refutable patterns.


    do
    a <- m
    b <- f a
    return (a+b)


    m >>= \a ->
    f a >>= \b ->
    return (a+b)

    A bit uglier, but not any more complex, in particular, the parens are not necessary so you do not have to deal with matching a bunch of them.

  7. todo este lío e incluso hasta poner una mini-entrevista realizada a Moot (ganador de la encuesta). La anotación titulada “Moot wins, Time Inc. loses” [en inglés] (bastante entretenida por cierto) hace énfasis en la traba que ponen en estos casos

  8. I like this post, enjoyed this one thanks for posting. “To the dull mind all nature is leaden. To the illumined mind the whole world sparkles with light.” by Ralph Waldo Emerson.


  1. 1 Reddit discussion considered productive « Data.Syntaxfree
  2. 2 teideal glic deisbhéalach » Blog Archive » Haskell: bootstrapping into a clue about monads
  3. 3 Refining my first steps with Parsec « lstephen
  4. 4 HSOE Chapter 3 « Lambdakjöt
  5. 5 dayvan cowboy » Blog Archive » Reddit discussion considered productive
  6. 6 Do-notation有害论 : Fleurer.Lee
  7. 7 Anonymous

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s


Follow

Get every new post delivered to your Inbox.

%d bloggers like this: