<TITLE>A Monad Tutorial</TITLE>

<P><DIV ALIGN="CENTER"><H1>Brian's Monad Tutorial</H1></DIV></P>

<P><DIV ALIGN="CENTER"><H2>The Problems With Monad Tutorials</H2></DIV></P>

<P><OL><LI>Bad metaphors- "A monad is like a burrito wrapped in a space

suit- it protects you from the toxic waste, and you can just reach in

and grab all the apples you want." Solution: no metaphors, just

code.</LI>

<LI>Excess of category theory- "A monad is just a monoid in the category

of endofunctors, what's the problem?" Solution: <B>NO CATEGORY

THEORY!</B></LI>

<LI>A need for "hands on" experience- see <A HREF="https://byorgey.wordpress.com/2009/01/12/abstraction-intuition-and-the-monad-tutorial-fallacy/">Abstract Intuition and the Monad Tutoral Fallacy</A>.

Solution: stay concrete, lots of code, homework exercises. For our

concrete examples, I borrow from the blog post

<A HREF="http://blog.sigfpe.com/2006/08/you-could-have-invented-monads-and.html">You Could Have Invented Monads! (And Maybe You Already Have.)</A>.

<LI>The "four faces" of monads: <OL><LI>Where they come from (category

theory)</LI><LI>How they are implemented</LI><LI>How they are

used</LI><LI>How they are thought about or designed with.</LI></OL>

Solution: address each face separately, except the category theory which

we don't need to address.</LI>

<LI>Unfamiliarity with the concept of functions as data- many Monads are

based around treating functions as data, and this is rare in other

languages, and thus unfamiliar to most programmers.

<P><DIV ALIGN="CENTER"><H2>Motivating Example #1</H2></DIV></P>

<P>We have three functions, f, g, and h, so f calls g, and g calls h:</P>

f :: ... -&gt; something

f ... =

...

let r = g ... in

...

something

g :: ... -&gt; somethingElse

g ... =

...

let r = h ... in

...

somethingElse

h :: ... -&gt; whatever

h ... =

...

<P>Now h needs some information (of type blah) from where f is called. So

now we need to thread that information through the whole calling stack:</P>

f :: ... -&gt; blah -&gt; something

f ... blah =

...

let r = g ... blah in

...

something

g :: ... -&gt; blah -&gt; somethingElse

g ... blah =

...

let r = h ... blah in

...

somethingElse

h :: ... -&gt; blah -&gt; whatever

h ... blah =

...

<P><DIV ALIGN="CENTER"><H2>The Reader Type</H2></DIV></P>

<P>I start by introducing a type:</P>

type Reader s a = s -&gt; a

<P>Note that the <CODE>type</CODE> declaration is Haskell is just like

the <CODE>typedef</CODE> declaration in C/C++. All it does is introduce

a type macro- I can always replace the type on the left with the type on

the right. Indeed, I often will, to show what's going on under the hood

(so to speak). So now we can clean up our types a little:</P>

f :: ... -&gt; Reader blah something

...

g :: ... -&gt; Reader blah somethingElse

...

h :: ... -&gt; Reader blah whatever

...

<P>Note: in Haskell, functions are first class, which means it makes

perfect sense to return a function as a value. Also, Haskell has

partial function application- which means there is no difference between

a function returning a function, and having the function just take that

many more arguments. In other words:</P>

-- A function that takes two arguments and returns some value

f foo bar = ...

<P>and:</P>

-- A function that takes one argument and returns a function

-- that takes one argument and returns some value

f foo = (\bar -&gt; ...)

<P>are treate the same. It's even OK to do:</P>

-- A function that takes one argument, does some stuff, and then

-- returns a function that takes one argument and returns some value

f foo =

...

(\bar -&gt; ...)

<P>These three different bits of code are all effectively

equivalent.</P>

<P>We've improved the situation, but not much. What we need is a

special "reader let", which automatically appends the blah value. This

is hard, as it requires help from the compiler. We'll get back to that.

However, there is something we can do now. A little know stunt in

functional programming is that if we have:</P>

-- A let expression.

let x = foo in bar

<P>we can replace it with:</P>

-- a function expression applied to an argument.

(\x -&gt; bar) foo

<P>And the code behaves the same. In fact, this is how let is defined

in theory. Apply is much easier than let to replace in code. So,

instead of a special let, let's do a special apply. Flip the order of

the args, so we can do:</P>

apply foo (\x -&gt; bar)

<P>We want foo to have the type <CODE>Reader s a</CODE>, and we want the

whole thing to have a return type of <CODE>Reader s b</CODE>, so we can

go:</P>

f :: ... -&gt; Reader blah something

f ... =

...

apply (g ...)

(\r -&gt;

...

something)

<P>and have apply do the right thing. And we can make an initial

cut at the code:</P>

apply :: (Reader r a) -&gt; (a -&gt; b) -&gt; Reader r b

-- apply :: (r -&gt; a) -&gt; (a -&gt; b) -&gt; r -&gt; b

apply f g s = g (f s)

<P>This type signature looks familiar. Where have I seen it before?</P>

fmap :: Functor f =&gt; (a -&gt; b) -&gt; f a -&gt; f b

<P>But there is a problem: what happens if we want to call two functions

and thread the variable into both?</P>

f :: ... -&gt; Reader blah something

f ... =

...

apply (g ...)

(\r -&gt;

...

apply (g2 ...)

(\r2 -&gt;

...

something))

<P>I can use fmap for the original <CODE>apply</CODE>, I want

<CODE>apply</CODE> to have the type: <CODE>(Reader r a) -&gt; (a -&gt;

Reader r b) -&gt; Reader r b</CODE>. The <CODE>apply</CODE> function

then becomes:</P>

apply :: Reader r a -&gt; (a -&gt; Reader r b) -&gt; Reader r b

-- apply :: (r -&gt; a) -&gt; (a -&gt; r &gt; b) -&gt; r -&gt; b

apply f g s = g (f s) s

<P>But this causes another problem:</P>

f :: ... -&gt; Reader blah something

f ... =

...

apply (g ...)

(\r -&gt;

...

apply (g2 ...)

(\r2 -&gt;

...

something)) -- Type error right here!

<P>The <CODE>something</CODE> expression has type

<CODE>something</CODE>, but we want it to have type <CODE>Reader blah

something</CODE>. We could user <CODE>fmap</CODE>, or we could just

provide a fixup function:</P>

fixup :: a -&gt; Reader r a

-- fixup :: a -&gt; r -&gt; a

fixup x _ = x

<P>Now we can go:</P>

f :: ... -&gt; Reader blah something

f ... =

...

apply (g ...)

(\r -&gt;

...

apply (g2 ...)

(\r2 -&gt;

...

fixup something))

<P>I will, at this point, just rename <CODE>apply</CODE> to be the operator

<CODE>&gt;&gt;=</CODE>, and the <CODE>fixup</CODE> function to

<CODE>return</CODE>. This should start looking familiar:</P>

f :: ... -&gt; Reader blah something

f ... =

...

(g ...) &gt;&gt;=

(\r -&gt;

...

(g2 ...) &gt;&gt;=

(\r2 -&gt;

...

return something))

<P>Two last things we need, if we want to have Reader be an abstract

data type (i.e., we don't let people see it's just a function under the

hood). We need some way to call f with our initial blah. We need some

function of type:</P>

runReader :: Reader r a -&gt; r -&gt; a

<P>And, we need some way to access the read variable down where we need

it (down in <CODE>h</CODE>). If we had a function:</P>

ask :: Reader r r

<P>We could write <CODE>h</CODE> like:</P>

h :: ... -&gt; Reader blah whatever

h ... = ask (\blah -&gt; ...)

<P><B>HOMEWORK:</B> Implement the <CODE>runReader</CODE> and

<CODE>ask</CODE> functions.</P>

<P><DIV ALIGN="CENTER"><B>Performance</B></DIV></P>

<P>One of the concerns people have with writing this abstract code is

the loss of performance- we're introducing a lot of unnecessary closures

and lambda expressions. Rest assured, the ghc compiler optimizes all of

this, and recovers code equalivalent to our original hand-threaded

code. The ghc compiler knows about the let/apply equivalence (so it's

not so unknown as I lead you to believe), and will happily convert back

from our apply the (more efficient) let representation. Also, it knows

about returning functions vr.s just taking more arguments, and will

happily swap that back. We can write our nice, generic code, and

Haskell will apply the obvious transformations to turn it into efficient

code.</P>

<P><DIV ALIGN="CENTER"><H2>Motivating Example #2</H2></DIV></P>

<P>Same as above, except now h doesn't just take a blah, it returns an

updated blah (common with immutable data):

f :: ... -&gt; blah -&gt; (something, blah)

f ... blah =

...

let (r, blah') = g ... blah in

...

(something, blah')

g :: ... -&gt; blah -&gt; (somethingElse, blah)

g ... blah =

...

let (r, blah') = h ... blah in

...

(somethingElse, blah')

h :: ... -&gt; blah -&gt; (whatever, blah)

h ... blah =

...

<P><DIV ALIGN="CENTER"><H2>The State Type</H2></DIV></P>

<P>We pull the same trick, just a little more complicated. We

define (spelling out the types):</P>

type State s a = s -&gt; (a, s)

(&gt;&gt;=) :: State s a -&gt; (a -&gt; State s b) -&gt; State s b

-- (&gt;&gt;=) :: (s -&gt; (a, s)) -&gt; (a -&gt; s -&gt; (b, s)) -&gt; s -&gt; (b, s)

f &gt;&gt;= g =

-- f :: State s a == s -&gt; (a, s)

-- g :: a -&gt; State s b == a -&gt; s -&gt; (b, s)

-- we want to produce a State s b == s -&gt; (b, s)

\s -&gt;

let (x, s') = f s

g x s'

return :: a -&gt; State s a

-- return :: a -&gt; s -&gt; (a, s)

return x s = (x, s)

<P>So now I can do:</P>

f :: ... -&gt; State blah something

f ... =

...

(g ...) &gt;&gt;=

(\r -&gt;

...

return something)

g :: ... -&gt; State blah somethingElse

g ... blah =

...

(h ...) &gt;&gt;=

(\r -&gt;

...

somethingElse)

<P><B>HOMEWORK:</B> To make <CODE>State</CODE> an abstract type (like we

made <CODE>Reader</CODE>), we need three new functions:

runState :: State s a -&gt; s -&gt; (a, s)

get :: State s s

put :: s -&gt; State s ()

<P>Write these functions. With these funtions, how would you write

<CODE>h</CODE> (approximately)?</P>

<P><DIV ALIGN="CENTER"><H2>The Monad Typeclass</H2></DIV></P>

<P>Now we have a problem. We have two definitions (with very similar

types) of the <CODE>&gt;&gt;=</CODE> operator:</P>

(&gt;&gt;=) :: Reader r a -&gt; (a -&gt; Reader r b) -&gt; Reader r b

(&gt;&gt;=) :: State s a -&gt; (a -&gt; State s b) -&gt; State s b

<P>And two copies of the <CODE>return</CODE> function:</P>

return :: a -&gt; Reader r a

return :: a -&gt; State s a

<P>This causes Haskell to be unhappy. The solution is to introduce a

type class:</P>

class Monad m where

(&gt;&gt;=) :: m a -&gt; (a -&gt; m b) -&gt; m b

return :: a -&gt; m a

<P>Our implementation of <CODE>Reader</CODE> would then be:</P>

type Reader r a = r -&gt; a

instance Monad (Reader r) where

-- We replace the m with (Reader r), so

-- m a -&gt; (a -&gt; m b) -&gt; m b

-- (Reader r) a -&gt; (a -&gt; (Reader r) b) -&gt; (Reader r) b

-- Reader r a -&gt; (a -&gt; Reader r b) -&gt; Reader r b

f &gt;&gt;= g = \r -&gt; g (f r) r

-- a -&gt; m a

-- a -&gt; (Reader r) a

-- a -&gt; Reader r a

return x = \_ -&gt; x

<P>And <CODE>State</CODE> would be:</P>

type State s a = s -&gt; (a, s)

instance Monad (State s) where

f &gt;&gt; g = \s -&gt; let (x, s') = f s in g x s'

return x = \s -&gt; (x, s)

<P><B>HOMEWORK:</B> Is it possible to write the <CODE>fmap</CODE>

function using only <CODE>&gt;&gt;=</CODE> and <CODE>return</CODE>?

What does this mean about the relationship between <CODE>Functor</CODE>

and <CODE>Monad</CODE>?</P>

<P><B>HOMEWORK:</B> Read up on the <CODE>Applicative</CODE> type class-

can it be implemented using only <CODE>&gt;&gt;=</CODE> and

<CODE>return</CODE>? What does that say about the relationship between

<CODE>Applicative</CODE> and <CODE>Monad</CODE>?</P>

<P><B>HOMEWORK:</B> The <CODE>Reader</CODE> type is "half of" the

<CODE>State</CODE> type. Can you implement the "other half"- the

<CODE>Writer</CODE> type? How would you deal with the state not being

written, or being written multiple times?</P>

<P><DIV ALIGN="CENTER"><H2>A Digression</H2></DIV></P>

<P>Consider the following code for a moment:</P>

instance Monad [] where

[] &gt;&gt;= _ = []

(x : xs) &gt;&gt;= f = (f x) ++ (xs &gt;&gt;= f)

return x = [ x ]

<P>So lists are monads.</P>

<P><B>HOMEWORK:</B> Can you write similar definitions for

<CODE>Maybe</CODE>? How about <CODE>Either String</CODE>?</P>

<P><DIV ALIGN="CENTER"><H2>Side effects and the IO Type</H2></DIV></P>

<P>Problem: the only way to guarantee that expression A is evaluated

before expression B is to have expression B depend upon the value

produced by A. But side-effecting computations have ordering dependency

instead of data dependency- we want to print the <CODE>"password:

"</CODE> and <EM>then</EM> read the input line. Many side-effecting

expressions do not even have a sensible data output- OK,

<CODE>getLine</CODE> returns a <CODE>String</CODE>, but what does

<CODE>putStr</CODE> return?</P>

<P>Solution: we model the ordering dependency as a "fake" data

dependency. We introduce a special value, of type <CODE>World#</CODE>

which represents "the state of the outside world". So now:</P>

putStr :: String -&gt; World# -&gt; ((), World#)

getLine :: World# -&gt; (String, World#)

<P>All side-effecting computations now return at least one peice of

"meaningful" data- the updated state of the world.</P>

<P>Problem: Now we need to thread the <CODE>World#</CODE> value through

your code. If only there was a way to do that...</P>

type IO a = State World# a

putStr :: String -&gt; IO ()

getLine :: IO String

<P><B>HOMEWORK:</B> Consider the following Haskell program:</P>

main = getLine &gt;&gt;=

(\line1 -&gt;

getLine &gt;&gt;=

(\line2 -&gt;

putStrLn line1))

<P>If I run it, and give it the input:<PRE>

hello

world

</PRE> (note, as two separate lines), what does the program output, and

why? What does a value of the type <CODE>IO String</CODE> represent?</P>

<P><DIV ALIGN="CENTER"><H2>The Do Notation</H2></DIV></P>

<P>Problem: continually have to introduce new lambda expressions to bind

the results of monadic computations is a pain. It sure would be nice to

have a "monadic let". And Haskell gives us that with the Do

notation:</P>

main = do

line1 &lt;- getLine

line2 &lt;- getLine

putStrLn line1

<P>The do notation "desugars" to a sequence of &gt;&gt;= calls and

lambda expressions. So the code:</P>

do

var &lt;- expr

...

<P>becomes:</P>

expr &gt;&gt;=

(\var -&gt;

do

...)

<P>Likewise,</P>

do

expr

...

<P>becomes:</P>

expr &gt;&gt;=

(\ _ -&gt;

do

...)

<P>And:</P>

do

let var = expr

...

<P>(Note the lack of an "in" there!) becomes: </P>

let var = expr in

do

...

<P>The last statement in a do block is a pure expression which is the

final result. This is normally a <CODE>return</CODE> call, but it

can be a control flow expression that itself contains do blocks:</P>

main = do

putStrLn "What is your guess?"

guess &lt;- getLine

-- Now, this is the last statement in this do block

if ((read guess) == 3::Int) then

-- Which contains two do blocks inside

do

putStrLn "Correct!"

return ()

else

do

putStrLn "Wrong!"

main

<P><B>HOMEWORK:</B> Rewrite the guessing game example above to

explicitly thread the <CODE>World#</CODE> value around (i.e. desugar the

do blocks, inline the definition of <CODE>&gt;&gt;=</CODE>). How does

the last call to main work?</P>

<P><DIV ALIGN="CENTER"><H2>Monad Transformers</H2></DIV></P>

<P>So, <CODE>IO</CODE> is "impure"- but a lot of the monads we've seen

are pure- <CODE>State</CODE>, <CODE>Reader</CODE>, <CODE>Writer</CODE>,

<CODE>Maybe</CODE>, <CODE>Either</CODE>, <CODE>List</CODE>, and so on.

They do mix fairly promiscuously, and cleanly, with other monads. Can

we express that?</P>

type StateT s m a = s -&gt; m (a, s)

instance Monad m =&gt; Monad StateT s m where

f &gt;&gt;= g = \s -&gt; do

(x, s') &lt;- f s

g x s'

return x s = return (x, s)

<P>This is the "State Transformer"- it stacks on top of another monad

and threads a state variable through.</P>

<P><B>HOMEWORK:</B> Write the transformer versions of ReaderT, WriterT,

and MaybeT.</P>

<P><B>HOMEWORK:</B> Look up the source code to the standard StateT,

ReaderT, WriterT, and MaybeT implementations on hackage. How does your

code differ from theres? Why did they design their code the way they

did?</P>

<P><DIV ALIGN="CENTER"><H2>Monad Laws</H2></DIV></P>

<P>The three monad laws:</P>

<P><TABLE CELLPADDING=10><TR><TD>1</TD><TD>Left Identity:</TD><TD><CODE>(return x) &gt;&gt;=

f</CODE></TD><TD>&lt;=&gt;</TD><TD><CODE>f x</CODE></TD></TR>

<TR><TD>2</TD><TD>Right Identity:</TD><TD><CODE>m &gt;&gt;=

return</CODE></TD><TD>&lt;=&gt;</TD><TD><CODE>m</CODE></TD></TR>

<TR><TD>3</TD><TD>Associativity:</TD><TD><CODE>(m &gt;&gt;= f) &gt;&gt;=

g</CODE></TD><TD>&lt;=&gt;</TD><TD><CODE>m&gt;&gt;= (\x -&gt; f x

&gt;&gt;= g)</CODE></TD></TR></TABLE></P>

<P>The english translation:</P>

<P>Rules 1 and 2 mean that the only thing return can do is inject a

value into the monad, it can not perform any other action. Rule 3 says

that the only important thing is the ordering of the bindings. One can

always pull subsequences out into their own values or functions.</P>

<P><EM>In other words, the monad laws just mean that the monad

implementation has to behave sensibly.</EM></P>

<P>The monad laws also only hold in the lack of bottom (expressions that

throw exceptions, go into infinite loops, exit the program, etc.).

Every so often a debate emerges on the haskell mailing lists over wether

the monad laws are actually followed or not. Rather than participating

in such debates, I recommend reading <A

HREF="http://www.cs.ox.ac.uk/jeremy.gibbons/publications/fast+loose.pdf">Fast

and Loose Reasoning is Morally Correct</A>, by Danielsson, Hughes,

Jansso, and Gibbons. Or, better yet, going outside to get some fresh

air and sunshine.</P>

<P><B>HOMEWORK:</B> If you really insist, prove that this implementation

of <CODE>return</CODE> for the List monad is incorrect:</P>

return x = [ x, x ]

<P><B>HOMEWORK:</B> If you really enjoy this sort of thing, go back and

prove all of our implementations up until this point do, in fact, follow

the monad laws.</P>

<P><DIV ALIGN="CENTER"><H2>Designing with Monads</H2></DIV></P>

<P>In terms of design, a monad is:

<UL><LI>An action</LI>

<LI>Returning a value</LI>

<LI>In a domain that has special abilities</LI></UL></P>

<P>There are the operations all monads support (<CODE>&gt;&gt;=</CODE>,

<CODE>return</CODE>), and operations only supported by specific monads

(<CODE>get</CODE>, <CODE>put</CODE>, <CODE>putStrLn</CODE>, etc.). The

"special abilities" of the monad are in these specific operations.</P>

<P><TABLE BORDER=1 CELLPADDING=5>

<TR><TD>Monad</TD><TD>Special abilities</TD></TR>

<TR><TD>IO</TD><TD>Can do I/O and/or side-effects</TD></TR>

<TR><TD>State</TD><TD>Has read/write access to a "global variable"</TD></TR>

<TR><TD>Reader</TD><TD>Has read-only access to a "global variable"</TD></TR>

<TR><TD>Writer</TD><TD>Has write-only access to a "global variable"</TD></TR>

<TR><TD>Maybe</TD><TD>May not produce an output</TD></TR>

<TR><TD>List</TD><TD>May produce multiple outputs</TD></TR>

<P>In addition, you can define your own monads, either directly, or

using one of the standard monads. For example, you might do:</P>

<P><CODE><PRE> type WithDBConn a = Reader DB.Conn a</PRE></CODE></P>

<P>To define a monad whose domain is "has a connection to the database".

This is one of the main ways to structure a Haskell program on the large

scale- using monads to define the major "domains" of a program (code

that needs a connection to the database, etc.).</P>

<P><B>HOMEWORK:</B> Think of a program you might want to write. What

are the major domains that program will want? How would you implement

them?</P>

<P><DIV ALIGN="CENTER"><H2>The last bit of homework</H2></DIV></P>

<P><B>HOMEWORK:</B> Go write Haskell code using monads!</P>

<P><DIV ALIGN="CENTER"><H1>FINI</H1></DIV></P>