https://wiki.haskell.org/api.php?action=feedcontributions&user=Arkx&feedformat=atomHaskellWiki - User contributions [en]2020-11-29T08:02:54ZUser contributionsMediaWiki 1.27.4https://wiki.haskell.org/index.php?title=Monads_as_computation&diff=43769Monads as computation2011-12-30T11:12:21Z<p>Arkx: Fixed a broken link to ‘All About Monads’</p>
<hr />
<div>=== Motivation ===<br />
<br />
Programmers in general, and functional programmers in particular, are usually not so content to solve a problem in a fragile way by coding a solution directly. Quite often the best way to solve a problem is to design a domain-specific language in which the solution to one's problem is easily expressed. Doing this generally ensures that a wide class of similar problems can be attacked using the same code. That way, you get code which is resistant to damage in the form of changes to design requirements.<br />
<br />
Better still, we'd like to embed those domain specific languages into the language which we wrote them in, so that they can be used together, and so we get benefits from the language we're working in without so much extra work. So we write combinator libraries which are essentially libraries of code whose API's are sufficiently powerful that using the library is like programming in a small language embedded within the existing one.<br />
<br />
Such a library will have some representation of primitive computations, and some ways to glue those computations together into more complex ones. A parsing library might define primitive parsers for parsing single characters, and then combining functions for concatenating parsers or selecting between them. A drawing library might define some basic drawing operations, and then various means of combining drawings into larger ones (on top, beside, above, etc.).<br />
<br />
In this manner, the user of the combinator library builds up the computation they want, piecing together smaller parts into larger ones.<br />
<br />
As far as programming is concerned, a [[monad]] is just a particular style of combinator library. That is, one which supports a few basic means of combination.<br />
<br />
The reason for making this abstraction is so that all the libraries which make use of those means of combination can then share a library of combining functions built up from the primitive ones they are required to support.<br />
<br />
Specifically, by defining an instance of Monad for your library when appropriate, you automatically get the benefit of the functions in the [http://www.haskell.org/ghc/docs/latest/html/libraries/base/Control-Monad.html Control.Monad library] (as well as a few others, like [http://www.haskell.org/ghc/docs/latest/html/libraries/base/Data-Traversable.html Data.Traversable]). This includes things like for-each loops (forM/mapM), ways to turn pure functions into combiners (liftM2, etc.), as well as other control structures which you get for free just for making your library an instance of Monad.<br />
<br />
=== The parts of a monad ===<br />
<br />
There are of course, other kinds of combinator library, but monads arise fairly naturally from a few basic premises.<br />
<br />
* Monadic computations have results. This is reflected in the types. Given a monad M, a value of type <code>M t</code> is a computation resulting in a value of type <code>t</code>. It's important to realise that this is typically just some data structure. It will be interpreted as a computation and "run" in a way which is dependent on the given library.<br />
* For any value, there is a computation which "does nothing", and produces that result. This is given by defining the function <code>return</code> for the given monad.<haskell><br />
return :: (Monad m) => a -> m a<br />
</haskell><br />
* Given a pair of computations <hask>x</hask> and <hask>y</hask>, one can form the computation <hask>x >> y</hask>, which intuitively "runs" the computation <hask>x</hask>, throws away its result, then runs <hask>y</hask> returning its result.<haskell><br />
(>>) :: (Monad m) => m a -> m b -> m b<br />
</haskell><br />
* Further, we're allowed to use the result of the first computation to decide "what to do next", rather than just throwing it away. This idea is embodied by the operation <hask>(>>=)</hask>, called 'bind'. If <hask>x</hask> is a computation, and <hask>f</hask> is a function from potential results of that computation to further computations to be performed, then <hask>x >>= f</hask> is a computation which runs <hask>x</hask>, then applies <hask>f</hask> to its result, getting a computation which it then runs. The result of this latter computation is the result of the combined one.<haskell><br />
(>>=) :: (Monad m) => m a -> (a -> m b) -> m b<br />
</haskell><br />
<br />
In fact, once we have bind, we can always define <hask>(>>)</hask> as:<br />
<haskell><br />
x >> y = x >>= (\_ -> y)<br />
</haskell><br />
<br />
It's important to realise that both what it means to "run" a computation, and what "then" means in the above are both <em>up to the monad in question</em> (subject to a few simple constraints to be discussed later). This point will become clearer as one sees more and more examples.<br />
<br />
=== A few examples ===<br />
<br />
On top of <hask>return</hask> and <hask>(>>=)</hask>, any given monad will typically define a bunch of primitive computations to get the user of the library started. The <hask>IO</hask> monad, for instance, has a large number of I/O operations such as <hask>getLine :: IO String</hask> and <hask>putStrLn :: String -> IO ()</hask>. The program: <haskell><br />
main :: IO ()<br />
main = getLine >>= putStrLn<br />
</haskell> gets a line of text from the user, and then prints it back out.<br />
For a slightly more complicated example, the program: <haskell><br />
main :: IO ()<br />
main = putStrLn "Enter a line of text:"<br />
>> getLine >>= \x -> putStrLn (reverse x)<br />
</haskell> prompts the user for a line of text, gets the line of text from the user, and then prints it back out in reverse.<br />
<br />
A parsing monad might define <hask>char :: Char -> Parser Char</hask>, for constructing a parser which succeeds if the input string matches the given character. As a very simple example without getting into the details of parsing monads, the parser: <haskell><br />
cat = char 'c' >> char 'a' >> char 't' >> return "It's a cat."<br />
</haskell> would try to match the string "cat", and if the parse succeeded, would return the string <hask>"It's a cat."</hask>.<br />
<br />
=== Do notation ===<br />
<br />
Because computations are typically going to be built up from long chains of <hask>(>>)</hask> and <hask>(>>=)</hask>, in Haskell, we have some syntax-sugar, called do-notation.<br />
<br />
The do-notation allows us to write our second IO program above as:<br />
<haskell><br />
main = do putStrLn "Enter a line of text:"<br />
x <- getLine<br />
putStrLn (reverse x)<br />
</haskell><br />
<br />
The basic mechanical translation for the do-notation is as follows:<br />
<haskell><br />
do { x } = x<br />
<br />
do { x ; <stmts> }<br />
= x >> do { <stmts> }<br />
<br />
do { v <- x ; <stmts> }<br />
= x >>= \v -> do { <stmts> }<br />
<br />
do { let <decls> ; <stmts> }<br />
= let <decls> in do { <stmts> }<br />
</haskell><br />
<br />
This gives monadic computations a bit of an imperative feel, but it's important to remember that the monad in question gets to decide what the combination means, and so some unusual forms of control flow might actually occur. In some monads (like parsers, or the list monad), "backtracking" may occur, and in others, even more exotic forms of control might show up (for instance, first-class continuations, or some form of parallelism).<br />
<br />
=== The monad laws ===<br />
<br />
However, in order to maintain some semblance of sanity, we agree to make the monads we define follow some basic rules. I'll show the three rules both in terms of <hask>return</hask> and <hask>(>>=)</hask> and do-notation, and try to give some feel of what they really mean.<br />
<br />
<haskell><br />
1. return v >>= f = f v<br />
<br />
2. x >>= return = x<br />
<br />
3. (x >>= f) >>= g = x >>= (\v -> f v >>= g)<br />
</haskell><br />
<br />
Rules 1 and 2 basically give one the sense that <hask>return v</hask> "does nothing" and results in <hask>v</hask>.<br />
<br />
Rule 3 puts a bit of a constraint on what "then" is supposed to mean. It is perhaps easier at first to look at what it means for <hask>(>>)</hask>:<br />
<haskell><br />
(x >> y) >> z = x >> (y >> z)<br />
</haskell><br />
This corresponds nicely with our usual reading of <hask>(>>)</hask> as "then":<br />
<br />
putting on your tie, <strong>then</strong> (putting on your socks <strong>then</strong> putting on your shoes)<br />
<br />
is the same thing as<br />
<br />
(putting on your tie <strong>then</strong> putting on your socks) <strong>then</strong> putting on your shoes.<br />
<br />
To get a bit of a different perspective on what the laws mean, let's see what they look like in do-notation:<br />
<br />
<haskell><br />
1. do { w <- return v; f w }<br />
= do { f v }<br />
<br />
2. do { v <- x; return v }<br />
= do { x }<br />
</haskell><br />
<br />
These two are again consistent with the idea that return produces a computation that has no "side-effects", and just returns its parameter.<br />
<br />
<haskell><br />
3. do w <- do v <- x<br />
f v<br />
g w<br />
<br />
= do v <- x<br />
w <- f v<br />
g w<br />
</haskell><br />
<br />
This is more interesting. It's telling us that asking for the result of a compound computation in the midst of a do-block will result in exactly the same thing as if that compound computation had been spliced in directly, and gives us a valid way to refactor code written in any monad. We're allowed to abstract a chunk of code out from the middle of a do-block and give it a name without worrying about whether we've changed the meaning of the code.<br />
<br />
=== The whole point ===<br />
<br />
This is all very good, but apart from defining a pretty syntax for a certain kind of combinator library, the stuff we've done so far is fairly inessential. What's the point of recognising something as a monad?<br />
<br />
The point, as I alluded to in the introduction, is that we can then write code which works for all monads, and have a whole library of code which is made available to us just for recognising that the library we're writing happens to be a monad. Since we have only return and bind to work with, this sort of code will serve to chain computations together in some methodical way. That is to say, it will consist of control structures.<br />
<br />
All the examples I'll give are already defined in the [http://www.haskell.org/ghc/docs/latest/html/libraries/base/Control-Monad.html Control.Monad] library, along with many more.<br />
<br />
The first example of such a control structure we'll look at is called <hask>sequence</hask>. It's a function which takes a list of computations of the same type, and builds from them a computation which will run each in turn and produce a list of the results:<br />
<br />
<haskell><br />
sequence :: (Monad m) => [m a] -> m [a]<br />
sequence [] = return []<br />
sequence (x:xs) = do v <- x<br />
vs <- sequence xs<br />
return (v:vs)<br />
</haskell><br />
or, without the do-notation:<br />
<haskell><br />
sequence :: (Monad m) => [m a] -> m [a]<br />
sequence [] = return []<br />
sequence (x:xs) = x >>= \v -> sequence xs >>= \vs -> return (v:vs)<br />
</haskell><br />
(one can start to see why do-notation might be desirable!)<br />
<br />
In a parsing monad, we might pass it a list of parsers, and get back a parser which parses its input using each in turn. In the IO monad, a simple example might be the following:<br />
<haskell><br />
main = sequence [getLine, getLine] >>= print<br />
</haskell><br />
which gets two lines of text from the user, and then prints the list.<br />
<br />
Since lists are lazy in Haskell, this gives us a sort of primordial loop from which most other kinds of loops can be built.<br />
<br />
What is a for-each loop really? It's something which performs some action based on each element of a list. So we might imagine a function with the type:<br />
<haskell><br />
forM :: (Monad m) => [a] -> (a -> m b) -> m [b]<br />
</haskell><br />
(as an added bonus, we'll have it collect the results of each iteration).<br />
<br />
We can write this with sequence and map:<br />
<haskell><br />
forM xs f = sequence (map f xs)<br />
</haskell><br />
we apply the function to each element of the list to construct the action for that iteration, and then sequence the actions together into a single computation.<br />
<br />
For example:<br />
<haskell><br />
main = forM [1..10] $ \x -> do<br />
putStr "Looping: "<br />
print x<br />
</haskell><br />
<br />
Since in this, and many other cases, the loop body doesn't produce a particularly interesting result, there are variants of <hask>sequence</hask> and <hask>forM</hask> called <hask>sequence_</hask> and <hask>forM_</hask>, which simply throw the results away as they run each of the actions.<br />
<br />
<haskell><br />
sequence_ :: (Monad m) => [m a] -> m ()<br />
sequence_ [] = return ()<br />
sequence_ (x:xs) = x >> sequence_ xs<br />
<br />
forM_ :: (Monad m) => [a] -> (a -> m b) -> m ()<br />
forM_ xs f = sequence_ (map f xs)<br />
</haskell><br />
<br />
Sometimes we only want a computation to happen when a given condition is true. For this, we can write the following:<br />
<haskell><br />
when :: (Monad m) => Bool -> m () -> m ()<br />
when p x = if p then x else return ()<br />
</haskell><br />
Remember that <hask>return ()</hask> is a no-op, so running this computation will run x when the condition is true, and will do nothing at all when the condition fails.<br />
<br />
Another extremely common thing to do is to construct a computation which performs another computation and then applies a function to the result. This can be accomplished by using the <hask>liftM</hask> function:<br />
<haskell><br />
liftM :: (Monad m) => (a -> b) -> m a -> m b<br />
liftM f x = do v <- x<br />
return (f v)<br />
</haskell><br />
Or:<br />
<haskell><br />
liftM :: (Monad m) => (a -> b) -> m a -> m b<br />
liftM f x = return . f =<< x<br />
</haskell><br />
where <hask>(=<<)</hask> is just bind with its parameters flipped.<br />
<br />
This is also generalised by <hask>liftM2, liftM3, ...</hask> to running more than one computation before applying a function to the results:<br />
<haskell><br />
liftM2 :: (Monad m) => (a -> b -> c) -> m a -> m b -> m c<br />
liftM2 f x y = do v <- x<br />
w <- y<br />
return (f v w)<br />
</haskell><br />
<br />
It's possible to rewrite sequence in terms of liftM2, return, and a fold over the list:<br />
<haskell><br />
sequence :: (Monad m) => [m a] -> m [a]<br />
sequence xs = foldr (liftM2 (:)) (return []) xs<br />
<br />
sequence_ :: (Monad m) => [m a] -> m ()<br />
sequence_ xs = foldr (>>) (return ()) xs<br />
</haskell><br />
<br />
Anyway, these are just a few of the simpler examples to give a taste of what sorts of control structures you get for free by defining a combinator library as a monad.<br />
<br />
=== Some final notes ===<br />
<br />
It's a common misconception that Haskell uses a monad for I/O out of necessity. Really, it could use any sort of combinator library to describe and combine I/O actions. It just happens that the most obvious way to formulate a library to describe I/O actions ends up being a monad. So we define it as such so as to be able to share all these control structures with other monadic libraries.<br />
<br />
That's really the only reason why we ever define anything as a monad -- the abstraction allows us to make use of a bunch of shared code for free without writing it out over and over again (or worse yet, failing to abstract it at all).<br />
<br />
At this point, you might want to look at some more examples of monads. One place which is a decent starting point for that is Part II of the [http://www.haskell.org/haskellwiki/All_About_Monads#Introduction_2 "All About Monads" tutorial]. You might also have a look at the [http://www.haskell.org/ghc/docs/latest/html/libraries/index.html Hierarchical Libraries Documentation] for the libraries under Control.Monad.<br />
<br />
-- [[User:CaleGibbard|CaleGibbard]]<br />
<br />
==See also==<br />
<br />
* [[Monad]]<br />
* [[Monads as containers]]<br />
<br />
[[Category:Tutorials]] [[Category:Monad]]</div>Arkxhttps://wiki.haskell.org/index.php?title=Monads_as_containers&diff=43768Monads as containers2011-12-30T10:56:11Z<p>Arkx: Fixed a broken link to ‘All About Monads’</p>
<hr />
<div>''There now exists a translation of this article into [http://community.livejournal.com/ru_lambda/12467.html Russian]!''<br />
<br />
----<br />
<br />
A [[monad]] is a container type together with a few methods defined on it.<br />
Monads model different kinds of computations.<br />
<br />
Like Haskell lists, all the elements which a monadic container holds at any<br />
one time must be the same type (it is homogeneous).<br />
<br />
There are a few ways to choose the basic set of functions that one can perform<br />
on these containers to be able to define a monad. Haskell generally uses a<br />
pair of functions called return and bind <code>(>>=)</code>, but it is more natural<br />
sometimes to begin with map (<code>fmap</code>), return and join, as these are simpler<br />
to understand at first. We can later define bind in terms of these.<br />
<br />
The first of these three, generally called ''map'', (but called <code>fmap</code> in<br />
Haskell 98) actually comes from the definition of a ''functor''. We can think<br />
of a functor as a type of container where we are permitted to apply a single<br />
function to every object in the container.<br />
<br />
That is, if <code style="color:darkgreen">f</code> is a functor, and we are given a function of type <code>(<span style="color:firebrick">a</span> -> <span style="color:mediumblue">b</span>)</code>,<br />
and a container of type <code>(<span style="color:darkgreen">f</span> <span style="color:firebrick">a</span>)</code>, we can get a new container of type <code>(<span style="color:darkgreen">f</span> <span style="color:mediumblue">b</span>)</code>.<br />
<br />
This is expressed in the type of <code>fmap</code>:<br />
<haskell><br />
fmap :: (Functor f) => (a -> b) -> f a -> f b<br />
</haskell><br />
''If you will give me a blueberry for each apple I give you'' <code>(<span style="color:firebrick">a</span> -> <span style="color:mediumblue">b</span>)</code>'', and I have a box of apples ''<code>(<span style="color:darkgreen">f</span> <span style="color:firebrick">a</span>)</code>'', then I can get a box of blueberries ''<code>(<span style="color:darkgreen">f</span> <span style="color:mediumblue">b</span>)</code>''.''<br />
<br />
Every monad is a functor.<br />
<br />
The second method, ''return'', is specific to monads. If <code style="color:indigo">m</code> is a monad, then<br />
return takes an element of type <code style="color:firebrick">a</code>, and gives a container of type <code>(<span style="color:indigo">m</span> <span style="color:firebrick">a</span>)</code><br />
with that element in it. So, its type in Haskell is<br />
<haskell><br />
return :: (Monad m) => a -> m a<br />
</haskell><br />
''If I have an apple'' <code>(<span style="color:firebrick">a</span>)</code> ''then I can put it in a box'' <code>(<span style="color:indigo">m</span> <span style="color:firebrick">a</span>)</code>''.''<br />
<br />
The third method, ''join'', also specific to monads, takes a container of<br />
containers <code><span style="color:indigo">m</span> (<span style="color:indigo">m</span> <span style="color:firebrick">a</span>)</code>, and combines them into one <code><span style="color:indigo">m</span> <span style="color:firebrick">a</span></code> in some sensible<br />
fashion. Its Haskell type is<br />
<haskell><br />
join :: (Monad m) => m (m a) -> m a<br />
</haskell><br />
''If I have a box of boxes of apples'' <code>(<span style="color:indigo">m</span> (<span style="color:indigo">m</span> <span style="color:firebrick">a</span>))</code> ''then I can take the apples from each, and put them in a new box'' <code>(<span style="color:indigo">m</span> <span style="color:firebrick">a</span>)</code>''.''<br />
<br />
From these, we can construct an important operation called ''bind'' or<br />
''extend'', which is commonly given the symbol <code>(>>=)</code>. When you define your<br />
own monad in Haskell, it will expect you to define just return and bind. It<br />
turns out that mapping and joining come for free from these two. Although only<br />
return and bind are needed to define a monad, it is usually simpler to think<br />
about map, return, and join first, and then get bind from these, as map and<br />
join are in general simpler than bind.<br />
<br />
What bind does is to take a container of type <code>(<span style="color:indigo">m</span> <span style="color:firebrick">a</span>)</code> and a function of type<br />
<code>(<span style="color:firebrick">a</span> -> <span style="color:indigo">m</span> <span style="color:mediumblue">b</span>)</code>. It first maps the function over the container, (which would give <br />
an <code><span style="color:indigo">m</span> (<span style="color:indigo">m</span> <span style="color:mediumblue">b</span>)</code>) and then applies join to the result to get a container of type<br />
<code>(<span style="color:indigo">m</span> <span style="color:mediumblue">b</span>)</code>. Its type and definition in Haskell is then<br />
<haskell><br />
(>>=) :: (Monad m) => m a -> (a -> m b) -> m b<br />
xs >>= f = join (fmap f xs) <br />
-- how we would get bind (>>=) in Haskell if it were join and fmap<br />
-- that were chosen to be primitive<br />
</haskell><br />
''If I have a box of apples'' <code>(<span style="color:indigo">m</span> <span style="color:firebrick">a</span>)</code> ''and for each apple, you will give me a box of blueberries'' <code>(<span style="color:firebrick">a</span> -> <span style="color:indigo">m</span> <span style="color:mediumblue">b</span>)</code> ''then I can get a box with all the blueberries together'' <code>(<span style="color:indigo">m</span> <span style="color:mediumblue">b</span>)</code>''.''<br />
<br />
Note that for a given container type, there might be more than one way to<br />
define these basic operations (though for obvious reasons, Haskell will only<br />
permit one instance of the Monad class per actual type). [Technical side note:<br />
The functions return and bind need to satisfy<br />
[[Monad_laws | a few laws]] in order to<br />
make a monad, but if you define them in a sensible way given what they are<br />
supposed to do, the laws will work out. The laws are only a formal way to<br />
give the informal description of the meanings of return and bind I have here.]<br />
<br />
It would be good to have a concrete example of a monad at this point, as these<br />
functions are not very useful if we cannot find any examples of a type to<br />
apply them to.<br />
<br />
Lists are most likely the simplest, most illustrative example. Here, <code>fmap</code><br />
is just the usual <code>map</code>, <code>return</code> is just <code>(\x -> [x])</code> and <code>join</code> is <code>concat</code>.<br />
<br />
<haskell><br />
instance Monad [] where<br />
--return :: a -> [a]<br />
return x = [x] -- make a list containing the one element given<br />
<br />
--(>>=) :: [a] -> (a -> [b]) -> [b]<br />
xs >>= f = concat (map f xs) <br />
-- collect up all the results of f (which are lists)<br />
-- and combine them into a new list<br />
</haskell><br />
<br />
The list monad, in some sense, models computations which could return any<br />
number of values. Bind pumps values in, and catches all the values output.<br />
Such computations are known in computer science as ''nondeterministic''.<br />
That is, a list [x,y,z] represents a value which is all of the values x, y,<br />
and z at once.<br />
<br />
A couple examples of using this definition of bind:<br />
<haskell><br />
[10,20,30] >>= \x -> [x, x+1] <br />
-- a function which takes a number and gives both it and its<br />
-- successor at once<br />
= [10,11,20,21,30,31]<br />
<br />
[10,20,30] >>= \x -> [x, x+1] >>= \y -> if y > 20 then [] else [y,y]<br />
= [10,10,11,11,20,20]<br />
</haskell><br />
<br />
And a simple fractal, exploiting the fact that lists are ordered:<br />
<haskell><br />
f x | x == '#' = "# #"<br />
| otherwise = " "<br />
<br />
"#" >>= f >>= f >>= f >>= f<br />
= "# # # # # # # # # # # # # # # #"<br />
</haskell><br />
<br />
You might notice a similarity here between bind and function application or<br />
composition, and this is no coincidence. The reason that bind is so important<br />
is that it serves to chain computations on monadic containers together.<br />
<br />
You might be interested in how, given just bind and return, we can get back<br />
to map and join.<br />
<br />
Mapping is equivalent to binding to a function which only returns containers<br />
with a single value in them -- the value that we get from the function of<br />
type <code>(a -> b)</code> which we are handed.<br />
<br />
The function that does this for any monad in Haskell is called <code>liftM</code> -- it<br />
can be written in terms of return and bind as follows:<br />
<haskell><br />
liftM :: (Monad m) => (a -> b) -> m a -> m b<br />
liftM f xs = xs >>= (return . f)<br />
-- take a container full of a's, to each, apply f,<br />
-- put the resulting value of type b in a new container,<br />
-- and then join all the containers together.<br />
</haskell><br />
<br />
Joining is equivalent to binding a container with the identity map. This is<br />
indeed still called <code>join</code> in Haskell:<br />
<haskell><br />
join :: (Monad m) => m (m a) -> m a<br />
join xss = xss >>= id<br />
</haskell><br />
<br />
It is common when constructing monadic computations that one ends up with a<br />
large chain of binds and lambdas. For this reason, some syntactic sugar called<br />
"do notation" was created to simplify this process, and at the same time, make<br />
the computations look somewhat like imperative programs.<br />
<br />
Note that in what follows, the syntax emphasizes the fact that the list monad<br />
models nondeterminism: the code <code>y <- xs</code> can be thought of as <code>y</code> taking on<br />
all the values in the list <code>xs</code> at once.<br />
<br />
The above (perhaps somewhat silly) list computations could be written:<br />
<haskell><br />
do x <- [10,20,30]<br />
[x, x+1]<br />
</haskell><br />
and,<br />
<haskell><br />
do x <- [10,20,30]<br />
y <- [x, x+1]<br />
if y > 20 then [] else [y,y]<br />
</haskell><br />
<br />
The code for liftM could be written:<br />
<haskell><br />
liftM f xs = do a <- xs<br />
return (f a)<br />
</haskell><br />
<br />
----<br />
<br />
If you understood the above, then you have a good start on understanding<br />
monads in Haskell. Check out Maybe (containers with at most one thing in them,<br />
modelling computations that might not return a value) and State (modelling<br />
computations that carry around a state parameter using an odd sort of<br />
container described below), and you'll start getting the picture as to how<br />
things work.<br />
<br />
A good exercise is to figure out a definition of bind and return (or fmap,<br />
join and return) which make the following tree type a monad. Just keep in<br />
mind what they are supposed to do.<br />
<haskell><br />
data Tree a = Leaf a | Branch (Tree a) (Tree a)<br />
</haskell><br />
<br />
For more good examples of monads, and lots of explanation see<br />
[http://www.haskell.org/haskellwiki/All_About_Monads All About Monads] which has a catalogue of the commonest<br />
ones, more explanation as to why you might be interested in monads, and<br />
information about how they work.<br />
<br />
----<br />
<br />
The question that many people will be asking at this point is "What does this<br />
all have to do with IO?".<br />
<br />
Well, in Haskell, IO is a monad. How does this mesh with the notion of a<br />
container?<br />
<br />
Consider <code>getChar :: IO Char</code> -- that is, an IO container with a character<br />
value in it. The exact character that the container holds is determined when<br />
the program runs by which keys the user presses. Trying to get the character<br />
out of the box will cause a side effect: the program stops and waits for the<br />
user to press a key. This is generally true of IO values - when you get a<br />
value out with bind, side effects can occur. Many IO containers don't<br />
actually contain interesting values. For example,<br />
<haskell><br />
putStrLn "Hello, World!" :: IO ()<br />
</haskell><br />
That is, the value returned by <code>putStrLn "Hello, World!"</code> is an IO container<br />
filled with a value of type <code>()</code>, a not so interesting type. However, when<br />
you pull this value out during a bind operation, the string <code>Hello, World!</code><br />
is printed on the screen. So another way to think about values of type <code>IO t</code><br />
is as computations which when executed, may have side effects before<br />
returning a value of type t.<br />
<br />
One thing that you might notice as well, is that there is no ordinary Haskell<br />
function you can call (at least not in standard Haskell) to actually get a<br />
value out of an IO container/computation, other than bind, which puts it right<br />
back in. Such a function of type <code>IO a -> a</code> would be very unsafe in the pure<br />
Haskell world, because the value produced could be different each time it was<br />
called, and the IO computation could have side effects, and there would be no<br />
way to control when it was executed (Haskell is lazy after all). So how do IO<br />
actions ever get run? The IO action called <code>main</code> runs when the program is<br />
executed. It can make use of other IO actions in the process, and everything<br />
starts from there.<br />
<br />
When doing IO, a handy special form of bind when you just want the side<br />
effects and don't care about the values returned by the container on the left<br />
is this:<br />
<haskell><br />
(>>) :: Monad m => m a -> m b -> m b<br />
m >> k = m >>= \_ -> k<br />
</haskell><br />
<br />
An example of doing some IO in do notation:<br />
<haskell><br />
main = do putStrLn "Hello, what is your name?"<br />
name <- getLine<br />
putStrLn ("Hello " ++ name ++ "!")<br />
</haskell><br />
<br />
or in terms of bind, making use of the special form:<br />
<haskell><br />
main = putStrLn "Hello, what is your name?" >><br />
getLine >>= \name -><br />
putStrLn ("Hello " ++ name ++ "!")<br />
</haskell><br />
<br />
or, very primitive, without the special form for bind:<br />
<haskell><br />
main = putStrLn "Hello, what is your name?" >>= \x -><br />
getLine >>= \name -><br />
putStrLn ("Hello " ++ name ++ "!")<br />
</haskell><br />
<br />
----<br />
<br />
Another good example of a monad which perhaps isn't obviously a container at<br />
first, is the [[Reader monad]]. This monad basically consists<br />
of functions from a particular type: <code>((->) e)</code>, which might be written<br />
<code>(e ->)</code> if that were supported syntax. These can be viewed as containers<br />
indexed by values of type <code>e</code>, having one spot for each and every value of<br />
type <code>e</code>. The primitive operations on them follow naturally from thinking<br />
this way.<br />
<br />
The [[Reader monad]] models computations which read from (depend on) a shared<br />
environment. To clear up the correspondence, the type of the environment is<br />
the index type on our indexed containers.<br />
<br />
<haskell><br />
type Reader e = (->) e -- our monad<br />
</haskell><br />
<br />
Return simply produces the container having a given value at every spot.<br />
<haskell><br />
return :: a -> (Reader e a)<br />
return x = (\k -> x)<br />
</haskell><br />
<br />
Mapping a function over such a container turns out to be nothing more than<br />
what composition does.<br />
<br />
<haskell><br />
fmap :: (a -> b) -> Reader e a -> Reader e b<br />
= (a -> b) -> (e -> a) -> (e -> b)<br />
-- by definition, (Reader a b) = (a -> b)<br />
<br />
fmap f xs = f . xs<br />
</haskell><br />
<br />
How about join? Well, let's have a look at the types.<br />
<haskell><br />
join :: (Reader e) (Reader e a) -> (Reader e a)<br />
= (e -> e -> a) -> (e -> a) -- by definition of (Reader a)<br />
</haskell><br />
There's only one thing the function of type <code>(e -> a)</code> constructed could<br />
really be doing:<br />
<br />
<haskell><br />
join xss = (\k -> xss k k)<br />
</haskell><br />
<br />
From the container perspective, we are taking an indexed container of indexed<br />
containers and producing a new one which at index <code>k</code>, has the value at index<br />
<code>k</code> in the container at index <code>k</code>.<br />
<br />
So we can derive what we want bind to do based on this:<br />
<haskell><br />
(>>=) :: (Reader e a) -> (a -> Reader e b) -> (Reader e b)<br />
= (e -> a) -> (a -> (e -> b)) -> (e -> b) -- by definition<br />
<br />
xs >>= f = join (fmap f xs)<br />
= join (f . xs)<br />
= (\k -> (f . xs) k k)<br />
= (\k -> f (xs k) k)<br />
</haskell><br />
<br />
Which is exactly what you'll find in other definitions of the Reader monad.<br />
What is it doing? Well, it's taking a container <code>xs</code>, and a function <code>f</code> from<br />
the values in it to new containers, and producing a new container which at<br />
index <code>k</code>, holds the result of looking up the value at <code>k</code> in <code>xs</code>, and then<br />
applying <code>f</code> to it to get a new container, and finally looking up the value<br />
in that container at <code>k</code>.<br />
<br />
The [[Monads as computation]] perspective makes the purpose of such a monad perhaps<br />
more obvious: bind is taking a computation which may read from the environment<br />
before producing a value of type <code>a</code>, and a function from values of type <code>a</code><br />
to computations which may read from the environment before returning a value<br />
of type <code>b</code>, and composing these together, to get a computation which might<br />
read from the (shared) environment, before returning a value of type <code>b</code>.<br />
<br />
----<br />
<br />
How about the [[State monad]]? Although I'll admit that<br />
with State and IO in particular, it is generally more natural to take the<br />
view of [[Monads as computation]], it is good to see that the container analogy<br />
doesn't break down. The state monad is a particular refinement of the reader<br />
monad discussed above.<br />
<br />
I won't go into huge detail about the state monad here, so if you don't<br />
already know what it's for, what follows may seem a bit unnatural. It's<br />
perhaps better taken as a secondary way to look at the structure.<br />
<br />
For reference to the analogy, a value of type <code>(State s a)</code> is like a<br />
container indexed by values of type <code>s</code>, and at each index, it has a value of<br />
type <code>a</code> and another, new value of type <code>s</code>. The function <code>runState</code> does<br />
this "lookup".<br />
<br />
<haskell><br />
newtype State s a = State { runState :: (s -> (a,s)) }<br />
</haskell><br />
<br />
What does return do? It gives a <code>State</code> container with the given element at<br />
every index, and with the "address" (a.k.a. state parameter) unchanged.<br />
<haskell><br />
return :: a -> State s a<br />
return x = State (\s -> (x,s))<br />
</haskell><br />
<br />
Mapping does the natural thing, applying a function to each of the values of<br />
type <code>a</code>, throughout the structure.<br />
<haskell><br />
fmap :: (a -> b) -> (State s a) -> (State s b)<br />
fmap f (State m) = State (onVal f . m)<br />
where onVal f (x, s) = (f x, s)<br />
</haskell><br />
<br />
Joining needs a bit more thought. We want to take a value of type<br />
<code>(State s (State s a))</code> and turn it into a <code>(State s a)</code> in a natural way.<br />
This is essentially removal of indirection. We take the new address and new<br />
box that we get from looking up a given address in the box, and we do another<br />
lookup -- note that this is almost the same as what we did with the reader<br />
monad, only we use the new address that we get at the location, rather than<br />
the same address as for the first lookup.<br />
<br />
So we get:<br />
<haskell><br />
join :: (State s (State s a)) -> (State s a)<br />
join xss = State (\s -> uncurry runState (runState xss s))<br />
</haskell><br />
<br />
----<br />
<br />
I hope that the above was a reasonably clear introduction to what monads are<br />
about. Feel free to [[Talk:Monads as containers|make criticisms and ask questions]].<br />
<br />
- [[User:CaleGibbard|CaleGibbard]]<br />
<br />
==See also==<br />
<br />
* [[Monad]]<br />
* [[Monads as computation]]<br />
<br />
<br />
[[Category:Tutorials]] [[Category:Monad]]</div>Arkx