monad thinking process
Andre W B Furtado
awfurtado@uol.com.br
Sat, 26 Jan 2002 01:18:11 -0200
This is a multi-part message in MIME format.
------=_NextPart_000_007F_01C1A607.5224A640
Content-Type: text/plain;
charset="iso-8859-1"
Content-Transfer-Encoding: 7bit
Just check this monad tutorial (attached). It's really great for beginners.
-- Andre
------=_NextPart_000_007F_01C1A607.5224A640
Content-Type: message/rfc822;
name="Monads for the Working Haskell Programmer (fwd).eml"
Content-Transfer-Encoding: 7bit
Content-Disposition: attachment;
filename="Monads for the Working Haskell Programmer (fwd).eml"
Received: by parkinson (mbox awfurtado)
(with Cubic Circle's cucipop (v1.22 1998/04/11) Wed Jun 6 14:23:34 2001)
X-From_: root Wed Jun 6 14:20:24 2001
Received: from recife.cin.ufpe.br (recife.cin.ufpe.br [150.161.2.1])
by capote.uol.com.br (8.9.1/8.9.1) with ESMTP id OAA15977
for <awfurtado@uol.com.br>; Wed, 6 Jun 2001 14:20:01 -0300 (BRT)
Received: from caruaru.cin.ufpe.br (caruaru [172.19.33.30])
by recife.cin.ufpe.br (8.11.2/8.11.2) with ESMTP id f56HIu529463
for <awfurtado@uol.com.br>; Wed, 6 Jun 2001 14:18:56 -0300 (EST)
Received: from localhost (awbf@localhost)
by caruaru.cin.ufpe.br (8.9.3+Sun/8.9.1) with ESMTP id OAA05937
for <awfurtado@uol.com.br>; Wed, 6 Jun 2001 14:18:56 -0300 (EST)
X-Authentication-Warning: caruaru.cin.ufpe.br: awbf owned process doing -bs
Date: Wed, 6 Jun 2001 14:18:55 -0300 (EST)
From: Andre W B Furtado <awbf@cin.ufpe.br>
X-X-Sender: <awbf@caruaru>
To: Eu <awfurtado@uol.com.br>
Subject: Monads for the Working Haskell Programmer (fwd)
Message-ID: <Pine.GSO.4.32.0106061418520.5912-200000@caruaru>
MIME-Version: 1.0
Content-Type: MULTIPART/Mixed; BOUNDARY=------------AA9F6594372313DC3CB49701
Content-ID: <Pine.GSO.4.32.0106061418521.5912@caruaru>
This message is in MIME format. The first part should be readable text,
while the remaining parts are likely unreadable without MIME-aware tools.
Send mail to mime@docserver.cac.washington.edu for more info.
--------------AA9F6594372313DC3CB49701
Content-Type: TEXT/PLAIN; CHARSET=US-ASCII
Content-ID: <Pine.GSO.4.32.0106061418522.5912@caruaru>
---------- Forwarded message ----------
Date: Tue, 05 Jun 2001 11:26:12 -0300
From: Andre Santos <alms@cin.ufpe.br>
Newsgroups: depto.cursos.grad.if098
Subject: Monads for the Working Haskell Programmer
http://www.engr.mun.ca/~theo/Misc/haskell_and_monads.htm
--------------AA9F6594372313DC3CB49701
Content-Type: TEXT/HTML; CHARSET=us-ascii; NAME="haskell_and_monads.htm"
Content-ID: <Pine.GSO.4.32.0106061418523.5912@caruaru>
Content-Description:
Content-Disposition: INLINE; FILENAME="haskell_and_monads.htm"
<html>
<head>
<meta name="GENERATOR" content="Microsoft FrontPage 3.0">
<title>Monads for the Working Haskell Programmer</title>
<style>
PRE {
margin-right: 5%;
margin-left: 5%;
width: 90% ;
padding-left: 3%;
padding-right: 3%;
padding-top: 16px;
padding-bottom: 16px;
color: #000000;
background-color: #ffcc99;
font-size: 100%; }
</style>
</head>
<body topmargin="20" leftmargin="20">
<h1 align="center">Monads for the Working Haskell Programmer <br>
-- a short tutorial.</h1>
<p align="center">Theodore Norvell<br>
Memorial University of Newfoundland</p>
<p><em>New: Updated to Haskell '98.</em></p>
<p>This short tutorial introduces monads to Haskell programmers. It applies to Haskell
'98. Gofer programmers (are there any left?) can read it too; there is a section at the
end detailing the differences between Haskell and Gofer around monads and another about
the differences between Haskell 1.3, Haskell 1.4, and Haskell 98.</p>
<p>The reader is assumed to have a familiarity with the basics of Haskell programming such
as data declarations, function definitions, and lambda expressions. Familiarity with
classes and instance declarations will help.</p>
<h2>Simulating states without Monads</h2>
<p>Consider the following function</p>
<pre>f1 w a = let (b, x) = g1 w a
(c, y) = h1 w x b
(d, z) = i1 w x y c
in (d, z)</pre>
<p>where <tt>a</tt>, <tt>b</tt>, <tt>c</tt>, and <tt>d</tt> all have the same type, <tt>State</tt>.
In a sense this definition is very similar to an imperative program in which <tt>a</tt>
represents the initial state, <tt>d</tt> represents the final state, and <tt>b</tt> and <tt>c</tt>
represent intermediate states. The functions <tt>f1 w</tt>, <tt>g1 w</tt>, <tt>h1 w x</tt>,
and <tt>i1 w x y</tt> can be thought of as imperative routines that transform the state
and produce results. The results are like the return values in C programs and are bound to
variables <tt>x</tt>, <tt>y</tt>, and <tt>z</tt> in the example. A C routine that
corresponds to this would look something like this:</p>
<pre>int f1(float w) {
const char x = g1(w) ;
const double y = h1(w, x) ;
const int z = i1(w, x, y) ;
return z ; }</pre>
<p>All this explicit passing of states around can get a bit tedious, especially when
programs are modified. It also makes the program hard to read vs. the equivalent C
program. </p>
<p>Note that if we ignore the <tt>w</tt>, <tt>x</tt>, <tt>y</tt>, and <tt>z</tt>, then <tt>g1</tt>,
<tt>h1</tt>, and <tt>i1</tt> are being composed. Can we define a kind of "composition
operator" that allows us to deal with the returned values as well as the state?</p>
<h2>Simulating states with Monads</h2>
<p>The functions that transform the state in the example above all have the type <tt>State
-> (State, a)</tt> for some result type <tt>a</tt>. Let's generalize over the type of
the state and create a type to represent these transforms</p>
<pre>type StateTrans s a = s -> (s, a)</pre>
<p>Let us define two functions. The first is a kind of composition function.</p>
<pre>(>>=) :: StateTrans s a ->
(a -> StateTrans s b) ->
StateTrans s b
p >>= k = \s0 -> let (s1, a) = p s0
q = k a
in q s1</pre>
<p>The second is a function that turns a value into an "imperative program" that
does not change the state, but returns the result.</p>
<pre>return :: a -> StateTrans s a
return a = \s -> (s, a)</pre>
<p>Our original function may now be written with all the shunting of state around hidden
by these operators:</p>
<pre>f w = (g w) >>= (\x -> (h w x) >>= (\y -> (i w x y) >>= (\z -> return z)))</pre>
<p>You could also format this as follows</p>
<pre>f w = g w >>= \x ->
h w x >>= \y ->
i w x y >>= \z ->
return z</pre>
<p>You should verify that <tt>f</tt> is equal to <tt>f1</tt>, if <tt>g = g1</tt>, <tt>h =
h1</tt>, and <tt>i = i1</tt>.</p>
<p>(Warning, if you really try to make the above definitions of <tt>>>=</tt> and <tt>return</tt>,
your Haskell compiler will complain, for reasons that will be explained later. However,
you could try changing the names a little, e.g. change <tt>>>=</tt> to <tt>>==</tt>
and change <tt>return</tt> to <tt>rtn</tt>.)</p>
<h2>A nicer syntax</h2>
<p>Now Haskell provides a nice syntax to sugar-coat the calls to <tt>>>=</tt>. It
turns out that the definition of f can also be written as</p>
<pre>f w = do x <- g w
y <- h w x
z <- i w x y
return z</pre>
<p>The "do" is a keyword of Haskell. Any program involving a "do" can
be translated to one that doesn't use "do" by the following 4 rules:</p>
<p>1 An expression</p>
<table border="0" cellspacing="0" cellpadding="3">
<tr>
<td><tt>do</tt></td>
<td><em>pattern</em> <tt><-</tt> <em>expression</em></td>
</tr>
<tr>
<td></td>
<td><em>morelines</em></td>
</tr>
</table>
<p>becomes <em>expression</em> <tt>>>= (\<em> </tt>pattern</em> <tt>-> do</tt> <em>morelines</em><tt>)</tt></p>
<p>2 An expression</p>
<table border="0" cellspacing="0" cellpadding="3">
<tr>
<td><tt>do</tt></td>
<td><em>expression</em></td>
</tr>
<tr>
<td></td>
<td><em>morelines</em></td>
</tr>
</table>
<p>becomes <em>expression</em> <tt>>> do</tt> <em>morelines</em></p>
<p>3 An expression </p>
<table border="0" cellspacing="0" cellpadding="3">
<tr>
<td><tt>do</tt></td>
<td><tt>let </tt><em>declarationList</em></td>
</tr>
<tr>
<td></td>
<td><em>morelines</em></td>
</tr>
</table>
<p>becomes </p>
<table border="0" cellspacing="0" cellpadding="3">
<tr>
<td><tt>let</tt></td>
<td><em>declarationList</em></td>
</tr>
<tr>
<td><tt>in</tt></td>
<td><tt>do </tt><em>morelines</em></td>
</tr>
</table>
<p>4. Finally when there is only one line in the do, an expression</p>
<table border="0" cellspacing="0" cellpadding="3">
<tr>
<td><tt>do</tt></td>
<td><em>expression</em></td>
</tr>
</table>
<p>becomes <em>expression</em></p>
<p>In the second rule, we saw the >> operator; this is used when the result of the
first operand is not subsequently used. It can always be defined as</p>
<pre>p >> q = p >>= (\ _ -> q)</pre>
<p>So</p>
<pre> do p
q</pre>
<p>is the same as</p>
<pre> do _ <- p
q</pre>
<p>The "do" notation follows the same conventions as other multi-line constructs
in Haskell. All lines must be vertically alligned. Alternatively, you may use braces and
semicolons if you prefer "free format":</p>
<pre> do {x <- g w ; y <- h w x ;
z <- i w x y ; return z }</pre>
<h2>How to Really Declare the StateTrans Monad.</h2>
<p>So far we've seen the monad concept applied to implicitly passing state. However monads
can be used to implement several other programming features including: consuming input,
producing output, exceptions and exception handling, nondeterminisim. To handle this
variety, the basic operations of <tt>>>=</tt> and <tt>return</tt> are overloaded
functions. </p>
<p>(Haskell requires that overloaded functions be declared in class declarations and
defined in instance declarations. This is the reason that <tt>>>=</tt> and <tt>return</tt>
can not be defined exactly as described in previous sections.)</p>
<p>The class that <tt>>>=</tt> and <tt>return</tt> are declared in is
called Monad and is itself declared in the Haskell Prelude. That declaration looks
like this</p>
<pre>class Monad m where
(>>=) :: m a -> (a -> m b) -> m b
(>>) :: m a -> m b -> m b
return :: a -> m a
fail :: String -> m a
m >> k = m >>= \_ -> k
fail s = error s</pre>
<p>To make a state transform monad that actually works with Haskell's "do"
notation, we have to declare <tt>>>=</tt> and <tt>return</tt> within an instance
declaration. There is one minor problem; type synonyms can not be used in instance
declarations, so we define <tt>StateTrans s a</tt> as a new type.</p>
<pre>newtype StateTrans s a = ST( s -> (s, a) )</pre>
<p>and we define the functions <tt>return</tt> and <tt>>>=</tt> for this type as
follows:</p>
<pre>instance Monad (StateTrans s)
where
-- (>>=) :: StateTrans s a -> (a -> StateTrans s b) -> StateTrans s b
(ST p) >>= k = ST( \s0 -> let (s1, a) = p s0
(ST q) = k a
in q s1 )
-- return :: a -> StateTrans s a
return a = ST( \s -> (s, a) )</pre>
<p>We don't need to define the <tt>>></tt> operator; it is defined automatically in
terms of <tt>>>=</tt>.</p>
<p>Note these new definitions change the type of functions like our example function
f. Indeed f is no longer equal to f1, since its type is different. To apply
members of the monad, we define a new function</p>
<pre>applyST :: StateTrans s a -> s -> (s, a)
applyST (ST p) s = p s</pre>
<p>Now <tt>applyST f</tt> is equal to <tt>f1</tt>.</p>
<h2>Which is the Monad?</h2>
<p>Technically each Monad (in Haskell) is not a type, but a "type contructor".
In our state transformer example, we have actually declared an infinite set of monads. For
each type <em>s,</em> there is a type constructor<tt> StateTrans </tt><em>s</em><tt>.</tt>
Each such type constructor has been declared to be a Monad by the instance declaration
above.</p>
<h2>An example</h2>
<p>A short example shows how the StateTrans monad lets you code in a fairly imperative
style.</p>
<p>We will implement a variation on Euclid's algorithm for finding the greatest common
divisor of two positive integers.</p>
<pre> while x != y do
if x < y
then y := y-x
else x := x-y
return x</pre>
<p>First we must define a type to represent the state:</p>
<pre>type ImpState = (Int, Int)</pre>
<p>Next we define some simple state transformers to access and change the state. We use
the type <tt>()</tt> and its sole value, <tt>()</tt>, when a state transformer does not
return a useful value.</p>
<pre>getX, getY :: StateTrans ImpState Int
getX = ST(\(x,y)-> ((x,y), x))
getY = ST(\(x,y)-> ((x,y), y))
putX, putY :: Int -> StateTrans ImpState ()
putX x' = ST(\(x,y)->((x',y),()))
putY y' = ST(\(x,y)->((x,y'),()))</pre>
<p>Now we can write the algorithm with the state squarely in the background:</p>
<pre>gcdST :: StateTrans ImpState Int
gcdST = do x <- getX
y <- getY
(if x == y
then
return x
else if x < y
then
do putY (y-x)
gcdST
else
do putX (x-y)
gcdST)</pre>
<p>And finally a function to construct an initial state, run the program and discard the
final state</p>
<pre>greatestCommonDivisor x y = snd( applyST gcdST (x,y) )</pre>
<p>This small example only hints at the utility of monads. It would be much shorter to
write the algorithm in a conventional functional style. The savings from not having to
explicitly pass the state around become larger as the program becomes larger.</p>
<h2>Monads, Monoids, and Identities</h2>
<p>The term "monad" comes from category theory, which is a branch of algebra
(or, depending on whom you talk to, algebra is a branch of category theory). There is no
need to understand the algebra at all to understand the use of monads in functional
programming. This section and the next, just touch on the algebra a little bit.</p>
<p>Monads share some similarity with monoids<a href="#monoid">*</a> , with <tt>>>=</tt>
being similar to the monoid operation and the <tt>return</tt> operator taking the place of
the identity member. Specifically we have the following identities</p>
<p align="center"><tt>return a >>= k = k a</tt></p>
<p align="center"><tt>p >>= return = p</tt></p>
<p align="center"><tt>(p >>= j) >= k = p >>=
(\x->(j x >>= k)) </tt> [provided x is not free in j
or k]</p>
<p align="left">These identities hold in the StateTrans monad and ought to hold for any
monad we define.</p>
<h2 align="left">Zeros and addition</h2>
<p align="left">Monoids sometimes also have a zero member and an addition operator.</p>
<p align="left">In Haskell, the zero member of a monad is called <tt>mzero</tt> and the
relevant identity is</p>
<p align="center"><tt>mzero >>= k = mzero</tt></p>
<p align="left">In a state transformation monad, <tt>mzero</tt> might represent an
exception. I.e. an indication that the task can not be completed.</p>
<p align="left">When a Monad has a zero member, it often also has an addition operation, <tt>mplus</tt>,
obeying the following additional identities</p>
<p align="center"><tt>p `mplus` mzero = p = mzero `mplus` p</tt></p>
<p align="center"><tt>p `mplus` (q `mplus` r) = (p `mplus` q) `mplus` r</tt></p>
<p align="left">It turns out that monads with zeros and addition are common enough that
there is a library class, called MonadPlus, defined to encompass them.</p>
<p align="left">If <tt>mzero</tt> represents failure to complete a computation, <tt>mplus</tt>
might represent a way of combining alternative computations such that, if one fails, the
other can succeed instead.</p>
<h2 align="left">Exceptions, exception handling, and backtracking.</h2>
<p align="left">We generalize the StateTrans monad, to include a zero element and an
addition operation. To do this we must change the type to include the possibility of
failure:</p>
<div align="left">
<pre>newtype StateTransEx s a = STE( s -> Maybe (s, a) )</pre>
</div>
<p align="left">(The Maybe type constructor is defined in the Haskell Prelude as</p>
<div align="left">
<pre>data Maybe t = Just t
| Nothing</pre>
</div>
<p align="left">"Maybe" is itself a Monad, but I won't be using that fact here.)</p>
<p align="left">We use <tt>Nothing</tt> to represent failure, i.e., an exception, and <tt>Just
(s,a)</tt> to represent success with result <tt>a</tt> and new state <tt>s</tt>.</p>
<p align="left">We must define <tt>>>=</tt> and <tt>return</tt> so that it is a
monad. We define <tt>>>=</tt> so that it propagates exceptions. That is, if<tt> p</tt>
throws an exception, then so does <tt>p >>= f </tt>.</p>
<div align="left">
<pre>instance Monad (StateTransEx s)
where
-- (>>=) :: StateTransEx s a -> (a -> StateTransEx s b) -> StateTransEx s b
(STE p) >>= k = STE( \s0 -> case p s0 of
Just (s1, a) -> let (STE q) = k a
in q s1
Nothing -> Nothing)
-- return :: a -> StateTransEx s a
return a = STE( \s -> Just (s, a) )</pre>
</div>
<p align="left">We define <tt>mzero</tt> and <tt>mplus</tt> to make <tt>StateTransEx s</tt>
a member of class MonadPlus. <tt>mzero</tt> will mean throw an exception. <tt>mplus</tt>
will give a means to recover from an exception; <tt>mplus p q</tt> will mean, execute p,
but if an exception is thrown in p, then recover by executing q instead.</p>
<p align="left">Since MonadPlus is not in the Prelude, but rather the Monad library, we
must import it from the Monad library (the import declaration must go at the top of your
Haskell module).</p>
<div align="left">
<pre>import Monad( MonadPlus( .. ), guard )
instance MonadPlus (StateTransEx s)
where
-- mzero :: StateTransEx s a
mzero = STE( \s -> Nothing )
-- mplus :: StateTransEx s a -> StateTransEx s a -> StateTransEx s a
(STE p) `mplus` (STE q) = STE( \s0 -> case p s0 of
Just (s1, a) -> Just (s1, a)
Nothing -> q s0 )
applySTE (STE p) s = p s</pre>
</div>
<p>Now, if we execute <tt>p `mplus` q</tt>, and <tt>p</tt> fails, then the computation
will be resumed with <tt>q</tt>. Note that <tt>q</tt> starts with the state that <tt>p</tt>
<em>started</em> with, not the state that <tt>p</tt> had reached when the exception
ocurred; <tt>p</tt> and <tt>q</tt> can be regarded as alternative computations. Although
I've called this exception handling, "backtracking" is arguably a more accurate
term.</p>
<p>We can use <tt>mplus</tt> and <tt>mzero</tt> to implement backtracking algorithms.
Consider the classic problem of finding a way to place 8 queens on an 8 by 8 chess board
such that no queen attacks another.</p>
<p>First the state</p>
<pre>type QState = ([Int], [Int], [Int])</pre>
<p>We use three lists to keep track of three sets: the set of occupied columns, the set of
occupied south-west diagonals and the set of occupied south-east diagonals. The south-west
diagonals are represented by the difference in the column and row number. The south-east
diagonals are represented by the sum of the row and column number. There are functions to
get and set each of these components of the state:</p>
<pre>getCols = STE( \(cols, swDiags, seDiags) ->
Just ((cols, swDiags, seDiags), cols) )
getSWDiags = STE( \(cols, swDiags, seDiags) ->
Just ((cols, swDiags, seDiags), swDiags) )
getSEDiags = STE( \(cols, swDiags, seDiags) ->
Just ((cols, swDiags, seDiags), seDiags) )
putCols c = STE( \(cols, swDiags, seDiags) ->
Just ((c:cols, swDiags, seDiags), ()) )
putSWDiags sw = STE( \(cols, swDiags, seDiags) ->
Just ((cols, sw:swDiags, seDiags), ()) )
putSEDiags se = STE( \(cols, swDiags, seDiags) ->
Just ((cols, swDiags, se:seDiags), ()) )</pre>
<p>We don't want to add a column or a diagonal to a set it is already in. To ensure that
we don't, we use the library routine guard defined by</p>
<pre>guard true = return()
guard false = mzero</pre>
<p>The following routines fail if the item being added to a set is already in the set:</p>
<pre>tryPutCol c =
do cols <- getCols
guard (c `notElem` cols)
putCols c
tryPutSWDiag sw =
do swDiags <- getSWDiags
guard (sw `notElem` swDiags)
putSWDiags sw
tryPutSEDiag se =
do seDiags <- getSEDiags
guard (se `notElem` seDiags)
putSEDiags se</pre>
<p>The next routine attempts to place a queen at a particular spot, failing if the new
queen would attack one that is already on the board.
(I'm assuming there is no other queen in the same row, so no check is
required to see if the row is occupied.)</p>
<pre>place r c =
do tryPutCol c
tryPutSWDiag (c-r)
tryPutSEDiag (c+r)</pre>
<p>The main algorithm to place queens in each of rows [0..r-1] of a board with colNum
columns is:</p>
<pre>queens r colNum =
if r == 0
then getCols -- Success, return list of columns
else tryEach [0..colNum-1] (\c ->
do place (r-1) c
queens (r-1) colNum )</pre>
<p>The tryEach "loop" is a control structure defined by</p>
<pre>tryEach :: MonadPlus m => [a] -> (a -> m b) -> m b
tryEach [] f = mzero
tryEach (h:t) f = f h `mplus` tryEach t f</pre>
<p>(We could also define <tt>tryEach</tt> in terms of the library function, <tt>msum</tt>,
which takes a list of monad members and combines them with <tt>mplus</tt>: <tt>tryEach xs
f = msum (map f xs)</tt> ).</p>
<p>To find an arrangement on an 8 by 8 chess board we write:</p>
<pre>applySTE (queens 8 8) ([], [], [])</pre>
<h2>Nondeterminism</h2>
<p>The StateTransEx monad provides a limited form of nondeterminism. Computations either
succeed or fail, but if they succeed, they succeed but once. For example in</p>
<pre> do (p `mplus` q)
r</pre>
<p>if <tt>p</tt> succeeds and then <tt>r</tt> then fails, <tt>q</tt> will not be given a
chance to "execute".</p>
<p>To get nondeterminism of the sort found in languages such as Icon, SNOBOL, and Prolog,
we need to allow a computation to succeed more than once. To create such a monad, we
replace the Maybe type constructor with the list type constructor:</p>
<p>The type is</p>
<pre>newtype StateTransMany s a = STM( s -> [(s, a)] )</pre>
<p>I leave it as an exercise to define <tt>>>=</tt>, <tt>return</tt>, <tt>mplus</tt>,
and <tt>mzero</tt> for this monad, and to change the queens example to generate all
solutions to the 8-queens problem.</p>
<h2>The IO Monad</h2>
<p>Haskell defines a monad called IO that is used to describe computations that interact
with the operating system -- in particular to perform input and output. For example, here
is how you can write a function to read a file, printing an error message if the file can
not be read</p>
<pre>
maybeReadFile :: String -> IO (Maybe String)
----
-- Read a file or print an error message and return Nothing.
maybeReadFile fileName = catch (do s <- readFile fileName
return (Just s))
(readErrHandler fileName)
readErrHandler :: String -> IOError -> IO (Maybe String)
readErrHandler fileName err =
do putStr ("Error reading file " ++ fileName
++ " " ++ show err ++ ".\n")
return Nothing</pre>
<p>You can see that the IO monad also supports exception handling, though with the
"catch" function, not the <tt>mplus</tt> operator. (<tt>mplus</tt> would be
inappropriate because changes to the world can not be undone!)</p>
<p>In Haskell the main program should be of type <tt>IO()</tt>.</p>
<p>It is often said that pure functional languages can't be used to write interactive
programs. At first glance the IO monad seems to contradict this idea. You can think
of it this way: When your functional program is executed, it does not interact with the
operating system, it merely computes an object of type<tt> IO(), </tt>which describes a
set of possible interactive computations. An interpreter interacts with the environment to
make one of these computations happen. The fact that Haskell is a lazy language is key to
this, for the set of computations for many applications is infinite, even if each
computation is finite. The choice of which computation is needed is governed by the input;
thanks to lazyness, only the computation that is actually required is computed.</p>
<h2>Lists as a Monad</h2>
<p>The list type constructor itself is a simple monad. Its definition is</p>
<pre>instance Monad [ ] where
xs >>= f = concat (map f xs)
return x = [x]
instance MonadPlus [ ] where
mzero = []
mplus = (++)</pre>
<p>(The notation<tt> [ ] </tt>in the first line of each instance declaration refers to the
list type constructor, i.e. the function that maps each type to its corresponding list
type.)</p>
<p>The definition of the list constructor as a monad allows one to write such things as</p>
<pre>do a <- [1,2,3]
b <- [3,4,5]
return (a+b)</pre>
<p>This evaluates to</p>
<pre>[4,5,6,5,6,7,6,7,8] ,</pre>
<p>just as does the list comprehension </p>
<pre>[ a+b | a <- [1,2,3],
b <- [3,4,5] ] </pre>
<h2>Monads and Software Engineering</h2>
<p>The key to engineering a large software project is to make changes easy..</p>
<p>Monads can be used to make functional programs far more adaptable. You need to
insert another processing step? Go right ahead, don't worry about plumbing the state. You
need another variable in the state? No problem, just change the underlying state and the
basic members of the monad. You need to output messages from your computation? No problem,
just change the monad to add an output string. You need to handle exceptions or
nondeterminism? No problem, just change the monad.</p>
<p>It might be said that Haskell with monads does not give you much that you won't find in
an imperative, nondeterministic language, with extensible, strong, but generic typing, and
a powerful applicative expression sublanguage. The problem is there is no such language in
common use. Monads make up for many of the drawbacks of Haskell relative to imperative
languages, but without giving up any of its strengths.</p>
<h2>More information</h2>
<p>Monads can be used for parsing. By using the remaining input as state, the StateTrans
monad can be used to write deterministic recursive-descent parsers. Better yet, the
StateTransEx and StateTransMany parsers can (respectively) be used to create backtracking
parsers and non-deterministic parsers (allowing ambiguous grammars). Monadic parsing
is the topic of the following paper:</p>
<blockquote>
<p>Graham Hutton and Erik Meijer, <em>Monadic parser combinators</em>, Technical Report
NOTTCS-TR-96-4, Department of Computer Science, University of Nottingham.</p>
</blockquote>
<p>Available on the Web at <a
href="http://www.cs.nott.ac.uk/Department/Techreports/96-4.html">http://www.cs.nott.ac.uk/Department/Techreports/96-4.html</a></p>
<p>I like to add an output for error and warning message, to the monad, and the
possibility of fatal errors that can not be recovered from. I also use a clearer
separation between parsing and lexical analysis than Hutton and Meijer. My own monadic
parsing combinators are available on the web at <a
href="http://www.engr.mun.ca/~theo/Misc/index.html#ParsingMonad">http://www.engr.mun.ca/~theo/Misc/index.html#ParsingMonad</a></p>
<p>The IO monad and the theory behind it is reported in</p>
<blockquote>
<p>Philip Wadler, <em>How to declare an imperative</em>, ACM Computing Surveys,
29(3):240--263, September 1997.</p>
</blockquote>
<p>Available on the Web at <a
href="http://www.cs.bell-labs.com/who/wadler/topics/monads.html">http://www.cs.bell-labs.com/who/wadler/topics/monads.html</a>.</p>
<p>An extension of the IO monad for use in systems with graphical user interfaces, is the
GUI monad that lets Haskell or Gofer interact with the tk library. The GUI monad, many
widgets and operators to compose widgets can be found in the TkGofer and TkHaskell
systems. See <a href="http://www.informatik.uni-ulm.de/pm/ftp/tkgofer.html">http://www.informatik.uni-ulm.de/pm/ftp/tkgofer.html</a>
and <a href="http://www.dcs.gla.ac.uk/~nww/TkHaskell/TkHaskell.html">http://www.dcs.gla.ac.uk/~nww/TkHaskell/TkHaskell.html</a>.</p>
<p>One of the best introductions to monads is in</p>
<blockquote>
<p>Philip Wadler, <em>Monads for functional programming</em>, in M. Broy, editor,
Marktoberdorf Summer School on Program Design Calculi, Springer Verlag, NATO ASI Series F:
Computer and systems sciences, Volume 118, August 1992. Also in J. Jeuring and E. Meijer,
editors, Advanced Functional Programming, Springer Verlag, LNCS 925, 1995. </p>
</blockquote>
<p>Available on the Web at <a
href="http://www.cs.bell-labs.com/who/wadler/topics/monads.html">http://www.cs.bell-labs.com/who/wadler/topics/monads.html</a>.</p>
<p>The first paper that I know of to deal with monads as a tool in functional
programming is</p>
<blockquote>
<p>Philip Wadler, <em>The essence of functional programming</em>. Invited talk, 19'th
Symposium on Principles of Programming Languages, ACM Press, Albuquerque, January 1992. </p>
</blockquote>
<p align="left">Available on the Web at <a
href="http://www.cs.bell-labs.com/who/wadler/topics/monads.html">http://www.cs.bell-labs.com/who/wadler/topics/monads.html</a>.</p>
<p align="left">There is a whole lot that could be said about the mathematical theory of
monads. It is my belief that most programmers don't need to know much of this theory to
reap the benefits of programming with monads. Philip Wadler's papers give an introduction
to the mathematics and pointers back to the earlier, more mathematical, literature.</p>
<h2>A Note for Gofer Programmers</h2>
<p>Almost everything in this tutorial applies equally to Gofer. However a few notations
are different. I think the following table completely summarizes the notational
differences assuming you are using Gofer 2.30 and the cc.prelude prelude.</p>
<table border="1">
<tr>
<td>Haskell</td>
<td> </td>
<td>Gofer</td>
</tr>
<tr>
<td><tt>>>=</tt></td>
<td>replace by</td>
<td><tt>`bind`</tt></td>
</tr>
<tr>
<td><tt>>></tt></td>
<td>no equivalent?</td>
<td> </td>
</tr>
<tr>
<td><tt>return</tt></td>
<td>replace by</td>
<td><tt>result</tt></td>
</tr>
<tr>
<td><tt>newtype</tt></td>
<td>replace by</td>
<td><tt>data</tt></td>
</tr>
<tr>
<td><tt>MonadPlus</tt></td>
<td>replace by</td>
<td><tt>Monad0</tt> and <tt>MonadPlus</tt></td>
</tr>
</table>
<p>Gofer supports both the "do" syntax (if Gofer is compiled with the right
options) and a "comprehension" syntax for monads explained next. In Gofer
the so-called "list" comprehension notation is an alternative to the
"do" notation, no matter whether you are using the list monad or any other
monad. You can write</p>
<pre>[a+b | a<-getX, b<-getY]</pre>
<p>which means the same as</p>
<pre>do a <- getX
b <- getY
return (a+b)</pre>
<p>The advantage of the "do" notation is that it doesn't force you to end with a
"<tt>return</tt>".</p>
<p>In Gofer, each instance of class Monad must be an instance of class Functor. To be in
class Functor a monad m must support a function called map of type (a -> b) -> (m a
-> m b). The map function lifts an ordinary function to a monad function. For monads,
it can always be defined by</p>
<pre>map f p = [f a | a <- p]</pre>
<p>In Gofer, use of the IO monad requires a special compilation option and inclusion of
the file iomonad.gs.</p>
<h2>A Note for Haskell 1.3 and 1.4 users</h2>
<p>In Haskell 1.3 and 1.4 <tt>mzero</tt> is called <tt>zero</tt> and <tt>mplus</tt>
is called <tt>++</tt>. There is a separate class MonadZero, declaring the zero. All the
classes are declared in the Prelude, so you do not need to import from Monad.</p>
<p>Haskell 1.4 supports the comprehension syntax for Monads (see the Gofer section).</p>
<h2>End Notes</h2>
<h3><a name="monoid">Monoids</a></h3>
<p>A monoid is an algebraic structure consisting of a set <em>S</em> and an operation *
with the following properties
<dl>
<dt>Closure:</dt>
<dd><em>x*y</em> is in <em>S</em>, if <em>x</em> and <em>y</em> are both in <em>S</em>.</dd>
<dt>Associativity:</dt>
<dd><em>x*(y*z) = (x*y)*z</em> for all <em>x</em>, <em>y</em>, and <em>z</em> in <em>S</em>.</dd>
<dt>Identity:</dt>
<dd>There is an element <em>e</em> in <em>S</em> such that <em>e*x= x*e = x</em> , for all <em>x</em>
in <em>S</em> .</dd>
</dl>
<p>Examples of monoids are the integers with multiplication as the operator, character
strings with catenation as the operator, functions with composition as the operator, and
programming langauge statements with sequential composition as the operator. Also any
group is a monoid and any monoid that has inverses is a group.</p>
</body>
</html>
--------------AA9F6594372313DC3CB49701--
------=_NextPart_000_007F_01C1A607.5224A640--