Monday, August 13, 2007

Learning Monads in 1996

Given the plethora of monad tutorials these days it's hard to imagine how anybody could have learned about this concept during the 90's. I learned most of what I know about monads in 1996, back in the days when even researchers had a hard time understanding the list monad. This post will not be another monad tutorial. I'm simply going to explain how I managed to become friendly with monads in a time where monad tutorials where very scarce. So, why did I start looking into monads in the first place? In 1995 I started my undergraduate studies at Chalmers and the first language we were taught was Gofer, a now extinct dialect of Haskell. When the time came for teaching us I/O they didn't show us the monadic way of doing things. Apparently our teacher (who by the way was not a functional programmer, a strange fact considering that Chalmers abound with functional programmers) thought that the concept of monads was too scary and complicated and taught us continuation I/O, something which I experienced as painfully horrible and utterly confusing. But some of us students had heard about monads and how they were supposed to be they way of the future when it came to I/O and other things. They sounded really cool, and hey, they couldn't possibly be worse than continuation I/O right? So I set my mind to learning monads. I tried to read everything that was available on the subject which wasn't much at the time. There were two papers which I spent a considerable time with: "The essence of functional programming" and "Monads for functional programming" by Phil Wadler. I implemented every single bit of code in those papers, tore the code to pieces and put it back again. I started implementing monadic parser libraries based on the paper "Monadic parser combinators" by Hutton and Meijer. Trying out different implementations and combinators I wrote variation after variation of these libraries. I don't know how many of parser libraries I implemented in the end. I've lost count. Slowly I was starting to grasp monads as I played around with them. After some time I was even able to digest and understand the paper "Monad Transformers and Modular Interpreters" but it certainly didn't happen the first time I read it. What finally pushed me over the edge was when a friend asked me how to combine different monads. I didn't know the answer and for some reason it kind of bugged me that I couldn't answer his question. But I had a vague recollection of ideas in the above paper. Determined to understand this, I sat down and started to hack on monad transformers and didn't finish until I finally had a rudimentary understanding of them, several hours later. Monadic I/O turned out to be a breeze to learn thanks to the nice "Monadic I/O in Haskell 1.3" by Kevin Hammond and Andrew Gordon. And there you have it. The way I learned about monads. No magic, just hard work. I'm a slow learner and you can probably get comfortable with monads much faster than I. But I don't think you'll find any method which is significantly different from mine. What makes me say that? Why are monads such a difficult concept to learn? The conclusion I've come to is that the difficulty lie in the fact that it's an abstraction. Abstract things are simply hard, especially for people who have little experience with abstractions before. As an example take an abstraction like the concept of a group. What is a group? It's a set, call it G, and a binary operator on G which is associative and has inverses and an identity element. For anyone used to abstractions this is a perfectly fine definition. But not so for your average man on the street, or even programmer. They will react something like this: "Ok, I understand the definition. But what *is* a group? I mean, in *reality*?" I remember having similar thoughts myself. The fact that a group is not a concrete thing is a great confusion. In my experience this only settles after the person has gained some experience with lots of examples of what a group is, and a few examples of things that fail to be a group. By then most people will have gotten pretty comfortable with the concept. It's the same thing with monads. They're an abstract concept which will take time to digest. And this digestion is best done by playing around with various examples of monads and occasionally meet examples of data types which are not monads and for what reason they fail. I don't think there are any shortcuts to learning abstract concepts. But I think that one can become better at it and it certainly helps to have a good tutorial when learning a subject, such as monads.


Marceau Huxley said...

On the other hand, mathematicians have understood monads for decades. The list monad is just a functor L from Sets to Sets (or Monoids if you prefer) such that there is a multiplication map (natural transformation) mu: L L X -> L X given by concatenation and an identity map nu: X -> L X taking an element x to a list with one element [x]. This forms a monoid in the category of endofunctors over Set and was called a triple for years before the word monad was invented.

Monads for programmers take a formally different, less familiar, but nevertheless equivalent form: the map nu is called return and a map called bind is used instead of mu, where bind f x can be defined as join ( fmap f x). (Join can be given by join x = bind id x.) This approach is more difficult to understand because it obscures the more familiar underlying structure of a monoid, of which we are intimately acquainted with: addition and multiplication of integers, rationals, reals; compositions of functions; etc. Even the bind approach is well understood mathematically as the Kleisli category of a monoid -- a way of factoring a monad into a pair of adjoint functors (of which there are in general many).

Monads are still taught the wrong way (nuclear waste containers!?) today by nearly everyone and as such have continued to be a barrier to understanding Haskell and functional programming. Monoids are much easier to understand (concatenation versus bind for instance) and the cost is only one more definition, that of bind in terms of join.

José Dinuncio said...

I followed your path plus tutorials. I have my "Ok, I understand the definition. But what *is* a monad?" moment too.

Mathematical definition is almost useless for a programmer, I still wanted to know when and where should I create my own monads. I can agree with Marceau that the best way for a programmer to understand monads is following the monoid/functor way.

Then I realized it... A monad is not something I "want" to create, it is something the program itself impose to me. I have my types a, b, c and a lot of functions over them. Then I need a type constructor D, and suddenly I have D a, D b, D c and all my old functions are useless on the new types. And is in this stage that super monad comes to rescue: I implement bind and return on D, and voila! I get my old functions working in my new types.

Shane said...

Great article. And I just wanted to say thanks to José for his comment too. I've worked with Haskell and am comfortable with functional programming, but I still had not grokked monads, and José's insight about not _wanting_ to create them really hit home for me. Thank you for that.

Anonymous said...

Hello I just entered before I have to leave to the airport, it's been very nice to meet you, if you want here is the site I told you about where I type some stuff and make good money (I work from home): here it is