The Monadic Way
An evaluation of Philip Wadler's "Monads for functional programming"
This tutorial is a "translation" of Philip Wedler's "Monads for functional programming". (avail. from here)
I'm a Haskell newbie trying to grasp such a difficult concept as the ones of Monad and monadic computation. While "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 wonderful! It explains how to create a monad!
So I decided to "translate it", in order to clarify to myself the topic. And I'm now sharing this traslation (not completed yet) with 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 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
Let's start with something simple: suppose we want to implement a new programming language. We just finished with 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:
> module MyMonads where
> data Term = Con Int
> | Add Term Term
> deriving (Show)
After that we build our interpreter:
> eval :: Term -> Int
> eval (Con a) = a
> eval (Add a b) = eval a + eval b
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!
> 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
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:
evalO (Add t u) = ((a + b),(x ++ y ++ formatLine (Add t u) (a + b)))
where (a, x) = evalO t
(b, y) = evalO u
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:
f x = x + x
"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
f 3
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:
f = \x -> x + x
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:
> bindM :: MOut a -> (a -> MOut b) -> MOut b
> bindM m f = (b, x ++ y)
> where (a, x) = m
> (b, y) = f a
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:
> 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))
> )
> )
Ugly, isn't it?
Let's start from the outside:
bindM (evalM_1 u) (\b -> ((a + b), formatLine (Add t u) (a + b)))
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:
> 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)))
Now, look at the first part:
evalM_2 (Con a) = (a, formatLine (Con a) a)
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 evalM_2 (Con a) is doing, after all.
Very simply:
> mkM :: a -> MOut a
> mkM a = (a, "")
We then need to "insert" some text (Output) in our type M:
> outPut :: Output -> MOut ()
> outPut x = ((), x)
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:
> 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)
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`:
> combineM :: MOut a -> MOut b -> MOut b
> combineM m f = m `bindM` \_ -> f
So the new evaluator:
> 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)
Let's put everything together (and change some names):
> 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)
What Does Bind Bind?
The evaluator looks like:
evalM t >>= \a -> evalM u >>= \b -> outPut "something" >>= \_ -> mkM (a +b)
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)
| (a,Out) >>= \a -> (b,Out) >>= \b -> ((),Out) >>= \_ >>= ((a + b), Out) d | V V V V V V V V ^ ^ ^ ^ o | |__|________^ | | ^ | | | | | | B | |__(++)__|_Out_|__|__(++)__V_____|___|__Out___|_(++)__|___|____| i | | |______(b)__|_____|_____(b)____|__(b)__|___| n | |_________(a)___________|____________|__(a)__| d | |_____()_____|
Clear, isn't it?
"bindM" is just a function that takes care of gluing together, inside a data type, a sequence of computations!
Some Sugar, Please!
Now our evaluator has been completely transformed into a monadic evaluator. That's what it is: a monad.
We have a function that constructs an object of type MO Int, formed by a pair: the result of the evaluation and the accumulated (concatenated) output.
The process of accumulation and the act of parting the MO Int into its component is buried into bindM, that can also preserve some value for later uses.
So we have:
- MO a type constructor for a type carrying a pair composed by an Int and a String;
- bindMO, that gives a direction to the process of evaluation: it concatenates computations and captures some side effects we created.
- mkOM lets us create an object of type MO Int starting from an Int.
As you see this is all we need to create a monad. In other words monads arise from the type system. Everything else is just syntactic 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.
> newtype Eval a = Eval a
> deriving (Show)
So, our type will be an instance of the monad class. We will have to define the methods of this class (>>= and return), but that will be easy since we already done that while defining bindMO and mkMO.
> instance Monad Eval where
> return a = Eval a
> Eval m >>= f = f m
And then we will take the old version of our evaluator and substitute `bindMO` with >>= and `mkMO` with return:
> evalM_4 :: Term -> Eval Int
> evalM_4 (Con a) = return a
> evalM_4 (Add t u) = evalM_4 t >>= \a ->
> evalM_4 u >>= \b ->
> return (a + b)
which is, in the do-notation:
> evalM_5 :: Term -> Eval Int
> evalM_5 (Con a) = return a
> evalM_5 (Add t u) = do a <- evalM_5 t
> b <- evalM_5 u
> return (a + b)
Simple: do binds the result of "eval_M5 t" to a, binds the result of "eval_M5 u" to b and then returns the sum. In a very imperative style.
We can now have an image of our monad: it is out type (Eval) that is 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 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 we attach to each step of the evaluation (the String attached to the 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 notation:
> newtype Eval_IO a = Eval_IO (a, O)
> deriving (Show)
> type O = String
> 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
> 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)
Let's see the evaluator with output in action:
*MyMonads> eval_IO (Add (Con 6) (Add (Con 16) (Add (Con 20) (Con 12))))
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:
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??
Well, actually something happened to the output. Let's compare the output of evalMO (the monadic evaluator written without the do-notation) and eval_IO:
*MyMonads> evalMO (Con 6) (6,"eval (Con 6) <= 6 - ") *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 eval_IO has the Eval_IO stuff. It must be related to the changes we had to do to our evaluator in order to use the do-conation, obviously.
What's changed?
First the type definition. We have now:
newtype Eval_IO a = Eval_IO (a, O)
deriving (Show)
instead of
type MO a = (a, Out)
Moreover our bindMO and mkMO functions changed too, to reflect the change of the type definition:
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
Now return a 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 Eval_IO (a, x) 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:
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
You can see that the "combineM"" method (or (>>)) is automatically derived by
the "bindMO" (or >>=) method:
p >> q = p >>= \ _ -> q
So, what the hell is the old type MO a = (a, Out) that
did not required all this additional work (apart the need to
specifically define (>>)?
Thanks the help of some nice guy of the haskell-cafe mailing list (look at the thread started by 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
(Text to be done yet: just a summary)
In this section we will se how to handle exceptions in our monadic evaluator.
The basic evaluator, non monadic, with exception:
> 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)
Test it with:
evalE (Add (Con 10) (Add (Add (Con 20) (Con 10)) (Con 2)))
The same evaluator now goes monadic:
> 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)
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 field with a label selector (we called it showM).
Just to refresh your memory:
> 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
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>
This is the evaluator that produces output, plus exceptions.
> 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)
Since we have to concatenate output we must check that also the next run of the evaluator will not raise an exception.
> 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
> let out = formatLine (Add t u) (a + b)
> print_IOE out
> if (a+b) == 42
> then raise_IOE $ out ++ "The Ultimate Answer Has Been Computed!! Now I'm tired!"
> else return (a + b)
Run with
eval_IOE (Add (Con 10) (Add (Add (Con 20) (Con 10)) (Con 2)))
Look at the let clause within the do notation: we do not need let since all variable bound within a do procedure will be available all the way down.
Remember m >>= \a -> f >>= \ -> ...
We Need A State
We start adding complexity to our monadic evaluator. But in order to
add a counter we will start over again (to review out knowledeg).
The basic evaluator plus a counter: evalNM takes now the expression to
be evaluated plus an initial state (0) to start counting from.
> -- 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)
The moadic version without do notation.
> -- 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
Now we'll add Output to the stateful evaluator:
> -- 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
State, Output in do-notation. Look at how much the complexity of our (>>=) founction is increasing:
> -- 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
This is e second version that exploit label fields in datatype to decrease the complexity of the binding operations.
> -- Thanks Udo Stenzel
> newtype Eval_SIO a = Eval_SIO { unPackMSIOandRun :: State -> (a, State, Output) }
> instance Monad Eval_SIO where
> return a = Eval_SIO (\s -> (a, s, ""))
> (>>=) m f = Eval_SIO (\x ->
> let (a, y, s1) = unPackMSIOandRun m x in
> let (b, z, s2) = unPackMSIOandRun (f a) y in
> (b, z, s1 ++ s2))
> incSIOstate :: Eval_SIO ()
> incSIOstate = Eval_SIO (\s -> ((), s + 1, ""))
> print_SIO :: Output -> Eval_SIO ()
> print_SIO x = Eval_SIO (\s -> ((),s, x))
> eval_SIO :: Term -> Eval_SIO Int
> eval_SIO (Con a) = do incSIOstate
> print_SIO (formatLine (Con a) a)
> return a
> eval_SIO (Add t u) = do a <- eval_SIO t
> b <- eval_SIO u
> incSIOstate
> print_SIO (formatLine (Add t u) (a + b))
> return (a + b)
> --unPackMSIOandRun (eval_SIO (Add (Con 6) (Add (Con 16) (Add (Con 20) (Con 12))))) 0
If There's A State We Need Some Discipline: Dealing With Complexity
In order to increase the complexity of our monad now we will try to mix State (counter), Exceptions and Output.
This is an email I send to the haskell-cafe mailing list:
Now I'm trying to create a statefull evaluator, with output and exception, but I'm facing a problem I seem not to be able to conceptually solve. Take the code below. Now, in order to get it run (and try to debug) the Eval_SOI type has a Raise constructor that produces the same type of SOIE. Suppose instead it should be constructing something like Raise "something". Moreover, I wrote a second version of >>=, commented out. This is just to help me illustrate to problem I'm facing. Now, >>= is suppose to return Raise if "m" is matched against Raise (second version commented out). If "m" matches SOIE it must return a SOIE only if "f a" does not returns a Raise (output must be concatenated). I seem not to be able to find a way out. Moreover, I cannot understand if a way out can be possibly found. Something suggests me it could be related to that Raise "something". But my feeling is that functional programming could be something out of the reach of my mind... by the way, I teach Law, so perhaps you'll forgive me...;-) If you can help me to understand this problem all I can promise is that I'll mention your help in the tutorial I'm trying to write on "the monadic way"... that seems to lead me nowhere. Thanks for your kind attention. Andrea
This was the code:
data Eval_SOI a = Raise { unPackMSOIandRun :: State -> (a, State, Output) }
| SOIE { unPackMSOIandRun :: State -> (a, State, Output) }
instance Monad Eval_SOI where
return a = SOIE (\s -> (a, s, ""))
m >>= f = SOIE (\x ->
let (a, y, s1) = unPackMSOIandRun m x in
case f a of
SOIE nextRun -> let (b, z, s2) = nextRun y in
(b, z, s1 ++ s2)
Raise e1 -> e1 y --only this happens
)
-- (>>=) m f = case m of
-- Raise e -> error "ciao" -- why this is not going to happen?
-- SOIE a -> SOIE (\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 = SOIE (\s -> ((), s + 1, ""))
print_SOI :: Output -> Eval_SOI ()
print_SOI x = SOIE (\s -> ((),s, x))
raise x e = Raise (\s -> (x,s,e))
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))
if (a + b) == 42
then raise (a+b) " = The Ultimate Answer!!"
else return (a + b)
runEval exp = case eval_SOI exp of
Raise a -> a 0
SOIE p -> let (result, state, output) = p 0 in
(result,state,output) --"Result = " ++ show result ++ " Recursions = " ++ show state ++ " Output = " ++ output
--runEval (Add (Con 10) (Add (Con 28) (Add (Con 40) (Con 2))))
This code will produce
eval (Con 10) <= 10 - eval (Con 28) <= 28 - eval (Con 40) <= 40 - eval (Con 2) <= 2 - = The Ultimate Answer!! eval (Add (Con 28) (Add (Con 40) (Con 2))) <= 70 - eval (Add (Con 10) (Add (Con 28) (Add (Con 40) (Con 2)))) <= 80 -
The exception appears in the output, but executioon is not stopped.
Brian Hulley came up with this solution:
> -- thanks to Brian Hulley
> data Result a
> = Good a State Output
> | Bad State Output Exception
> deriving Show
> newtype Eval_SIOE a = SIOE {runSIOE :: State -> Result a}
> instance Monad Eval_SIOE where
> return a = SIOE (\s -> Good a s "")
> m >>= f = SIOE $ \x ->
> case runSIOE m x of
> Good a y o1 ->
> case runSIOE (f a) y of
> Good b z o2 -> Good b z (o1 ++ o2)
> Bad z o2 e -> Bad z (o1 ++ o2) e
> Bad z o2 e -> Bad z o2 e
> raise_SIOE e = SIOE (\s -> Bad s "" e)
> incSIOEstate :: Eval_SIOE ()
> incSIOEstate = SIOE (\s -> Good () (s + 1) "")
> print_SIOE :: Output -> Eval_SIOE ()
> print_SIOE x = SIOE (\s -> Good () s x)
> eval_SIOE :: Term -> Eval_SIOE Int
> eval_SIOE (Con a) = do incSIOEstate
> print_SIOE (formatLine (Con a) a)
> return a
> eval_SIOE (Add t u) = do a <- eval_SIOE t
> b <- eval_SIOE u
> incSIOEstate
> let out = formatLine (Add t u) (a + b)
> print_SIOE out
> if (a+b) == 42
> then raise_SIOE $ out ++ "The Ultimate Answer Has Been Computed!! Now I'm tired!"
> else return (a + b)
> runEval exp = case runSIOE (eval_SIOE exp) 0 of
> Bad s o e -> "Error at iteration n. " ++ show s ++ " - Output stack = " ++ o ++ " - Exception = " ++ e
> Good a s o -> "Result = " ++ show a ++ " - Iterations = " ++ show s ++ " - Output = " ++ o
Run with runEval (Add (Con 18) (Add (Con 12) (Add (Con 10) (Con 2))))
Taking Complexity Out of a Monad: Monadic Transformers
We have seen how the complexity of (>>=) was growing by adding operations to be done. N We will do the opposite: we will implement a state transformer (I copied StateT).
We will embed our monad in the StateT monad and we will start moving state and output from the inner monad (our one) to the outer monad (StateT).
Let me introduce StateT with some useful functions:
> newtype StateT s m a = StateT {runStateT :: s -> m (a,s) } --StateT (s -> m (a,s))
> instance Monad m => Monad (StateT s m) where
> return a = StateT (\s -> return (a,s))
> StateT m1 >>= k = StateT (\s -> do ~(a,s1) <- m1 s
> let StateT m2 = k a
> m2 s1)
> -- | Execute a stateful computation, as a result we get
> -- the result of the computation, and the final state.
> runState :: s -> StateT s m a -> m (a,s)
> runState s (StateT m) = m s
> -- | Execute a stateful computation, ignoring the final state.
> evalState :: Functor m => s -> StateT s m a -> m a
> evalState s m = fmap fst (runState s m)
> -- | Execute a stateful computation, just for the side effect.
> execState :: Functor m => s -> StateT s m a -> m s
> execState s m = fmap snd (runState s m)
> liftT :: (Monad m) => m a -> StateT s m a
> liftT m = StateT (\s -> do x <- m
> return (x,s))
StateT is pleased to meet you!.
And now out monad, with state out from it:
> data MTa a = FailTa Exception
> | DoneTa {unpackDoneTa :: (a,O) }
> deriving (Show)
> instance Monad MTa where
> return a = DoneTa (a, "")
> m >>= f = case m of
> FailTa e -> FailTa e
> DoneTa (a, x) -> case (f a) of
> FailTa e1 -> FailTa e1
> DoneTa (b, y) -> DoneTa (b, x ++ y)
> instance Functor MTa where
> fmap _ (FailTa e) = FailTa e
> fmap f (DoneTa (r,o)) = DoneTa ((f r),o)
> raiseTa_SIOE :: O -> StateT Int MTa a
> raiseTa_SIOE e = liftT (FailTa e)
> printTa_SIOE :: O -> StateT Int MTa ()
> printTa_SIOE x = liftT (DoneTa ((), x))
> incTaState :: StateT Int MTa ()
> incTaState = StateT (\s -> return ((), s + 1))
> evalTa_SIOE :: Term -> StateT Int MTa Int
> evalTa_SIOE (Con a) = do incTaState
> printTa_SIOE (formatLine (Con a) a)
> return a
> evalTa_SIOE (Add t u) = do a <- evalTa_SIOE t
> b <- evalTa_SIOE u
> incTaState
> let out = formatLine (Add t u) (a + b)
> printTa_SIOE out
> if (a+b) == 42
> then raiseTa_SIOE $ out ++ "The Ultimate Answer Has Been Computed!! Now I'm tired!"
> else return (a + b)
> runEvalTa :: Term -> String
> runEvalTa exp = case runStateT (evalTa_SIOE exp) 0 of
> FailTa e -> e
> DoneTa (~(r,s),o)-> "Result = " ++ show r ++ "; Iteration = " ++ show s ++ "; Output = " ++ o
> runEvalTa1 :: Term -> String
> runEvalTa1 exp = case runState 0 (evalTa_SIOE exp) of
> FailTa e -> e
> DoneTa ((r,s),o) -> "Result = " ++ show r ++ "; Iteration = " ++ show s ++ "; Output = " ++ o
> runEvalTa2 :: Term -> String
> runEvalTa2 exp = case evalState 0 (evalTa_SIOE exp) of
> FailTa e -> e
> DoneTa (r,o) -> "Result = " ++ show r ++ "; Output = " ++ o
> runEvalTa3 :: Term -> String
> runEvalTa3 exp = case execState 0 (evalTa_SIOE exp) of
> FailTa e -> e
> DoneTa (s,o) -> "Iterations = " ++ show s ++ "; Output = " ++ o
Now we take output away from the inner monad and place it in the outer one (StateT):
> data MTb a = FailTb Exception
> | DoneTb {unpackDoneTb :: a }
> deriving (Show)
> type IOs = String
> type StateIO = (IOs,Int)
> instance Monad MTb where
> return a = DoneTb a
> m >>= f = case m of
> FailTb e -> FailTb e
> DoneTb a -> f a
> instance Functor MTb where
> fmap _ (FailTb e) = FailTb e
> fmap f (DoneTb b) = DoneTb (f b)
> raiseTb_SIOE :: O -> StateT StateIO MTb a
> raiseTb_SIOE e = liftT (FailTb e)
> printTb_SIOE :: O -> StateT StateIO MTb ()
> printTb_SIOE x = StateT (\(o,s) -> return ((), (o ++ x,s)))
> incTbStateIO :: StateT StateIO MTb ()
> incTbStateIO = StateT (\(o,s) -> return ((), (o,s + 1)))
> evalTb_SIOE :: Term -> StateT StateIO MTb Int
> evalTb_SIOE (Con a) = do incTbStateIO
> printTb_SIOE (formatLine (Con a) a)
> return a
> evalTb_SIOE (Add t u) = do a <- evalTb_SIOE t
> b <- evalTb_SIOE u
> incTbStateIO
> let out = formatLine (Add t u) (a + b)
> printTb_SIOE out
> if (a+b) == 42
> then raiseTb_SIOE $ out ++ "The Ultimate Answer Has Been Computed!! Now I'm tired!"
> else return (a + b)
We take away complexity from >>= and put it in the function we need to use to manipulate content in our StateT monad.
This are some wrapper to the evaluator to get the risult and the side-effects produced by evaluation:
> runEvalTb :: Term -> String
> runEvalTb exp = case runStateT (evalTb_SIOE exp) ("",0) of
> FailTb e -> e
> DoneTb (r,~(o,s)) -> "Result = " ++ show r ++ "; Iteration = " ++ show s ++ "; Output = " ++ o
> runEvalTb1 :: Term -> String
> runEvalTb1 exp = case runState ("",0) (evalTb_SIOE exp) of
> FailTb e -> e
> DoneTb (r,~(o,s)) -> "Result = " ++ show r ++ "; Iteration = " ++ show s ++ "; Output = " ++ o
> runEvalTb2 :: Term -> String
> runEvalTb2 exp = case evalState ("",0) (evalTb_SIOE exp) of
> FailTb e -> e
> DoneTb r -> "Result = " ++ show r
> runEvalTb3 :: Term -> String
> runEvalTb3 exp = case execState ("",0) (evalTb_SIOE exp) of
> FailTb e -> e
> DoneTb (o,s) -> "Iterations = " ++ show s ++ " - Output = " ++ o
And now wewill keep in the inner monad only the result of the evaluation.
> data MT a = FailT Exc
> | DoneT {unpackDoneT :: a }
> deriving (Show)
> type Exc = String
> type IOstack = [Output]
> newtype StateTIO = StateTIO {unPackStateTIO :: (IOstack,Exc,Int)}
> deriving(Show)
> instance Monad MT where
> return a = DoneT a
> m >>= f = case m of
> FailT e -> FailT e
> DoneT a -> f a
> instance Functor MT where
> fmap _ (FailT a) = FailT a
> fmap f (DoneT a) = DoneT (f a)
Simple isn't it?
The complexity is now below:
> stopExecT_SIOE :: O -> StateT StateTIO MT Int
> stopExecT_SIOE exc = StateT (\s -> do x <- FailT exc
> return (x, s))
> catchT_SIOE exc = StateT (\(StateTIO (o,e,s)) ->
> return ((), StateTIO (o ,"Exception at Iteration " ++
> show s ++ ": " ++ exc ++ " - " ++ e,s)))
> printT_SIOE :: Output -> StateT StateTIO MT ()
> printT_SIOE x = StateT (\(StateTIO (o,e,s)) -> return ((), StateTIO (x:o,e,s)))
> incTstateIO :: StateT StateTIO MT ()
> incTstateIO = StateT (\(StateTIO (o,e,s)) -> return ((),StateTIO (o,e,s + 1)))
> evalT_SIOE :: Term -> StateT StateTIO MT Int
> evalT_SIOE (Con a) = do incTstateIO
> printT_SIOE (formatLine (Con a) a)
> return a
> evalT_SIOE (Add t u) = do a <- evalT_SIOE t
> b <- evalT_SIOE u
> incTstateIO
> let out = formatLine (Add t u) (a + b)
> printT_SIOE out
> case (a+b) of
> 42 -> do catchT_SIOE "The Ultimate Answer Has Been Computed!! Now I'm tired!"
> return (a+b)
> 11 -> stopExecT_SIOE "11.... I do not like this number!"
> otherwise -> return (a + b)
But now we have exceptions to stop execution and debugging output.
Some helper functions:
> runEvalT :: Term -> String
> runEvalT exp = case runStateT (evalT_SIOE exp) (StateTIO ([],"",0)) of
> FailT e -> e
> DoneT (r,StateTIO (o,e,s)) -> "Result = " ++ show r ++ "; Iteration = " ++ show s ++
> "; Output = " ++ show o ++ " - Exceptions = " ++ e
> runEvalT1 :: Term -> String
> runEvalT1 exp = case runState (StateTIO ([],"",0)) (evalT_SIOE exp) of
> FailT e -> e
> DoneT (r,StateTIO(o,e,s)) -> "Result = " ++ show r ++ "; Iteration = " ++ show s
> ++ "; Output = " ++ show o ++ " - Exceptions = " ++ e
> runEvalT2 :: Term -> String
> runEvalT2 exp = case evalState (StateTIO ([],"",0)) (evalT_SIOE exp) of
> FailT e -> e
> DoneT r -> "Result = " ++ show r
> runEvalT3 :: Term -> String
> runEvalT3 exp = case execState (StateTIO ([],"",0)) (evalT_SIOE exp) of
> FailT e -> e
> DoneT (StateTIO (o,e,s)) -> "Iterations = " ++ show s ++
> " - Output = " ++ show o ++ " - Exceptions = " ++ e
> showOut :: [String] -> IO ()
> showOut [] = return ()
> showOut (a:xs) = do print a
> showOut xs
> runMyEval :: Term -> IO ()
> runMyEval exp = let StateTIO (a,b,c) = unpackDoneT $ execState (StateTIO ([],"",0)) (evalT_SIOE exp) in
> showOut $ reverse a
Some tests:
*MyMonads> runEvalT (Add (Con 18) (Add (Con 12) (Add (Con 10) (Con 2)))) "Result = 42; Iteration = 7; Output = [\"eval (Add (Con 18) (Add (Con 12) (Add (Con 10) (Con 2)))) <= 42 - \",\"eval (Add (Con 12) (Add (Con 10) (Con 2))) <= 24 - \",\"eval (Add (Con 10) (Con 2)) <= 12 - \",\"eval (Con 2) <= 2 - \",\"eval (Con 10) <= 10 - \",\"eval (Con 12) <= 12 - \",\"eval (Con 18) <= 18 - \"] - Exceptions = Exception at Iteration 7: The Ultimate Answer Has Been Computed!! Now I'm tired! - " *MyMonads> runEvalT2 (Add (Con 18) (Add (Con 12) (Add (Con 10) (Con 2)))) "Result = 42" *MyMonads> runEvalT3 (Add (Con 18) (Add (Con 12) (Add (Con 10) (Con 2)))) "Iterations = 7 - Output = [\"eval (Add (Con 18) (Add (Con 12) (Add (Con 10) (Con 2)))) <= 42 - \",\"eval (Add (Con 12) (Add (Con 10) (Con 2))) <= 24 - \",\"eval (Add (Con 10) (Con 2)) <= 12 - \",\"eval (Con 2) <= 2 - \",\"eval (Con 10) <= 10 - \",\"eval (Con 12) <= 12 - \",\"eval (Con 18) <= 18 - \"] - Exceptions = Exception at Iteration 7: The Ultimate Answer Has Been Computed!! Now I'm tired! - " *MyMonads> runEvalT3 (Add (Con 1) (Add (Con 7) (Add (Con 1) (Con 2)))) "Iterations = 7 - Output = [\"eval (Add (Con 1) (Add (Con 5) (Add (Con 1) (Con 2)))) <= 9 - \",\"eval (Add (Con 5) (Add (Con 1) (Con 2))) <= 8 - \",\"eval (Add (Con 1) (Con 2)) <= 3 - \",\"eval (Con 2) <= 2 - \",\"eval (Con 1) <= 1 - \",\"eval (Con 5) <= 5 - \",\"eval (Con 1) <= 1 - \"] - Exceptions = " *MyMonads> runEvalT3 (Add (Con 1) (Add (Con 7) (Add (Con 1) (Con 2)))) "11.... I do not like this number!" *MyMonads> runMyEval (Add (Add (Add (Add (Con 10) (Con 2)) (Add (Con 12) (Con 3))) (Con 3)) (Con 10)) "eval (Con 10) <= 10 - " "eval (Con 2) <= 2 - " "eval (Add (Con 10) (Con 2)) <= 12 - " "eval (Con 12) <= 12 - " "eval (Con 3) <= 3 - " "eval (Add (Con 12) (Con 3)) <= 15 - " "eval (Add (Add (Con 10) (Con 2)) (Add (Con 12) (Con 3))) <= 27 - " "eval (Con 3) <= 3 - " "eval (Add (Add (Add (Con 10) (Con 2)) (Add (Con 12) (Con 3))) (Con 3)) <= 30 - " "eval (Con 10) <= 10 - " "eval (Add (Add (Add (Add (Con 10) (Con 2)) (Add (Con 12) (Con 3))) (Con 3)) (Con 10)) <= 40 - " *MyMonads>
What Comex Next...
Let's see... Fist we must complete the text above!!
Suggested Readings
Cale Gibbard, Monads as Containers
Jeff Newbern, All About Monads
You Could Have Invented Monads! (And Maybe You Already Have.) by sigfpe
Acknowledgments
Thanks to Neil Mitchell, Daniel Fisher, Bulat Ziganzhin, Brian Hulley and Udo Stenzel for the invaluable help they gave, in the haskell-cafe mailing list, in understanding this topic.
I couldn't do it without their help.
Obviously errors are totally mine. But this is a wiki so, please, correct them!