Good Math, Bad Math

The biggest nightmare for most people learning Haskell is monads. Monads are the
key to how you can implement IO, state, parallelism, and sequencing (among numerous other things) in Haskell. The trick is wrapping your head around them.

On the most basic level, they’re actually pretty easy to understand. Think about something like IO in purely functional terms. When you write a function that performs an IO action, what are you really
doing in terms of functions? For the moment, ignore all practical concerns, and just think in the
pure abstract: what happens when you do an output operation?

What happens is that you write some data to some entity accessible to the program. In purely
functional terms, you can think of taking a snapshot of the entire state of stuff accessible to the program both before and after the output action. Then the output operation is a function
from the state before to the state after. In pseudocode:

data StateOfEverything = ...

print :: String -> StateOfEverything -> StateOfEverything

Now, suppose you want to perform two IO actions in sequence – like printing “Hello world” by printing “Hello” and then printing “world”. What’s going on there?

What’s going on is that you’re chaining functions together, so that the state which
is the output of one function is the input to another.


printHelloWorld stateBefore =
    let stateAfter = print "Hello" stateBefore
    in print " World" stateAfter

Writing things that way – passing the state returned from one statement as a parameter to
the next one – is a pain. It’s messy, hard to read, and generally unpleasant. So why not just
do an abstraction? Just write a combinator, for chaining together calls. (A
combinator is a function which takes other functions as parameters for the purpose of combining or modifying them in some way.)

chain :: (x -> x) -> (x -> x) -> x -> x
chain firstfun secondfun initstate =
    let nextState = firstfun initstate
    in secondfun nextstate

printHello stateBefore =
    print "Hello" stateBefore

printWorld stateBefore =
    print " World" stateBefore

printHelloWorld stateBefore =
    printHello `chain` printWorld

That’s pretty much what a monad does. There’s a bit more to it – the combinator needs to behave
in certain ways – but the central concept is that the monad is a kind of combinator that enables
sequential chaining with the transfer of an internal state object between steps. Haskell also
provides some nice syntax in the form of “do” expressions and a ton of flexibility in
terms of monad parameters – but the most basic thing going on in monad code is that basic chaining of
a state parameter from call to call in a sequence.

Now, let’s look at doing what I just did with “chain”, only do it using the Haskell IO monad:

	
>printHello ::  IO ()
>printHello  = print "Hello "
>
>printWorld ::  IO ()
>printWorld = print "World"
>
>printHelloWorld ::  IO ()
>printHelloWorld  = do
>                      printHello 
>                      printWorld

As you can see, there’s a monad type IO, which is an object encapsulating
the IO state. You can’t see inside of it – the IO state itself is completely hidden, and
inaccessible to any code outside of the implementation of the IO monad. But what it does is combine
functions so that the IO state returned by one operation is passed on to the next in sequence. It’s really just like the chaining operator – but with a really nice syntax, and a lot more flexibility.

To see why it’s more flexible, let’s start by breaking down the “do” syntax, and see what’s really going on. The do statement in the code example above is equivalent to the following:


>printHelloWorldWithoutDo :: IO ()
>printHelloWorldWithoutDo = printHello >>= (\ x -> printWorld)

One of the things that the “do” syntax does is expand each expression after the
first in the do so that the result value of each expression is passed as a parameter to the next. So
in addition to just passing the IO state internally, it also allows the programmer to pass their own
value from one element of the sequence to the next. To see just how flexible that is, let’s take a
moment, and look at the actually type of “>>=“.

*Main> :type (>>=)
(>>=) :: (Monad m) => m a -> (a -> m b) -> m b

Let’s piece that apart. First, monads are type-parametric – meaning that, for example, “IO” isn’t a type; “IO x” is a type – an instance value of the IO monad carrying a payload value of type x.

The monadic sequencing parameter takes two parameters. The first is a monad value with a payload of type “a”. The second is a function which can be chained with the first – so it needs to take a parameter value who type is the type of the payload carried over from the first – so it’s a function from a value of type “a” to another monad value – but it doesn’t need to return the
same type as the first
– it doesn’t need to return an instance of IO a. It can return whatever type of payload it wants – so the type of the second parameter is a function from a value of type a, to a monad carrying a value of type b.

What this means is that there’s a huge amount of flexibility in how we can pass values
between steps of a monad! My naive chain operator required everything in a sequence to take and return values of exactly the same type; the actual monadic chaining operator allows each step of a monadic chain to take different types as input, and return different types as output – so long as the value returned by one step matches the parameter type accepted by the next.

Let’s take a look at how this value-carrying stuff can actually be really useful – and at the same time, get a look at the other really wonderful thing about Haskell’s do syntax.
Suppose we want to write the usual follow-on to a hello world program – that is, a program that
asks for the users name, and then prints out a hello message using it. Here’s the
program as a Python function:


def FancyHello():
   print "What is your name?"
   x = sys.stdin.readLine()
   print "Hello ", x

How do we do that in Haskell?


>fancyHello :: IO ()
>fancyHello =
>    do
>       print "What is your name?"
>       x <- getLine
>       print (concat ["Hello ", x])

In addition to the simple chaining, Haskell do statements allow us to bind
the payload returned by a step in a monadic sequence to a pattern, and then use the names defined by that pattern throughout the rest of the do statement. So, since “getLine” has type “IO String“, in the body of a “do” statement, “getLine” can be treated as a function that returns a string – and the result of it can be bound to a variable using the “<-" operator.

There are a couple of tricks to using monads. Suppose in our fancyHello function,
we wanted to return the hello string with the users name, instead of printing it. You might think that we could do something easy like:


fancyHW :: String
fancyHW =
   do
      print "What is your name?"
      x <- getLine
      concat ["Hello ", x]

But if you try to put that through a Haskell compiler, you'll get a type error. You see, there's no way out of a monad. Once you're inside a monad, there's no way out. It's a closed world. You can't get out of it. So you can't return an input string from the IO monad without the IO state associated with it by the monad. So fancyHW can't return "String"; it must return "IO String". Based on that, you might think that
the fix would be to just change the declaration in the code above to:


fancyHW :: IO String
fancyHW =
   do
      print "What is your name?"
      x <- getLine
      concat ["Hello ", x]

Again, it doesn't work. concat returns a value of type String, not
a value of type IO String. How do we generate a value of type IO String? There's a function return, with type (Monad m) => a -> m a. What return does is wrap a non-monadic value into the appropriate monad type, so that it can be used as an element in a monadic sequence. So let's look at the correct version of
"fancyHW":


>fancyHW :: IO (String)
>fancyHW =
>   do
>      print "What is your name?"
>      x <- getLine
>      return (concat ["Hello ", x])

This works, but it's actually a bit deceptive. In fact, return is a bit deceptive -
it makes monadic code read more clearly in some cases, but it can also be very misleading, because it
does not return a value from the "do" statement; it just wraps a non-monadic
call, so that it can be enclosed in a monadic sequence. Let's look at a variation of the above
to see why it can be confusing. This is a bit artificial to make it short, but it illustrates the point.


>generateHelloMessage :: String -> String
>generateHelloMessage name = concat ["Hello there ", name, ", how are you?"]
>
>fancyTwo :: IO ()
>fancyTwo = do
>              print "What is your  name?"
>              x <- getLine
>              msg <- return (generateHelloMessage x)
>              print msg

See, the return call isn't returning a value from the do statement, it's just wrapping a non-monadic call so that it can be a participant in a
monadic sequence.

This isn't all there is to know about monads; this is just barely scratching the surface. We'll go farther with it in the next few posts. We'll go through some more details of the IO monad,
show a couple of other monad types, how to define your own monad types, and show a wonderful example of monads as glue: you can write YACC-like parser code in Haskell without a parser generator,
using a parser monad!

Comments

  1. #1 Doug
    January 23, 2007

    Hi Mark

    I am still trying to interest you in mathematical game theory. Please consider the following game theory work since monad is within category theory.

    Paul-Andr̩ Melli̬s [Google can translate French into English] Рvintage talks
    1 – ‘Functional boxes in string diagrams’, CSL 2006
    2 – ‘Asynchronous games: a fully complete model of propositional linear logic’, LiCS 2005
    http://www.pps.jussieu.fr/~mellies/

    Mellies [University Denis Diderot] is a “member of the committee of program of the conference Computer Science and Logic 2007″.

    Categories, lamda calculus, intuitionistic linear logic and game semantics [Conway] are introduced [latter in slide 64/88] talk 1.

    Tensor products, various strategies and intuitionistic linear logic are dicussed in talk 2. [Tendency to sigma rather than lamda calculus when a stochastic game.]

  2. #2 alpha
    January 23, 2007

    I think that monads are not so complex but the problems with most monad tutorials are:

    1 – They focus on the IO monad which is a bit special ;
    2 – They explain more how monads are implemented rather than how to use them (specially for the State monad).

    I have myself written a very short monad tutorial where I try to present different use : sequencing, side effect, container. It is very short probably too short but it may interest your readers.

    I am looking forward to reading your next posts about monad. It was a good idea to start this serie of posts about Haskell. Haskell is COOL !

  3. #3 Mark C. Chu-Carroll
    January 23, 2007

    alpha:

    I mostly agree with you. I do think too many introductions to
    Haskell spend a lot of time on the formalisms of monads, and not enough time on just how to actually use them in practice.

    On the other hand, I think that at least initially focusing on the IO monad makes sense: for a beginner to Haskell, like someone who’s been following these tutorial posts, how IO works in a functional language is a big question, and a lot about how IO works just doesn’t make sense without monads. (How do you explain that silly “return” statement there in the middle of a do without understanding a bit about monads, and how they’re put together?)

    I’ll be getting to the state monad soon. It’s actually my favorite for explaining how to implement your own monads.

  4. #4 Dane Jensen
    January 24, 2007

    I’m still learning Haskell, and that’s one of the clearest explanations of Monads I’ve seen yet. So many others try to wrap them up in so many layers of complexity that the fact that they’re really pretty simple gets lost.

  5. #5 Harald Korneliussen
    January 24, 2007

    I agree with Dane that this was one of the more clear presentations of monads. Monads are sometimes presented as containers, sometimes as computations, but while they may or may not be about those things, they are always about chaining actions together.

    The point that the IO monad is quite special is a trap that it seems to me you’ve fallen into: You say that there’s no way to get a value out of a monad, which is true for IO, but certainly not for List or Maybe:

    getOut :: Maybe Int -> Int
    getOut Nothing = 0
    getOut Just x = x

  6. #6 Brent
    January 24, 2007

    Thanks Mark! I think Haskell is awesome but I’ve never understood monads (which, as I gather, means I’m missing out on a lot of awesomeness). So this whole time I’ve been just waiting for you to get around to them. =) I’m pretty sure I understand everything you wrote in this post… although I’m still not sure exactly what the purpose of monads is, how they fit into the theoretical framework. I presume this will become clearer in your future posts, which I look forward to reading!

  7. #7 Justin
    January 24, 2007

    I have to agree with the others here – you’ve written an excellent introduction to monads. It took me months to realize the key thing about monads was they carried this extra parameter around with them. I’m glad you put it right up front!

  8. #8 Casey Williams
    January 30, 2007

    I also agree with the others. I’ve been doing a lot of reading about monads lately, and this article has done a really great job of explaining it. I think all I need now is some good hands on experience. :)

    And thanks for explaining the ‘return’ function so clearly. I was a bit fuzzy on that until now.

  9. #9 Masklinn
    January 30, 2007

    Mark, may I ask while you’re using `concat` and bothering with creating a list (in 4 out of your 5 last examples) when you could just use (++) to concatenate “Hello” and the string in `x`?

    `concat` is useful for concatenating list, but it’s a bit overkill (and doesn’t help readability) if you just want to concatenate a pair of strings, I think.

  10. #10 Jason Orendorff
    February 8, 2007

    Just to be contrary, I have to disagree. I think this monad tutorial is around the 60th percentile, as these things go. The sad fact is, monads just don’t fit into a blog post. :(

    Thanks for trying, though, Mark! Love the blog!

  11. #11 Panos
    October 31, 2007

    Hi, can you please explain the difference between Monads and function composition? Both seem to carry around a variable

The site is undergoing maintenance presently. Commenting has been disabled. Please check back later!