Monads 6
I’ve been following Adam Turoff’s excellent Haskell tutorial and he’s just reached the part where he explains Monads.
To listen to a lot of people, Monads are the bit of Haskell that breaks their brains. As they’re usually described, Monads are the part of Haskell that allow you to write code that has side effects. You know, stuff like reading a file or generating a random number.
What most of the tutorials I’ve read don’t do is explain why Monads let you use side effects. Or, to put it another way, why you can’t successfully use side effects in Haskell without them.
Monads wrap up the concept of a sequence of actions in something that looks, from outside the Monad, like an other datatype. It clicked for me when I remembered something from a course on Set Theory when I was an undergraduate mathematician. The thing about sets is, they’re not ordered. {a, b} is the same set as {b, a}. However, when you’re busily constructing all the entities that get used in mathematics from the Zermelo/Fraenkel axioms, you eventually need to build ordered pairs of numbers. Coordinate systems for example, make heavy use of ordered pairs.
So, if you’ve got sets, which are not ordered, and you need to build a set which can be interpreted as an ordered pair, how do you proceed?
The standard method is to represent the ordered pair, (x,y) as { {x}, {x, y} }. Look at the Wikipedia article if you want the gory details.
So, an ordered pair is just a handy notation for a slightly more complicated, unordered, set.
Monads are a generalization of this principle; in a sense, the details of how they work are irrelevant (in the same way that the innards of an ordered pair are irrelevant), what’s important is that they provide a box in which ordered execution can happen. And ordered execution is what you need if you want to write code that uses side effects or works with impure ‘functions’ that don’t always return the same value given the same input.
Monads can seem so mindbending because most of us come from a programming background where ordered execution is all there is. In pretty much every mainstream language, the idea that the programmer doesn’t control the order in which code is evaluated seems utterly outlandish. Monads look weird, then, because we’ve never thought of the problem they solve as a problem in the first place. It’s just how programs are.
Maybe it’s time we tried to let go of that assumption. Or maybe I’ve completely misunderstood monads.
It’s probably the latter.
Updates
Someone commenting on this post at reddit.com points out that monads aren’t solely used for wrapping sequential processing; they can be used to wrap pretty much every model of computation you could come up with. Which, I must admit, hadn’t quite clicked with me, despite realising that Parsec, a Haskell parser combinator library, was monadic but wasn’t really about sequential processing because the Parser monad also handled backtracking.
So, it seems that I’ve incompletely misunderstood monads.
Hi Piers, I don’t know if you’ve seen this, but Simon Peyton-Jones gave a great 3-hour introduction to Haskell, all on video: Part 1 , Part 2 .
It’s aimed at someone with no experience of Haskell, so he doesn’t really explain monads in any depth, although he does explain how to work with IO.
He gives some great insights into the thinking behind Haskell (and how he thinks it’s ready to take over the world!)
You need to get a copy of his slides to really appreciate it.
Cheers, Michael
All the talk about monads led me to believe that they were the core of Haskell. I took a Haskell tutorial at OSCON taught by Simon Peyton-Jones. It was three hours and he didn’t even mention monads. At the end, I asked “What’s a monad?” and his answer was, “It’s ten minutes after five. All done!”
Afterwards he explained it, though. I think you pretty much nailed it there. I think also that monads aren’t actually that crucial to Haskell, they just get a lot of attention because they seem so puzzling at the outset.
Michael: About 10 seconds after I hit the ‘save’ button on this post, I hit ‘play’ on Simon Peyton-Jones’s OSCON tutorial and opened up the slides to follow along. I need to see the second part, but I really enjoyed the first half.
I was particularly delighted that they fetched him a whiteboard.
Tangentially, I also loved the bug in the slide towards the end of the first part and the way that he dealt with it – I was reminded of a story about Turing’s paper in which he describes the Turing machine, implements a Universal Turing Machine, proves the halting problem is insoluble and generally reshapes the world. The thing is, there’s at least one bug in the UTM implementation. One’s a glaring typographical error which had me scratching my head on the first read through for a while. There’s at least one more, but I’m not sure of the details.
Anyhow, a young grad student spotted both the typo and the more subtle bug and had the temerity to bring them Turing. He dumped them at his feet like a springer spaniel fetching a tennis ball from a stagnant pond.
Far from praising the grad student’s perspicacity, Turing bit his head off. He pointed out that of course there was a bug, but it was obviously fixable, and so didn’t affect the argument at the core of the paper. To Turing, it seems, the TM wasn’t all that important, it was just a bit of apparatus he’d cooked up to support the more interesting proof. Either that or he was sick of people finding that bloody silly typo and doing the spaniel routine.
The grad student went off and redid the UTM. He even optimized it, reducing the total number of states required and the amount of seeking back and forth along the tape (apparently Turing’s machine was forever returning to the beginning of the tape and then hunting forwards for the next interesting bit.) Whether optimizing a program for a theoretical machine was a useful use of a grad student’s time is left as an exercise for the interested reader, but you can find the redone UTM implementation (and the grad student’s recollections) in The Essential Turing.
Now, why did I tell that story? Ah, yes. Spj’s reaction to the bug in the presentation was lovely. First reaction: “Drat… well, let’s fix it.” Second reaction: “Ah… not quite as easy a fix as I thought.” Third reaction: “Thank you very much, sir, for suggesting that we all go and have tea.” And then, on returning from tea, he took a polite version of Turing’s response to the bug in his UTM by giving a quick verbal sketch of the fix and carrying on with the meat of the tutorial.
There are two kinds of people who try to learn Haskell: the people who give up because they can’t figure out monads, and the people who go on to write tutorials on how to understand monads.
I claim that the above is not a tutorial. Then again, I’m not entirely sure that I’ve even started with Haskell.
Karsten Wagner’s explanation is the one that worked for me. It’s not far off from what you’ve written here.