Personal tools

The Monadic Way

From HaskellWiki

(Difference between revisions)
Jump to: navigation, search
(added exception handling, an ascii art chart flow of what >>= does, and some minor corrections)
(Links)
 
(17 intermediate revisions by 2 users not shown)
Line 1: Line 1:
==An evaluation of Philip Wadler's "Monads for functional programming"==
+
'''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.
   
This tutorial is a "translation" of Philip Wedler's "Monads for
+
'''Contents'''
functional programming".
 
(avail. from [http://homepages.inf.ed.ac.uk/wadler/topics/monads.html here])
 
   
I'm a Haskell newbie trying to grasp such a difficult concept as the
+
;[[Meet Bob The Monadic Lover]]
ones of Monad and monadic computation.
+
:A (supposed-to-be) 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.
While [http://www.cs.utah.edu/~hal/htut/ "Yet Another Haskell Tutorial"]
 
gave me a good understanding of the type system when it
 
comes to monads I find it almost unreadable.
 
   
But I had also Wedler's paper, and started reading it. Well, just
+
;[[The Monadic Way/Part I]]
wonderful! It explains how to ''create'' a monad!
+
: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.
   
So I decided to "translate it", in order to clarify to myself the
+
;[[The Monadic Way/Part II]]
topic. And I'm now sharing this traslation (not completed yet) with
+
: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.
the hope it will be useful to someone else.
 
   
Moreover, that's a wiki, so please improve it. And, specifically,
 
correct my poor English. I'm Italian, after all.
 
   
'''Note: The source of this page can be used as a Literate Haskel
+
==Preliminary remarks==
file nad can be run with ghci or hugs: so cut paste change'n run (in
 
emacs for instance) while reading it...'''
 
   
==A Simple Evaluator==
+
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
  +
[http://homepages.inf.ed.ac.uk/wadler/papers/marktoberdorf/baastad.pdf 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.
   
Let's start with something simple: suppose we want to implement a new
+
I had this feeling because I am a newcomer, and this is the way I came to understand monads.
programming language. We just finished with
 
[http://swiss.csail.mit.edu/classes/6.001/abelson-sussman-lectures/ Abelson and Sussman's Structure and Interpretation of ComputerPrograms]
 
and we want to test what we have learned.
 
 
Our programming language will be very simple: it will just compute the
 
sum operation.
 
 
So we have just one primitive operation (Add) that takes two constants
 
and calculates their sum
 
 
For instance, something like:
 
 
(Add (Con 5) (Con 6))
 
 
should yeld:
 
 
11
 
 
We will implement our language with the help of a data type
 
constructor such as:
 
 
<haskell>
 
 
> module MyMonads where
 
> data Term = Con Int
 
> | Add Term Term
 
> deriving (Show)
 
 
</haskell>
 
 
After that we build our interpreter:
 
 
<haskell>
 
 
> eval :: Term -> Int
 
> eval (Con a) = a
 
> eval (Add a b) = eval a + eval b
 
 
</haskell>
 
 
That's it. Just an example:
 
 
*MyMonads> eval (Add (Con 5) (Con 6))
 
11
 
*MyMonads>
 
 
Very very simple. The evaluator checks if its argument is a Con: if
 
it is it just returns it.
 
 
If it's not a Cons, but it is a Term, it evaluates the right one and
 
sums the result with the result of the evaluation of the second term.
 
 
== Some Output, Please!==
 
 
Now, that's fine, but we'd like to add some features, like providing
 
some output, to show how the computation was carried out.
 
Well, but Haskell is a pure functional language, with no side effects,
 
we were told.
 
 
Now we seem to be wanting to create a side effect of the computation,
 
its output, and be able to stare at it...
 
If we had some global variable to store the out that would be
 
simple...
 
 
But we can create the output and carry it along the computation,
 
concatenating it with the old one, and present it at the end of the
 
evaluation together with the evaluation of the expression!
 
 
Simple and neat!
 
 
<haskell>
 
 
> type MOut a = (a, Output)
 
> type Output = String
 
>
 
> formatLine :: Term -> Int -> Output
 
> formatLine t a = "eval (" ++ show t ++ ") <= " ++ show a ++ " - "
 
>
 
> evalO :: Term -> MOut Int
 
> evalO (Con a) = (a, formatLine (Con a) a)
 
> evalO (Add t u) = ((a + b),(x ++ y ++ formatLine (Add t u) (a + b)))
 
> where (a, x) = evalO t
 
> (b, y) = evalO u
 
 
</haskell>
 
 
Now we have what we want. But we had to change our evaluator quite a
 
bit. First we added a function, that takes a Term (of the expression
 
to be evaluated), an Int (the result of the evaluation) and gives back
 
an output of type Output (that is a synonymous of String).
 
 
The evaluator changed quite a lot! Now it has a different type: it
 
takes a Term data type and produces a new type, we called MOut, that
 
is actually a pair of a variable type a (an Int in our evaluator) and
 
a type Output, a string.
 
 
So our evaluator, now, will take a Term (the type of the expressions
 
in our new programming language) and will produce a pair, composed of
 
the result of the evaluation (an Int) and the Output, a string.
 
 
So far so good. But what's happening inside the evaluator?
 
 
The first part will just return a pair with the number evaluated and
 
the output formatted by formatLine.
 
 
The second part does something more complicated: it returns a pair
 
composed by
 
1. the result of the evaluation of the right Term summed to the result
 
of the evaluation of the second Term
 
2. the output: the concatenation of the output produced by the
 
evaluation of the right Term, the output produced by the evaluation of
 
the left Term (each this evaluation returns a pair with the number and
 
the output), and the formatted output of the evaluation.
 
 
Let's try it:
 
*MyMonads> evalO (Add (Con 5) (Con 6))
 
(11,"eval (Con 5) <= 5 - eval (Con 6) <= 6 - eval (Add (Con 5) (Con 6)) <= 11 - ")
 
*MyMonads>
 
 
It works! Let's put the output this way:
 
eval (Con 5) <= 5 -
 
eval (Con 6) <= 6 -
 
eval (Add (Con 5) (Con 6)) <= 11 -
 
 
Great! We are able to produce a side effect of our evaluation and
 
present it at the end of the computation, after all.
 
 
Let's have a closer look at this expression:
 
<haskell>
 
 
evalO (Add t u) = ((a + b),(x ++ y ++ formatLine (Add t u) (a + b)))
 
where (a, x) = evalO t
 
(b, y) = evalO u
 
 
</haskell>
 
 
Why all that? The problem is that we need "a" and "b" to calculate their
 
sum, together with the output coming from their calculation (to be
 
concatenated by the expression x ++ y ++ formatLine ...).
 
 
So we need to separate the pairs produced by "evalO t" and "eval u"
 
(remember: eval now produces a value of type M Int, i.e. a pair of an
 
Int and a String!).
 
 
== Let's Go Monadic==
 
 
Is there a more general way of doing so?
 
 
Let's analyze the evaluator from another perspective. From the type
 
perspective.
 
 
We solved our problem by creating a new type, a pair of an Int (the
 
result of the evaluation) and a String (the output of the process of
 
evaluation).
 
 
The first part of the evaluator does nothing else but creating, from
 
a value of type Int, an object of type M Int (Int,Output). It does so
 
by creating a pair with that Int and some text.
 
 
The second part evaluates the two Term(s) and "stores" the values thus
 
produced in some variables to be use later to compute the output.
 
 
Let's focus on the "stores" action. The correct term should be
 
"binds".
 
 
Take a function:
 
<haskell>
 
f x = x + x
 
</haskell>
 
"x" appears on both sides of the expression. We say that on the right
 
side "x" is bound to the value of x given on the left side.
 
 
So
 
<haskell>
 
f 3
 
</haskell>
 
binds x to 3 for the evaluation of the expression "x + x".
 
 
Our evaluator binds "a" and "x" / "b" and "y" with the evaluation of
 
"eval t" and "eval u" respectively. "a","b","x" and "y" will be then
 
used in the evaluation of ((a+)(x ++ ...).
 
 
We know that there is an ad hoc operator for binding variables to a
 
value: lambda, or \.
 
 
Indeed f x = x + x is syntactic sugar for:
 
<haskell>
 
f = \x -> x + x
 
</haskell>
 
When we write f 3 we are actually binding "x" to 3 within what's next
 
"->", that will be used (substituted) for evaluating f 3.
 
 
So we can try to abstract this phenomenon.
 
 
What we need is a function that takes our composed type MOut Int and a
 
function in order to produce a new MOut Int, concatenating the
 
output of the computation of the first with the output of the
 
computation of the second.
 
 
This is what bindM does:
 
 
<haskell>
 
 
> bindM :: MOut a -> (a -> MOut b) -> MOut b
 
> bindM m f = (b, x ++ y)
 
> where (a, x) = m
 
> (b, y) = f a
 
 
</haskell>
 
 
It takes:
 
* "m": the compound type MOut Int carrying the result of an "eval Term",
 
* a function "f". This function will take the Int ("a") extracted by the evaluation of "m" ((a,x)=m). This function will produce anew pair: a new Int produced by a new evaluation; some new output.
 
 
bindM will return the new Int in pair with the concatenated outputs
 
resulting from the evaluation of "m" and "f a".
 
 
So let's write the new version of the evaluator:
 
 
<haskell>
 
 
> evalM_1 :: Term -> MOut Int
 
> evalM_1 (Con a) = (a, formatLine (Con a) a)
 
> evalM_1 (Add t u) = bindM (evalM_1 t) (\a ->
 
> bindM (evalM_1 u) (\b ->
 
> ((a + b), formatLine (Add t u) (a + b))
 
> )
 
> )
 
 
</haskell>
 
 
Ugly, isn't it?
 
 
Let's start from the outside:
 
 
<haskell>
 
bindM (evalM_1 u) (\b -> ((a + b), formatLine (Add t u) (a + b)))
 
</haskell>
 
 
bindM takes the result of the evaluation "evalM_1 u", a type Mout Int,
 
and a function. It will extract the Int from that type and use it to
 
bind "b".
 
 
So in bindM (evalM_1 u)... "b" will be bound to a value.
 
 
Then the outer part (bindM (evalM_1 t) (\a...) will bind "a" to the
 
value needed to evaluate "((a+b), formatLine...) and produce our final
 
MOut Int.
 
 
We can write the evaluator in a more convinient way, now that we know
 
what it does:
 
 
<haskell>
 
 
> evalM_2 :: Term -> MOut Int
 
> evalM_2 (Con a) = (a, formatLine (Con a) a)
 
> evalM_2 (Add t u) = evalM_2 t `bindM` \a ->
 
> evalM_2 u `bindM` \b ->
 
> ((a + b), (formatLine (Add t u) (a + b)))
 
 
</haskell>
 
 
Now, look at the first part:
 
 
<haskell>
 
evalM_2 (Con a) = (a, formatLine (Con a) a)
 
</haskell>
 
 
We could use a more general way of creating some output.
 
 
First we need a method for creating someting of type M a, starting from
 
something of type a. This is what <hask>evalM_2 (Con a)</hask> is doing, after all.
 
Very simply:
 
 
<haskell>
 
 
> mkM :: a -> MOut a
 
> mkM a = (a, "")
 
 
</haskell>
 
 
We then need to "insert" some text (Output) in our type M:
 
 
<haskell>
 
 
> outPut :: Output -> MOut ()
 
> outPut x = ((), x)
 
 
</haskell>
 
 
Very simple: we have a string "x" (Output) and create a pair with a ()
 
instead of an Int, and the output.
 
 
This way we will be able to define also this firts part in terms of
 
bindM, that will take care of concatenating outputs.
 
 
So we have now a new evaluator:
 
 
<haskell>
 
 
> evalM_3 :: Term -> MOut Int
 
> evalM_3 (Con a) = outPut (formatLine (Con a) a) `bindM` \_ -> mkM a
 
> evalM_3 (Add t u) = evalM_3 t `bindM` \a ->
 
> evalM_3 u `bindM` \b ->
 
> outPut (formatLine (Add t u) (a + b)) `bindM` \_ -> mkM (a + b)
 
 
</haskell>
 
 
Well, this is fine, definetly better then before, anyway.
 
 
Still we use `bindM` \_ -> that binds something we do not use (_). We
 
could write something for this case, when we concatenate computations
 
without the need of binding variables. Let's call it `combineM`:
 
 
<haskell>
 
 
> combineM :: MOut a -> MOut b -> MOut b
 
> combineM m f = m `bindM` \_ -> f
 
 
</haskell>
 
 
So the new evaluator:
 
 
<haskell>
 
 
> evalM :: Term -> MOut Int
 
> evalM (Con a) = outPut (formatLine (Con a) a) `combineM`
 
> mkM a
 
> evalM (Add t u) = evalM t `bindM` \a ->
 
> evalM u `bindM` \b ->
 
> outPut (formatLine (Add t u) (a + b)) `combineM`
 
> mkM (a + b)
 
 
</haskell>
 
 
Let's put everything together (and change some names):
 
 
<haskell>
 
 
> type MO a = (a, Out)
 
> type Out = String
 
 
> mkMO :: a -> MO a
 
> mkMO a = (a, "")
 
 
> bindMO :: MO a -> (a -> MO b) -> MO b
 
> bindMO m f = (b, x ++ y)
 
> where (a, x) = m
 
> (b, y) = f a
 
 
> combineMO :: MO a -> MO b -> MO b
 
> combineMO m f = m `bindM` \_ -> f
 
 
> outMO :: Out -> MO ()
 
> outMO x = ((), x)
 
 
> evalMO :: Term -> MO Int
 
> evalMO (Con a) = outMO (formatLine (Con a) a) `combineMO`
 
> mkMO a
 
> evalMO (Add t u) = evalMO t `bindMO` \a ->
 
> evalMO u `bindMO` \b ->
 
> outMO (formatLine (Add t u) (a + b)) `combineMO`
 
> mkMO (a + b)
 
 
</haskell>
 
 
==What Does Bind Bind?==
 
 
The evaluator looks like:
 
<haskell>
 
evalM t >>= \a -> evalM u >>= \b -> outPut "something" >>= \_ -> mkM (a +b)
 
</haskell>
 
where >>= is bindM, obviously.
 
 
Let's do some substitution where
 
* evalM t = (a,Out)
 
* evalM u = (b,Out)
 
* outMO "string" = ((),Out)
 
* mkMO (a+b) = ((a+b),Out)
 
   
  +
I did not received very much feedback for this tutorial, and I must
  +
admit that I would like to. But one person, on the haskell-cafe
  +
mailing list, [http://www.haskell.org/pipermail/haskell-cafe/2006-September/017740.html told me]
  +
that:
 
<pre>
 
<pre>
| (a,Out) >>= \a -> (b,Out) >>= \b -> ((),Out) >>= \_ >>= ((a + b), Out)
+
imho your tutorial makes the error that is a very typical: when you
d | V V V V V V V V ^ ^ ^ ^
+
write your tutorial you already know what are monads and what the
o | |__|________^ | | ^ | | | | | |
+
program you will construct at the end. but your reader don't know all these!
B | |__(++)__|_Out_|__|__(++)__V_____|___|__Out___|_(++)__|___|____|
+
for such fresh reader this looks as you made some strange steps, write
i | | |______(b)__|_____|_____(b)____|__(b)__|___|
+
some ugly code and he doesn't have chances to understand that this ugly
n | |_________(a)___________|____________|__(a)__|
+
code is written just to show that this can be simplified by using monads.
d | |_____()_____|
 
 
 
</pre>
 
</pre>
   
Clear, isn't it?
+
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]].
   
"bindM" is just a function that takes care of gluing together, inside
+
I took that mail as a challenge and
a data type, a sequence of computations!
+
[http://www.haskell.org/pipermail/haskell-cafe/2006-September/017778.html I responded]
  +
by writing [[Meet Bob The Monadic Lover]].
   
== Some Sugar, Please!==
+
In "Meet Bob" the code is clean, variable names are very descriptive,
Now our evaluator has been completely transformed into a monadic
+
and you see that I can create a monad without any use of lambda
evaluator. That's what it is: a monad.
+
abstraction.
   
We have a function that constructs an object of type MO Int, formed by
+
Bind (in "Meet Bob" is askLover) now takes a monad and a partial
a pair: the result of the evaluation and the accumulated
+
application, not an anonymous function.
(concatenated) output.
 
   
The process of accumulation and the act of parting the MO Int into its
+
Obviously you can see an anonymous function as a partial application.
component is buried into bindM, that can also preserve some value for
 
later uses.
 
   
So we have:
+
The problem, I think, is that, in "Meet Bob", you cannot understand
* MO a type constructor for a type carrying a pair composed by an Int and a String;
+
the strict relation between what I did before and what I do when I
* bindMO, that gives a direction to the process of evaluation: it concatenates computations and captures some side effects we created.
+
start using the "do-notation". You see that the same functions are
* mkOM lets us create an object of type MO Int starting from an Int.
+
being used ("tellMyself" and "newLove"), but "andrea <- tellMyself 1"
  +
is not explained. It's just magic.
   
As you see this is all we need to create a monad. In other words
+
The fact is that you cannot understand "andrea <- tellMyself 1"
monads arise from the type system. Everything else is just syntactic
+
without the use of lambda abstraction.
sugar.
 
 
So, let's have a look to that sugar: the famous do-notation!
 
 
We will now rewrite our basic evaluator to use it with the
 
do-notation.
 
 
Now we have to crate a new type: this is necessary in order to use
 
specific monadic notation and have at our disposal the more practical
 
do-notation.
 
   
  +
I should have written an intermediate step, something like this:
 
<haskell>
 
<haskell>
+
drunk = do newLove "Paula " >>
> newtype Eval a = Eval a
+
(tellLover 1 10) >>= \paula ->
> deriving (Show)
+
(tellMyself 3) >>= \lorena -> tellMyself (paula + lorena)
   
 
</haskell>
 
</haskell>
   
So, our type will be an instance of the monad class. We will have to
+
With this approach I think you can understand '''why and how''' you
define the methods of this class (>>= and return), but that will be
+
come to write something like this:
easy since we already done that while defining bindMO and mkMO.
 
 
 
<haskell>
 
<haskell>
+
drunk = do newLove "Paula "
> instance Monad Eval where
+
paula <- (tellLover 1 10)
> return a = Eval a
+
lorena <- tellMyself 3
> Eval m >>= f = f m
+
tellMyself (paula + lorena)
 
 
</haskell>
 
</haskell>
   
And then we will take the old version of our evaluator and substitute
+
That is to say, in this way you can see a do block as a series of
`bindMO` with >>= and `mkMO` with return:
+
nested anonymous functions whose arguments are bound to some value by
+
the application of >>=. Anonymous functions that bind to some value
<haskell>
+
the variables appearing after the "->" ("paula" and "lorena").
   
> evalM_4 :: Term -> Eval Int
+
To summarize, I think that even if you can start using monads without
> evalM_4 (Con a) = return a
+
understanding that what happens inside a "do" block is strictly
> evalM_4 (Add t u) = evalM_4 t >>= \a ->
+
related with lambda calculus, I don't think you can claim you
> evalM_4 u >>= \b ->
+
understand monads just because you are using them.
> return (a + b)
 
   
</haskell>
+
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.
   
which is, in the do-notation:
+
==How to explain monads to newcomers?==
   
<haskell>
+
Monads are not an impossible-to-understand-unless-you-have-a-phd
  +
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.
   
> evalM_5 :: Term -> Eval Int
+
Moreover, since I have come to understand them, I think I can try to
> evalM_5 (Con a) = return a
+
explain them to newcomers like me. This is why I started writing this
> evalM_5 (Add t u) = do a <- evalM_5 t
+
tutorial.
> b <- evalM_5 u
 
> return (a + b)
 
   
</haskell>
+
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.
   
Simple: do binds the result of "eval_M5 t" to a, binds the result of
+
So, I cannot explain monads to you unless you are willing to study. I can
"eval_M5 u" to b and then returns the sum. In a very imperative style.
+
show you the way, but you must take your time and follow that way.
   
We can now have an image of our monad: it is out type (Eval) that is
+
==What do I need to know to understand monads?==
made up of a pair: during evaluation the first member of the pair (the
 
Int) will get the results of our computation (i.e.: the procedures to
 
calculate the final result). The second part, the String called
 
Output, will get filled up with the concatenated output of the
 
computation.
 
   
The sequencing done by bindMO (now >>=) will take care of passing to
+
===Functional programming===
the next evaluation the needed Int and will do some more side
 
calculation to produce the output (concatenating outputs resulting
 
from computation of the new Int, for instance).
 
   
So we can grasp the basic concept of a monad: it is like a label which
+
First you need at least a basic understanding of functional
we attach to each step of the evaluation (the String attached to the
+
programming.
Int).
 
This label is persistent within the process of computation and at each
 
step bindMO can do some manipulation of it.
 
We are creating side-effects and propagating them within our monads.
 
   
Ok. Let's translate our output-producing evaluator in monadic
+
This is going to be the easiest step, because there is an invaluable
notation:
+
resource available on line for free.
   
<haskell>
+
This is what I did: I spent 20 hours of my life watching the Video
  +
Lectures by Hal Abelson and Gerald Jay Sussman on
  +
[http://swiss.csail.mit.edu/classes/6.001/abelson-sussman-lectures/ Structure and Interpretation of Computer Programs].
   
> newtype Eval_IO a = Eval_IO (a, O)
+
This course, and the annexed text book (I did not read it entirely),
> deriving (Show)
+
are an amazing introduction to computer science: you start by learning
> type O = String
+
some basic Scheme and then Abelson and Sussman will bring you, step by
  +
step, to understand evaluation, interpretation and compilation of Lisp
  +
(Scheme) code.
   
> instance Monad Eval_IO where
+
The course is clear, interesting, funny and will provide you with a
> return a = Eval_IO (a, "")
+
basic, but strong, understanding of functional programming.
> (>>=) m f = Eval_IO (b, x ++ y)
 
> where Eval_IO (a, x) = m
 
> Eval_IO (b, y) = f a
 
> print_IO :: O -> Eval_IO ()
 
> print_IO x = Eval_IO ((), x)
 
 
> eval_IO :: Term -> Eval_IO Int
 
> eval_IO (Con a) = do print_IO (formatLine (Con a) a)
 
> return a
 
> eval_IO (Add t u) = do a <- eval_IO t
 
> b <- eval_IO u
 
> print_IO (formatLine (Add t u) (a + b))
 
> return (a + b)
 
   
</haskell>
+
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
Let's see the evaluator with output in action:
+
watch that course has been the most productive investment of your
*MyMonads> eval_IO (Add (Con 6) (Add (Con 16) (Add (Con 20) (Con 12))))
+
learning life.
Eval_IO (54,"eval (Con 6) <= 6 - eval (Con 16) <= 16 - eval (Con 20) <= 20 - eval (Con 12) <= 12 - \
 
eval (Add (Con 20) (Con 12)) <= 32 - eval (Add (Con 16) (Add (Con 20) (Con 12))) <= 48 - \
 
eval (Add (Con 6) (Add (Con 16) (Add (Con 20) (Con 12)))) <= 54 - ")
 
*MyMonads>
 
   
Let's format the output part:
+
===My problem with Haskell===
eval (Con 6) <= 6
 
eval (Con 16) <= 16
 
eval (Con 20) <= 20
 
eval (Con 12) <= 12
 
eval (Add (Con 20) (Con 12)) <= 32
 
eval (Add (Con 16) (Add (Con 20) (Con 12))) <= 48
 
eval (Add (Con 6) (Add (Con 16) (Add (Con 20) (Con 12)))) <= 54
 
   
==What Happened to Our Output??==
+
I find Haskell an amazingly expressive programming language. It makes
  +
it incredibly easy to perform very difficult tasks, just like monads,
  +
for instance.
   
Well, actually something happened to the output. Let's compare the
+
The problem is that, in doing so, it makes it difficult to understand
output of evalMO (the monadic evaluator written without the
+
Haskell to newcomers.
do-notation) and eval_IO:
 
   
*MyMonads> evalMO (Con 6)
+
I must confess that tutorials and other learning material are quite
(6,"eval (Con 6) <= 6 - ")
+
dissatisfying on this regards too.
*MyMonads> eval_IO (Con 6)
 
Eval_IO (6,"eval (Con 6) <= 6 - ")
 
*MyMonads>
 
   
They look almost the same, but they are not the same: the output of
+
Since Haskell seems to make easy what is not easy, these tutorial take
eval_IO has the Eval_IO stuff. It must be related to the changes we
+
the "it's easy" approach.
had to do to our evaluator in order to use the do-conation, obviously.
 
 
What's changed?
 
 
First the type definition. We have now:
 
 
<haskell>
 
newtype Eval_IO a = Eval_IO (a, O)
 
deriving (Show)
 
</haskell>
 
 
instead of
 
 
<haskell>
 
type MO a = (a, Out)
 
</haskell>
 
 
Moreover our bindMO and mkMO functions changed too, to reflect the
 
change of the type definition:
 
 
<haskell>
 
instance Monad Eval_IO where
 
return a = Eval_IO (a, "")
 
(>>=) m f = Eval_IO (b, x ++ y)
 
where Eval_IO (a, x) = m
 
Eval_IO (b, y) = f a
 
</haskell>
 
 
Now <hask>return a</hask> is the product of the application of the
 
type constructor Eval_IO to the pair that are going to form our monad.
 
 
"return" takes an Int and insert it into our monad. It will also insert
 
a void String "" that (>>=) or (>>) will then concatenate in a
 
sequence of computations they glue together.
 
 
The same for (>>=): it will now return something constructed by
 
Eval_IO: "b", the result of the application of "f" to "a" (better, the
 
binding of "a" in "f") and "x" (matched by <hask>Eval_IO (a, x)</hask> with
 
the evaluation of "m") and "y", (matched by "Eval_IO(b,y)" with the
 
evaluation of "f a".
 
 
That is to say: in the "where" clause, we are matching for the
 
elements paired in a type Eval_IO: this is indeed the type of "m"
 
(corresponding to "eval_IO t" in the body of the evaluator) and "f a"
 
(where "f" correspond to another application of "eval_IO" to the
 
result of the previous application of "m").
 
 
And so, "Eval_IO (a,x) = m" means: match "a" and "x", paired in a type
 
Eval_IO, and that are produced by the evaluation of "m" (that is to
 
say: "eval_IO t"). The same for Eval_IO (b,y): match "b" and "y"
 
produced by the evaluation of "f a".
 
 
So the output of the evaluator is now not simply a pair made of and
 
Int and a String. It is a specific type (Eval_IO) that happens to
 
carry a pair of an Int and a String. But, if we want the Int and the
 
string, we have to extract them from the Eval_IO type, as we do in the
 
"where" clause: we ''unpack'' our type object (let's call it with its
 
name: our monad!) and take out the Int and the String to feed the next
 
function application and the output generation.
 
 
The same to insert something in our monad: if we want to create a pair
 
of an Int and a String, pair of type Eval_IO, we now have to ''pack''
 
the together by using our type constructor, feeding it with pair
 
composed by and Int and a String. This is what we do with the "return"
 
method of out monad and with "print_IO" function, where:
 
* return insert into the monad an Int;
 
* print_IO insert into the monad a String.
 
 
Notice that "combineM" disappeared. This is because it comes for free
 
by just defining our type Eval_IO as an instance of the Monad class.
 
 
Indeed, if we look at the definition of the Monad class in the Prelude we read:
 
<haskell>
 
class Monad m where
 
return :: a -> m a
 
(>>=) :: m a -> (a -> m b) -> m b
 
(>>) :: m a -> m b -> m b
 
fail :: String -> m a
 
 
-- Minimal complete definition: (>>=), return
 
p >> q = p >>= \ _ -> q
 
fail s = error s
 
</haskell>
 
 
You can see that the "combineM"" method (or (>>)) is automatically derived by
 
the "bindMO" (or >>=) method:
 
 
<haskell>
 
p >> q = p >>= \ _ -> q
 
</haskell>
 
 
So, what the hell is the old <hask>type MO a = (a, Out)</hask> that
 
did not required all this additional work (apart the need to
 
specifically define (>>)?
 
 
Thanks the help of some nice guy of the
 
[http://www.haskell.org/mailman/listinfo/haskell-cafe haskell-cafe mailing list]
 
(look at the thread started by
 
[http://www.haskell.org/pipermail/haskell-cafe/2006-August/017634.html this silly question of mine])
 
we can answer.
 
 
Type MO is just a synonymous for (a,Out): the two can be substituted
 
one for the other. That's it.
 
 
We did not have to pack "a" and "Out" together with a type constructor
 
to have a new type MO.
 
 
As a consequence, we cannot use MO as an instance of Monad, and so, we
 
cannot use with it the syntactic sugar we needed: the do-notation.
 
 
That is to say: a type created with the "type" keyword cannot be an
 
instance of a class, and cannot inherits its methods (in our case
 
(>>=, >> and return). And without those methods the do-notation is not
 
usable.
 
 
Anyway we will better understand all the far reaching consequences of
 
this new approach later on.
 
 
==Errare Monadicum Est==
 
 
That's it. For today...
 
 
This is the code for the next part, to be analyzed in the next sections.
 
 
A non monadic version.
 
 
<haskell>
 
 
> data M a = Raise Exception
 
> | Return a
 
> deriving (Show)
 
> type Exception = String
 
 
> evalE :: Term -> M Int
 
> evalE (Con a) = Return a
 
> evalE (Add a b) =
 
> case evalE a of
 
> Raise e -> Raise e
 
> Return a ->
 
> case evalE b of
 
> Raise e -> Raise e
 
> Return b ->
 
> if (a+b) == 42
 
> then Raise "The Ultimate Answer Has Been Computed!! Now I'm tired!"
 
> else Return (a+b)
 
 
</haskell>
 
 
Run with:
 
 
evalE (Add (Con 10) (Add (Add (Con 20) (Con 10)) (Con 2)))
 
 
A monadic version.
 
 
<haskell>
 
 
> data M1 a = Except Exception
 
> | Ok {showM :: a }
 
> deriving (Show)
 
 
> instance Monad M1 where
 
> return a = Ok a
 
> m >>= f = case m of
 
> Except e -> Except e
 
> Ok a -> f a
 
 
> raise :: Exception -> M1 a
 
> raise e = Except e
 
 
> eval_ME :: Term -> M1 Int
 
> eval_ME (Con a) = do return a
 
> eval_ME (Add t u) = do a <- eval_ME t
 
> b <- eval_ME u
 
> if (a+b) == 42
 
> then raise "The Ultimate Answer Has Been Computed!! Now I'm tired!"
 
> else return (a + b)
 
 
</haskell>
 
 
Run with:
 
 
eval_ME (Add (Con 10) (Add (Add (Con 20) (Con 10)) (Con 2)))
 
 
It is noteworthy the fact that in our datatype definition we used a
 
label fields with a label selector (we called it showM).
 
 
Just to refresh your memory:
 
 
<haskell>
 
 
> data Person = Person {name :: String,
 
> age :: Int,
 
> hobby :: String
 
> } deriving (Show)
 
 
> andreaRossato = Person "Andrea" 37 "Haskell The Monadic Way"
 
> personName (Person a b c) = a
 
 
</haskell>
 
 
will produce:
 
*MyMonads> andreaRossato
 
Person {name = "Andrea", age = 37, hobby = "Haskell The Monadic Way"}
 
*MyMonads> personName andreaRossato
 
"Andrea"
 
*MyMonads> name andreaRossato
 
"Andrea"
 
*MyMonads> age andreaRossato
 
37
 
*MyMonads> hobby andreaRossato
 
"Haskell The Monadic Way"
 
*MyMonads>
 
 
 
Combining output and exceptions.
 
 
<haskell>
 
 
> data M2 a = Ex Exception
 
> | Done {unpack :: (a,O) }
 
> deriving (Show)
 
 
> instance Monad M2 where
 
> return a = Done (a, "")
 
> m >>= f = case m of
 
> Ex e -> Ex e
 
> Done (a, x) -> case (f a) of
 
> Ex e1 -> Ex e1
 
> Done (b, y) -> Done (b, x ++ y)
 
 
 
> raise_IOE :: Exception -> M2 a
 
> raise_IOE e = Ex e
 
 
> print_IOE :: O -> M2 ()
 
> print_IOE x = Done ((), x)
 
 
> eval_IOE :: Term -> M2 Int
 
> eval_IOE (Con a) = do print_IOE (formatLine (Con a) a)
 
> return a
 
> eval_IOE (Add t u) = do a <- eval_IOE t
 
> b <- eval_IOE u
 
> print_IOE (formatLine (Add t u) (a + b))
 
> if (a+b) == 42
 
> then raise_IOE "The Ultimate Answer Has Been Computed!! Now I'm tired!"
 
> else return (a + b)
 
 
</haskell>
 
 
Run with
 
 
eval_IOE (Add (Con 10) (Add (Add (Con 20) (Con 10)) (Con 2)))
 
 
 
==We Need A State==
 
 
 
<haskell>
 
 
> -- non monadic
 
> evalNMS :: Term -> MS Int
 
> evalNMS (Con a) x = (a, x + 1)
 
> evalNMS (Add t u) x = let (a, y) = evalNMS t x in
 
> let (b, z) = evalNMS u y in
 
> (a + b, z +1)
 
 
</haskell>
 
 
Monadic
 
 
<haskell>
 
 
> -- monadic
 
 
> type MS a = State -> (a, State)
 
> type State = Int
 
 
> mkMS :: a -> MS a
 
> mkMS a = \x -> (a, x)
 
 
> bindMS :: MS a -> (a -> MS b) -> MS b
 
> bindMS m f = \x ->
 
> let (a, y) = m x in
 
> let (b, z) = f a y in
 
> (b, z)
 
 
> combineMS :: MS a -> MS b -> MS b
 
> combineMS m f = m `bindMS` \_ -> f
 
 
> incState :: MS ()
 
> incState = \s -> ((), s + 1)
 
 
> evalMS :: Term -> MS Int
 
> evalMS (Con a) = incState `combineMS` mkMS a
 
> evalMS (Add t u) = evalMS t `bindMS` \a ->
 
> evalMS u `bindMS` \b ->
 
> incState `combineMS` mkMS (a + b)
 
 
> --evalMS (Add (Con 6) (Add (Con 16) (Add (Con 20) (Con 12)))) 0
 
 
</haskell>
 
 
State and Output
 
 
<haskell>
 
 
> -- state and output
 
 
> type MSO a = State -> (a, State, Output)
 
 
> mkMSO :: a -> MSO a
 
> mkMSO a = \s -> (a, s, "")
 
 
> bindMSO :: MSO a -> (a -> MSO b) -> MSO b
 
> bindMSO m f = \x ->
 
> let (a, y, s1) = m x in
 
> let (b, z, s2) = f a y in
 
> (b, z, s1 ++ s2)
 
 
> combineMSO :: MSO a -> MSO b -> MSO b
 
> combineMSO m f = m `bindMSO` \_ -> f
 
 
> incMSOstate :: MSO ()
 
> incMSOstate = \s -> ((), s + 1, "")
 
 
> outMSO :: Output -> MSO ()
 
> outMSO = \x s -> ((),s, x)
 
 
> evalMSO :: Term -> MSO Int
 
> evalMSO (Con a) = incMSOstate `combineMSO`
 
> outMSO (formatLine (Con a) a) `combineMSO`
 
> mkMSO a
 
> evalMSO (Add t u) = evalMSO t `bindMSO` \a ->
 
> evalMSO u `bindMSO` \b ->
 
> incMSOstate `combineMSO`
 
> outMSO (formatLine (Add t u) (a + b)) `combineMSO`
 
> mkMSO (a + b)
 
 
> --evalMSO (Add (Con 6) (Add (Con 16) (Add (Con 20) (Con 12)))) 0
 
 
</haskell>
 
 
State, Output and do-notation
 
 
<haskell>
 
 
> -- thanks to Brian Hulley
 
 
> newtype MSIO a = MSIO (State -> (a, State, Output))
 
> instance Monad MSIO where
 
> return a = MSIO (\s -> (a, s, ""))
 
> (MSIO m) >>= f = MSIO $ \x ->
 
> let (a, y, s1) = m x in
 
> let MSIO runNextStep = f a in
 
> let (b, z, s2) = runNextStep y in
 
> (b, z, s1 ++ s2)
 
 
 
> incMSOIstate :: MSIO ()
 
> incMSOIstate = MSIO (\s -> ((), s + 1, ""))
 
 
> print_MSOI :: Output -> MSIO ()
 
> print_MSOI x = MSIO (\s -> ((),s, x))
 
 
> eval_MSOI :: Term -> MSIO Int
 
> eval_MSOI (Con a) = do incMSOIstate
 
> print_MSOI (formatLine (Con a) a)
 
> return a
 
 
> eval_MSOI (Add t u) = do a <- eval_MSOI t
 
> b <- eval_MSOI u
 
> incMSOIstate
 
> print_MSOI (formatLine (Add t u) (a + b))
 
> return (a + b)
 
 
> run_MSOI :: MSIO a -> State -> (a, State, Output)
 
> run_MSOI (MSIO f) s = f s
 
 
> --run_MSOI (eval_MSOI (Add (Con 6) (Add (Con 16) (Add (Con 20) (Con 12))))) 0
 
 
</haskell>
 
 
Version 2
 
 
<haskell>
 
 
> -- Thanks Udo Stenzel
 
 
> newtype Eval_SOI a = Eval_SOI { unPackMSOIandRun :: State -> (a, State, Output) }
 
> instance Monad Eval_SOI where
 
> return a = Eval_SOI (\s -> (a, s, ""))
 
> (>>=) m f = Eval_SOI (\x ->
 
> let (a, y, s1) = unPackMSOIandRun m x in
 
> let (b, z, s2) = unPackMSOIandRun (f a) y in
 
> (b, z, s1 ++ s2))
 
 
> incSOIstate :: Eval_SOI ()
 
> incSOIstate = Eval_SOI (\s -> ((), s + 1, ""))
 
 
> print_SOI :: Output -> Eval_SOI ()
 
> print_SOI x = Eval_SOI (\s -> ((),s, x))
 
 
> eval_SOI :: Term -> Eval_SOI Int
 
> eval_SOI (Con a) = do incSOIstate
 
> print_SOI (formatLine (Con a) a)
 
> return a
 
> eval_SOI (Add t u) = do a <- eval_SOI t
 
> b <- eval_SOI u
 
> incSOIstate
 
> print_SOI (formatLine (Add t u) (a + b))
 
> return (a + b)
 
 
> --unPackMSOIandRun (eval_SOI (Add (Con 6) (Add (Con 16) (Add (Con 20) (Con 12))))) 0
 
 
</haskell>
 
   
  +
I will give you an example. I think that the
  +
[http://www.cs.utah.edu/~hal/htut/ "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.
   
==If There's A State We Need Some Law==
+
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.
   
* Is it possible to combine the Stateful evaluator with the one with exceptions in one monads?
+
This probably makes sense for a functional programmer who is studying
* Why yes?
+
Haskell for the first time. But, on the other side it will make the
* Why No?
+
newcomer, who's not a functional programmer, believe that explaining
* Suggestions?
+
monads in terms of "\" is just ugly, and definitely not Haskell.
   
Introducing Monad StateT....
+
This is my problem with Haskell: it hides complexity with
'''(TO BE CONTINUED)'''
+
constructions like "let...in", "where", "do".
   
==Suggested Readings==
+
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.
   
Cale Gibbard, [http://haskell.org/haskellwiki/Monads_as_Containers Monads as Containers]
+
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.
   
Jeff Newbern, [http://www.nomaware.com/monads/html/index.html All About Monads]
+
===Starting from the inside or the outside?===
   
[http://haskell.org/haskellwiki/IO_inside IO Inside]
+
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.
   
[http://sigfpe.blogspot.com/2006/08/you-could-have-invented-monads-and.html You Could Have Invented Monads! (And Maybe You Already Have.) by sigfpe]
+
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.
   
==Acknowledgments==
+
===Prerequisites===
   
Thanks to Neil Mitchell, Daniel Fisher, Bulat Ziganzhin, Brian Hulley
+
As I said, in order to understand this tutorial you need:
and Udo Stenzel for the invaluable help they gave, in the
+
* a basic understanding of functional programming (this is required to understand Haskell after all)
[http://www.haskell.org/mailman/listinfo/haskell-cafe haskell-cafe mailing list],
+
* a basic understanding of the type system:
in understanding this topic.
+
** 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 couldn't do it without their help.
+
I hope I'll be able to write a short introductory summary to these
  +
topics (I will put it below this introductory remarks).
   
Obviously errors are totally mine. But this is a wiki so, please,
+
Have fun with Haskell!
correct them!
 
   
- [[User:AndreaRossato|AndreaRossato]]
+
- [[User:AndreaRossato|Andrea Rossato]]
   
 
[[Category:Tutorials]]
 
[[Category:Tutorials]]
 
[[Category:Idioms]]
 
[[Category:Idioms]]
  +
[[Category:Monad]]

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 (supposed-to-be) 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 haskell-cafe 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 "do-notation". 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 impossible-to-understand-unless-you-have-a-phd 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!

- Andrea Rossato