The Monadic Way
From HaskellWiki
BrettGiles (Talk  contribs) (Links) 

(21 intermediate revisions by 3 users not shown) 
Latest revision as of 22:35, 24 July 2007
Note Since the size of the previous file was getting too big for a wiki, the tutorial has been divided into two parts: The Monadic Way Part I and The Monadic Way Part II. See below for some introductory remarks.
Contents
 Meet Bob The Monadic Lover
 A (supposedtobe) funny and short introduction to Monads, with code but without any reference to category theory: what monads look like and what they are useful for, from the perspective of a ... lover. It could be an introduction to "The Monadic Way" tutorial.
 The Monadic Way/Part I
 In the first part of the tutorial we will start from a very simple evaluator that will be transformed into a monadic evaluator with an increasing number of features: output, exceptions, and state: a very simple counter for tracking the number of recursions of the evaluation precess.
 The Monadic Way/Part II
 In the second part of the tutorial we will see how to take complexity out of our monadic evaluator with the use of monadic transformers, and specifically StateT. This part is just a skeleton, since, for the time being, it contains only the code.
Contents 
[edit] 1 Preliminary remarks
When I started writing this tutorial I though that the only way to explain monads to a newcomer was to show them from the inside, with the use of lambda abstraction. Not only because this is the way Philip Wedler's paper adopts, but also because I believed, and still believe, that the only way to understand what bind (>>=) does is to explain it as a function that takes a monad and an anonymous function.
I had this feeling because I am a newcomer, and this is the way I came to understand monads.
I did not received very much feedback for this tutorial, and I must admit that I would like to. But one person, on the haskellcafe mailing list, told me that:
imho your tutorial makes the error that is a very typical: when you write your tutorial you already know what are monads and what the program you will construct at the end. but your reader don't know all these! for such fresh reader this looks as you made some strange steps, write some ugly code and he doesn't have chances to understand that this ugly code is written just to show that this can be simplified by using monads.
I believe that Bulat is right. In this tutorial you go through some code that is really ugly and then, with some kind of magic, it turns out in the (redundant but) clean evaluator of the end of The Monadic Way/Part II.
I took that mail as a challenge and I responded by writing Meet Bob The Monadic Lover.
In "Meet Bob" the code is clean, variable names are very descriptive, and you see that I can create a monad without any use of lambda abstraction.
Bind (in "Meet Bob" is askLover) now takes a monad and a partial application, not an anonymous function.
Obviously you can see an anonymous function as a partial application.
The problem, I think, is that, in "Meet Bob", you cannot understand the strict relation between what I did before and what I do when I start using the "donotation". You see that the same functions are being used ("tellMyself" and "newLove"), but "andrea < tellMyself 1" is not explained. It's just magic.
The fact is that you cannot understand "andrea < tellMyself 1" without the use of lambda abstraction.
I should have written an intermediate step, something like this:
drunk = do newLove "Paula " >> (tellLover 1 10) >>= \paula > (tellMyself 3) >>= \lorena > tellMyself (paula + lorena)
With this approach I think you can understand why and how you come to write something like this:
drunk = do newLove "Paula " paula < (tellLover 1 10) lorena < tellMyself 3 tellMyself (paula + lorena)
That is to say, in this way you can see a do block as a series of nested anonymous functions whose arguments are bound to some value by the application of >>=. Anonymous functions that bind to some value the variables appearing after the ">" ("paula" and "lorena").
To summarize, I think that even if you can start using monads without understanding that what happens inside a "do" block is strictly related with lambda calculus, I don't think you can claim you understand monads just because you are using them.
And I'm quite sure that if a problem arises somewhere you can have a very difficult time in trying to find out what the problem is. This is even more true when you start doing monadic transformations.
[edit] 2 How to explain monads to newcomers?
Monads are not an impossibletounderstandunlessyouhaveaphd topic. I don't know if I can claim I'm a living proof of this assumption, since I have a PhD. But please take into account that I have a PhD in Comparative Private Law! Nothing related to computer science. And I claim I understand monads.
Moreover, since I have come to understand them, I think I can try to explain them to newcomers like me. This is why I started writing this tutorial.
Still, in order to understand them I studied, and I studied hard. I wanted to understand, it was difficult, and I kept studying. Going back to the foundation when needed.
So, I cannot explain monads to you unless you are willing to study. I can show you the way, but you must take your time and follow that way.
[edit] 3 What do I need to know to understand monads?
[edit] 3.1 Functional programming
First you need at least a basic understanding of functional programming.
This is going to be the easiest step, because there is an invaluable resource available on line for free.
This is what I did: I spent 20 hours of my life watching the Video Lectures by Hal Abelson and Gerald Jay Sussman on Structure and Interpretation of Computer Programs.
This course, and the annexed text book (I did not read it entirely), are an amazing introduction to computer science: you start by learning some basic Scheme and then Abelson and Sussman will bring you, step by step, to understand evaluation, interpretation and compilation of Lisp (Scheme) code.
The course is clear, interesting, funny and will provide you with a basic, but strong, understanding of functional programming.
Believe me: if you like programming but don't have a computer science curriculum, you'll find out that spending 20 hours of your life to watch that course has been the most productive investment of your learning life.
[edit] 3.2 My problem with Haskell
I find Haskell an amazingly expressive programming language. It makes it incredibly easy to perform very difficult tasks, just like monads, for instance.
The problem is that, in doing so, it makes it difficult to understand Haskell to newcomers.
I must confess that tutorials and other learning material are quite dissatisfying on this regards too.
Since Haskell seems to make easy what is not easy, these tutorial take the "it's easy" approach.
I will give you an example. I think that the "Yet Another Haskell Tutorial" is a really good attempt to explain Haskell, and if you want to understand this tutorial you need to read it at least for getting a good understanding of the Haskell type system.
The tutorial explains monads and explains the "do notation" in terms of lambda abstraction (par. 9.1, p. 120). Still, to the lambda operator ("\") the tutorial dedicates only 17 lines in par. 4.4.1. Moreover "\" is explained just as another way of creating functions.
This probably makes sense for a functional programmer who is studying Haskell for the first time. But, on the other side it will make the newcomer, who's not a functional programmer, believe that explaining monads in terms of "\" is just ugly, and definitely not Haskell.
This is my problem with Haskell: it hides complexity with constructions like "let...in", "where", "do".
Still I believe that if you want to use those constructions you must know what they do. And they do ugly stuff like the one you'll be looking at in this tutorial.
I am not saying that this is the way to learn Haskell. I'm just saying that this is the way I'm learning Haskell. And this is the way this tutorial has been written.
[edit] 3.3 Starting from the inside or the outside?
In This tutorial I show monads from their inside. In "Meet Bob" I do the opposite. As I said I think (and I did it on purpose) that after reading "Meet Bob" you can have a general idea of what a monad is, but you need to go inside a monad to see how it works.
As a suggestion, I'd invite you to start with "Meet Bob", and then procede with the tutorial.
I hope the these two approaches will give you an overall image of a monad.
[edit] 3.4 Prerequisites
As I said, in order to understand this tutorial you need:
 a basic understanding of functional programming (this is required to understand Haskell after all)
 a basic understanding of the type system:
 how to create new types (with "data" and "newtype")
 how to use type constructors to construct and to match types and their internal components
 how to use a label field to retrieve a type internal component
 a basic understanding of lambda abstraction
I hope I'll be able to write a short introductory summary to these topics (I will put it below this introductory remarks).
Have fun with Haskell!