43649e54f12faafe44d3d8c78544bebe2edef92e
[haskell-report.git] / report / libs / Control-Monad.tex
1 \haddockmoduleheading{Control.Monad}
2 \label{module:Control.Monad}
3 \haddockbeginheader
4 {\haddockverb\begin{verbatim}
5 module Control.Monad (
6 Functor(fmap), Monad((>>=), (>>), return, fail), MonadPlus(mzero, mplus),
7 mapM, mapM_, forM, forM_, sequence, sequence_, (=<<), (>=>), (<=<),
8 forever, void, join, msum, filterM, mapAndUnzipM, zipWithM,
9 zipWithM_, foldM, foldM_, replicateM, replicateM_, guard, when,
10 unless, liftM, liftM2, liftM3, liftM4, liftM5, ap
11 ) where\end{verbatim}}
12 \haddockendheader
13
14 The \haddocktt{Control.Monad} module provide the \haddockid{Functor}, \haddockid{Monad} and
15 \haddockid{MonadPlus} classes, together with some useful operations on monads.
16 \par
17
18 \section{Functor and monad classes
19 }
20 \begin{haddockdesc}
21 \item[\begin{tabular}{@{}l}
22 class\ Functor\ f\ where
23 \end{tabular}]\haddockbegindoc
24 The \haddockid{Functor} class is used for types that can be mapped over.
25 Instances of \haddockid{Functor} should satisfy the following laws:
26 \par
27 \begin{quote}
28 {\haddockverb\begin{verbatim}
29 fmap id == id
30 fmap (f . g) == fmap f . fmap g
31 \end{verbatim}}
32 \end{quote}
33 The instances of \haddockid{Functor} for lists, \haddocktt{Data.Maybe.Maybe} and \haddocktt{System.IO.IO}
34 defined in the \haddocktt{Prelude} satisfy these laws.
35 \par
36
37 \haddockpremethods{}\textbf{Methods}
38 \begin{haddockdesc}
39 \item[\begin{tabular}{@{}l}
40 fmap\ ::\ (a\ ->\ b)\ ->\ f\ a\ ->\ f\ b
41 \end{tabular}]
42 \end{haddockdesc}
43 \end{haddockdesc}
44 \begin{haddockdesc}
45 \item[\begin{tabular}{@{}l}
46 instance\ Functor\ {\char 91}{\char 93}\\instance\ Functor\ IO\\instance\ Functor\ ReadP\\instance\ Functor\ Maybe\\instance\ Ix\ i\ =>\ Functor\ (Array\ i)
47 \end{tabular}]
48 \end{haddockdesc}
49 \begin{haddockdesc}
50 \item[\begin{tabular}{@{}l}
51 class\ Monad\ m\ where
52 \end{tabular}]\haddockbegindoc
53 The \haddockid{Monad} class defines the basic operations over a \emph{monad},
54 a concept from a branch of mathematics known as \emph{category theory}.
55 From the perspective of a Haskell programmer, however, it is best to
56 think of a monad as an \emph{abstract datatype} of actions.
57 Haskell's \haddocktt{do} expressions provide a convenient syntax for writing
58 monadic expressions.
59 \par
60 Minimal complete definition: \haddockid{>>=} and \haddockid{return}.
61 \par
62 Instances of \haddockid{Monad} should satisfy the following laws:
63 \par
64 \begin{quote}
65 {\haddockverb\begin{verbatim}
66 return a >>= k == k a
67 m >>= return == m
68 m >>= (\x -> k x >>= h) == (m >>= k) >>= h
69 \end{verbatim}}
70 \end{quote}
71 Instances of both \haddockid{Monad} and \haddockid{Functor} should additionally satisfy the law:
72 \par
73 \begin{quote}
74 {\haddockverb\begin{verbatim}
75 fmap f xs == xs >>= return . f
76 \end{verbatim}}
77 \end{quote}
78 The instances of \haddockid{Monad} for lists, \haddocktt{Data.Maybe.Maybe} and \haddocktt{System.IO.IO}
79 defined in the \haddocktt{Prelude} satisfy these laws.
80 \par
81
82 \haddockpremethods{}\textbf{Methods}
83 \begin{haddockdesc}
84 \item[\begin{tabular}{@{}l}
85 (>>=)\ ::\ m\ a\ ->\ (a\ ->\ m\ b)\ ->\ m\ b
86 \end{tabular}]\haddockbegindoc
87 Sequentially compose two actions, passing any value produced
88 by the first as an argument to the second.
89 \par
90
91 \end{haddockdesc}
92 \begin{haddockdesc}
93 \item[\begin{tabular}{@{}l}
94 (>>)\ ::\ m\ a\ ->\ m\ b\ ->\ m\ b
95 \end{tabular}]\haddockbegindoc
96 Sequentially compose two actions, discarding any value produced
97 by the first, like sequencing operators (such as the semicolon)
98 in imperative languages.
99 \par
100
101 \end{haddockdesc}
102 \begin{haddockdesc}
103 \item[\begin{tabular}{@{}l}
104 return\ ::\ a\ ->\ m\ a
105 \end{tabular}]\haddockbegindoc
106 Inject a value into the monadic type.
107 \par
108
109 \end{haddockdesc}
110 \begin{haddockdesc}
111 \item[\begin{tabular}{@{}l}
112 fail\ ::\ String\ ->\ m\ a
113 \end{tabular}]\haddockbegindoc
114 Fail with a message. This operation is not part of the
115 mathematical definition of a monad, but is invoked on pattern-match
116 failure in a \haddocktt{do} expression.
117 \par
118
119 \end{haddockdesc}
120 \end{haddockdesc}
121 \begin{haddockdesc}
122 \item[\begin{tabular}{@{}l}
123 instance\ Monad\ {\char 91}{\char 93}\\instance\ Monad\ IO\\instance\ Monad\ P\\instance\ Monad\ ReadP\\instance\ Monad\ Maybe
124 \end{tabular}]
125 \end{haddockdesc}
126 \begin{haddockdesc}
127 \item[\begin{tabular}{@{}l}
128 class\ Monad\ m\ =>\ MonadPlus\ m\ where
129 \end{tabular}]\haddockbegindoc
130 Monads that also support choice and failure.
131 \par
132
133 \haddockpremethods{}\textbf{Methods}
134 \begin{haddockdesc}
135 \item[\begin{tabular}{@{}l}
136 mzero\ ::\ m\ a
137 \end{tabular}]\haddockbegindoc
138 the identity of \haddockid{mplus}. It should also satisfy the equations
139 \par
140 \begin{quote}
141 {\haddockverb\begin{verbatim}
142 mzero >>= f = mzero
143 v >> mzero = mzero
144 \end{verbatim}}
145 \end{quote}
146 (but the instance for \haddocktt{System.IO.IO} defined in Control.Monad.Error
147 in the mtl package does not satisfy the second one).
148 \par
149
150 \end{haddockdesc}
151 \begin{haddockdesc}
152 \item[\begin{tabular}{@{}l}
153 mplus\ ::\ m\ a\ ->\ m\ a\ ->\ m\ a
154 \end{tabular}]\haddockbegindoc
155 an associative operation
156 \par
157
158 \end{haddockdesc}
159 \end{haddockdesc}
160 \begin{haddockdesc}
161 \item[\begin{tabular}{@{}l}
162 instance\ MonadPlus\ {\char 91}{\char 93}\\instance\ MonadPlus\ P\\instance\ MonadPlus\ ReadP\\instance\ MonadPlus\ Maybe
163 \end{tabular}]
164 \end{haddockdesc}
165 \section{Functions
166 }
167 \subsection{Naming conventions
168 }
169 The functions in this library use the following naming conventions:
170 \par
171 \begin{itemize}
172 \item
173 A postfix '\haddocktt{M}' always stands for a function in the Kleisli category:
174 The monad type constructor \haddocktt{m} is added to function results
175 (modulo currying) and nowhere else. So, for example,
176 \par
177
178 \end{itemize}
179 \begin{quote}
180 {\haddockverb\begin{verbatim}
181 filter :: (a -> Bool) -> [a] -> [a]
182 filterM :: (Monad m) => (a -> m Bool) -> [a] -> m [a]
183 \end{verbatim}}
184 \end{quote}
185 \begin{itemize}
186 \item
187 A postfix '\haddocktt{{\char '137}}' changes the result type from \haddocktt{(m\ a)} to \haddocktt{(m\ ())}.
188 Thus, for example:
189 \par
190
191 \end{itemize}
192 \begin{quote}
193 {\haddockverb\begin{verbatim}
194 sequence :: Monad m => [m a] -> m [a]
195 sequence_ :: Monad m => [m a] -> m ()
196 \end{verbatim}}
197 \end{quote}
198 \begin{itemize}
199 \item
200 A prefix '\haddocktt{m}' generalizes an existing function to a monadic form.
201 Thus, for example:
202 \par
203
204 \end{itemize}
205 \begin{quote}
206 {\haddockverb\begin{verbatim}
207 sum :: Num a => [a] -> a
208 msum :: MonadPlus m => [m a] -> m a
209 \end{verbatim}}
210 \end{quote}
211
212 \subsection{Basic \haddocktt{Monad} functions
213 }
214 \begin{haddockdesc}
215 \item[\begin{tabular}{@{}l}
216 mapM\ ::\ Monad\ m\ =>\ (a\ ->\ m\ b)\ ->\ {\char 91}a{\char 93}\ ->\ m\ {\char 91}b{\char 93}
217 \end{tabular}]\haddockbegindoc
218 \haddocktt{mapM\ f} is equivalent to \haddocktt{sequence\ .\ map\ f}.
219 \par
220
221 \end{haddockdesc}
222 \begin{haddockdesc}
223 \item[\begin{tabular}{@{}l}
224 mapM{\char '137}\ ::\ Monad\ m\ =>\ (a\ ->\ m\ b)\ ->\ {\char 91}a{\char 93}\ ->\ m\ ()
225 \end{tabular}]\haddockbegindoc
226 \haddocktt{mapM{\char '137}\ f} is equivalent to \haddocktt{sequence{\char '137}\ .\ map\ f}.
227 \par
228
229 \end{haddockdesc}
230 \begin{haddockdesc}
231 \item[\begin{tabular}{@{}l}
232 forM\ ::\ Monad\ m\ =>\ {\char 91}a{\char 93}\ ->\ (a\ ->\ m\ b)\ ->\ m\ {\char 91}b{\char 93}
233 \end{tabular}]\haddockbegindoc
234 \haddockid{forM} is \haddockid{mapM} with its arguments flipped
235 \par
236
237 \end{haddockdesc}
238 \begin{haddockdesc}
239 \item[\begin{tabular}{@{}l}
240 forM{\char '137}\ ::\ Monad\ m\ =>\ {\char 91}a{\char 93}\ ->\ (a\ ->\ m\ b)\ ->\ m\ ()
241 \end{tabular}]\haddockbegindoc
242 \haddockid{forM{\char '137}} is \haddockid{mapM{\char '137}} with its arguments flipped
243 \par
244
245 \end{haddockdesc}
246 \begin{haddockdesc}
247 \item[\begin{tabular}{@{}l}
248 sequence\ ::\ Monad\ m\ =>\ {\char 91}m\ a{\char 93}\ ->\ m\ {\char 91}a{\char 93}
249 \end{tabular}]\haddockbegindoc
250 Evaluate each action in the sequence from left to right,
251 and collect the results.
252 \par
253
254 \end{haddockdesc}
255 \begin{haddockdesc}
256 \item[\begin{tabular}{@{}l}
257 sequence{\char '137}\ ::\ Monad\ m\ =>\ {\char 91}m\ a{\char 93}\ ->\ m\ ()
258 \end{tabular}]\haddockbegindoc
259 Evaluate each action in the sequence from left to right,
260 and ignore the results.
261 \par
262
263 \end{haddockdesc}
264 \begin{haddockdesc}
265 \item[\begin{tabular}{@{}l}
266 (=<<)\ ::\ Monad\ m\ =>\ (a\ ->\ m\ b)\ ->\ m\ a\ ->\ m\ b
267 \end{tabular}]\haddockbegindoc
268 Same as \haddockid{>>=}, but with the arguments interchanged.
269 \par
270
271 \end{haddockdesc}
272 \begin{haddockdesc}
273 \item[\begin{tabular}{@{}l}
274 (>=>)\ ::\ Monad\ m\ =>\ (a\ ->\ m\ b)\ ->\ (b\ ->\ m\ c)\ ->\ a\ ->\ m\ c
275 \end{tabular}]\haddockbegindoc
276 Left-to-right Kleisli composition of monads.
277 \par
278
279 \end{haddockdesc}
280 \begin{haddockdesc}
281 \item[\begin{tabular}{@{}l}
282 (<=<)\ ::\ Monad\ m\ =>\ (b\ ->\ m\ c)\ ->\ (a\ ->\ m\ b)\ ->\ a\ ->\ m\ c
283 \end{tabular}]\haddockbegindoc
284 Right-to-left Kleisli composition of monads. \haddocktt{(>=>)}, with the arguments flipped
285 \par
286
287 \end{haddockdesc}
288 \begin{haddockdesc}
289 \item[\begin{tabular}{@{}l}
290 forever\ ::\ Monad\ m\ =>\ m\ a\ ->\ m\ b
291 \end{tabular}]\haddockbegindoc
292 \haddocktt{forever\ act} repeats the action infinitely.
293 \par
294
295 \end{haddockdesc}
296 \begin{haddockdesc}
297 \item[\begin{tabular}{@{}l}
298 void\ ::\ Functor\ f\ =>\ f\ a\ ->\ f\ ()
299 \end{tabular}]\haddockbegindoc
300 \haddocktt{void\ value} discards or ignores the result of evaluation, such as the return value of an \haddockid{IO} action.
301 \par
302
303 \end{haddockdesc}
304 \subsection{Generalisations of list functions
305 }
306 \begin{haddockdesc}
307 \item[\begin{tabular}{@{}l}
308 join\ ::\ Monad\ m\ =>\ m\ (m\ a)\ ->\ m\ a
309 \end{tabular}]\haddockbegindoc
310 The \haddockid{join} function is the conventional monad join operator. It is used to
311 remove one level of monadic structure, projecting its bound argument into the
312 outer level.
313 \par
314
315 \end{haddockdesc}
316 \begin{haddockdesc}
317 \item[\begin{tabular}{@{}l}
318 msum\ ::\ MonadPlus\ m\ =>\ {\char 91}m\ a{\char 93}\ ->\ m\ a
319 \end{tabular}]\haddockbegindoc
320 This generalizes the list-based \haddockid{concat} function.
321 \par
322
323 \end{haddockdesc}
324 \begin{haddockdesc}
325 \item[\begin{tabular}{@{}l}
326 filterM\ ::\ Monad\ m\ =>\ (a\ ->\ m\ Bool)\ ->\ {\char 91}a{\char 93}\ ->\ m\ {\char 91}a{\char 93}
327 \end{tabular}]\haddockbegindoc
328 This generalizes the list-based \haddockid{filter} function.
329 \par
330
331 \end{haddockdesc}
332 \begin{haddockdesc}
333 \item[\begin{tabular}{@{}l}
334 mapAndUnzipM\ ::\ Monad\ m\ =>\ (a\ ->\ m\ (b,\ c))\ ->\ {\char 91}a{\char 93}\ ->\ m\ ({\char 91}b{\char 93},\ {\char 91}c{\char 93})
335 \end{tabular}]\haddockbegindoc
336 The \haddockid{mapAndUnzipM} function maps its first argument over a list, returning
337 the result as a pair of lists. This function is mainly used with complicated
338 data structures or a state-transforming monad.
339 \par
340
341 \end{haddockdesc}
342 \begin{haddockdesc}
343 \item[\begin{tabular}{@{}l}
344 zipWithM\ ::\ Monad\ m\ =>\ (a\ ->\ b\ ->\ m\ c)\ ->\ {\char 91}a{\char 93}\ ->\ {\char 91}b{\char 93}\ ->\ m\ {\char 91}c{\char 93}
345 \end{tabular}]\haddockbegindoc
346 The \haddockid{zipWithM} function generalizes \haddockid{zipWith} to arbitrary monads.
347 \par
348
349 \end{haddockdesc}
350 \begin{haddockdesc}
351 \item[\begin{tabular}{@{}l}
352 zipWithM{\char '137}\ ::\ Monad\ m\ =>\ (a\ ->\ b\ ->\ m\ c)\ ->\ {\char 91}a{\char 93}\ ->\ {\char 91}b{\char 93}\ ->\ m\ ()
353 \end{tabular}]\haddockbegindoc
354 \haddockid{zipWithM{\char '137}} is the extension of \haddockid{zipWithM} which ignores the final result.
355 \par
356
357 \end{haddockdesc}
358 \begin{haddockdesc}
359 \item[\begin{tabular}{@{}l}
360 foldM\ ::\ Monad\ m\ =>\ (a\ ->\ b\ ->\ m\ a)\ ->\ a\ ->\ {\char 91}b{\char 93}\ ->\ m\ a
361 \end{tabular}]\haddockbegindoc
362 The \haddockid{foldM} function is analogous to \haddockid{foldl}, except that its result is
363 encapsulated in a monad. Note that \haddockid{foldM} works from left-to-right over
364 the list arguments. This could be an issue where \haddocktt{(>>)} and the `folded
365 function' are not commutative.
366 \par
367 \begin{quote}
368 {\haddockverb\begin{verbatim}
369 foldM f a1 [x1, x2, ..., xm ]
370 \end{verbatim}}
371 \end{quote}
372 ==
373 \par
374 \begin{quote}
375 {\haddockverb\begin{verbatim}
376 do
377 a2 <- f a1 x1
378 a3 <- f a2 x2
379 ...
380 f am xm
381 \end{verbatim}}
382 \end{quote}
383 If right-to-left evaluation is required, the input list should be reversed.
384 \par
385
386 \end{haddockdesc}
387 \begin{haddockdesc}
388 \item[\begin{tabular}{@{}l}
389 foldM{\char '137}\ ::\ Monad\ m\ =>\ (a\ ->\ b\ ->\ m\ a)\ ->\ a\ ->\ {\char 91}b{\char 93}\ ->\ m\ ()
390 \end{tabular}]\haddockbegindoc
391 Like \haddockid{foldM}, but discards the result.
392 \par
393
394 \end{haddockdesc}
395 \begin{haddockdesc}
396 \item[\begin{tabular}{@{}l}
397 replicateM\ ::\ Monad\ m\ =>\ Int\ ->\ m\ a\ ->\ m\ {\char 91}a{\char 93}
398 \end{tabular}]\haddockbegindoc
399 \haddocktt{replicateM\ n\ act} performs the action \haddocktt{n} times,
400 gathering the results.
401 \par
402
403 \end{haddockdesc}
404 \begin{haddockdesc}
405 \item[\begin{tabular}{@{}l}
406 replicateM{\char '137}\ ::\ Monad\ m\ =>\ Int\ ->\ m\ a\ ->\ m\ ()
407 \end{tabular}]\haddockbegindoc
408 Like \haddockid{replicateM}, but discards the result.
409 \par
410
411 \end{haddockdesc}
412 \subsection{Conditional execution of monadic expressions
413 }
414 \begin{haddockdesc}
415 \item[\begin{tabular}{@{}l}
416 guard\ ::\ MonadPlus\ m\ =>\ Bool\ ->\ m\ ()
417 \end{tabular}]\haddockbegindoc
418 \haddocktt{guard\ b} is \haddocktt{return\ ()} if \haddocktt{b} is \haddockid{True},
419 and \haddockid{mzero} if \haddocktt{b} is \haddockid{False}.
420 \par
421
422 \end{haddockdesc}
423 \begin{haddockdesc}
424 \item[\begin{tabular}{@{}l}
425 when\ ::\ Monad\ m\ =>\ Bool\ ->\ m\ ()\ ->\ m\ ()
426 \end{tabular}]\haddockbegindoc
427 Conditional execution of monadic expressions. For example,
428 \par
429 \begin{quote}
430 {\haddockverb\begin{verbatim}
431 when debug (putStr "Debugging\n")
432 \end{verbatim}}
433 \end{quote}
434 will output the string \haddocktt{Debugging{\char '134}n} if the Boolean value \haddocktt{debug} is \haddockid{True},
435 and otherwise do nothing.
436 \par
437
438 \end{haddockdesc}
439 \begin{haddockdesc}
440 \item[\begin{tabular}{@{}l}
441 unless\ ::\ Monad\ m\ =>\ Bool\ ->\ m\ ()\ ->\ m\ ()
442 \end{tabular}]\haddockbegindoc
443 The reverse of \haddockid{when}.
444 \par
445
446 \end{haddockdesc}
447 \subsection{Monadic lifting operators
448 }
449 \begin{haddockdesc}
450 \item[\begin{tabular}{@{}l}
451 liftM\ ::\ Monad\ m\ =>\ (a1\ ->\ r)\ ->\ m\ a1\ ->\ m\ r
452 \end{tabular}]\haddockbegindoc
453 Promote a function to a monad.
454 \par
455
456 \end{haddockdesc}
457 \begin{haddockdesc}
458 \item[\begin{tabular}{@{}l}
459 liftM2\ ::\ Monad\ m\ =>\ (a1\ ->\ a2\ ->\ r)\ ->\ m\ a1\ ->\ m\ a2\ ->\ m\ r
460 \end{tabular}]\haddockbegindoc
461 Promote a function to a monad, scanning the monadic arguments from
462 left to right. For example,
463 \par
464 \begin{quote}
465 {\haddockverb\begin{verbatim}
466 liftM2 (+) [0,1] [0,2] = [0,2,1,3]
467 liftM2 (+) (Just 1) Nothing = Nothing
468 \end{verbatim}}
469 \end{quote}
470
471 \end{haddockdesc}
472 \begin{haddockdesc}
473 \item[\begin{tabular}{@{}l}
474 liftM3\ ::\ Monad\ m\ =>\ (a1\ ->\ a2\ ->\ a3\ ->\ r)\\\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ ->\ m\ a1\ ->\ m\ a2\ ->\ m\ a3\ ->\ m\ r
475 \end{tabular}]\haddockbegindoc
476 Promote a function to a monad, scanning the monadic arguments from
477 left to right (cf. \haddockid{liftM2}).
478 \par
479
480 \end{haddockdesc}
481 \begin{haddockdesc}
482 \item[\begin{tabular}{@{}l}
483 liftM4\ ::\ Monad\ m\ =>\ (a1\ ->\ a2\ ->\ a3\ ->\ a4\ ->\ r)\\\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ ->\ m\ a1\ ->\ m\ a2\ ->\ m\ a3\ ->\ m\ a4\ ->\ m\ r
484 \end{tabular}]\haddockbegindoc
485 Promote a function to a monad, scanning the monadic arguments from
486 left to right (cf. \haddockid{liftM2}).
487 \par
488
489 \end{haddockdesc}
490 \begin{haddockdesc}
491 \item[\begin{tabular}{@{}l}
492 liftM5\ ::\ Monad\ m\ =>\ (a1\ ->\ a2\ ->\ a3\ ->\ a4\ ->\ a5\ ->\ r)\\\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ ->\ m\ a1\ ->\ m\ a2\ ->\ m\ a3\ ->\ m\ a4\ ->\ m\ a5\ ->\ m\ r
493 \end{tabular}]\haddockbegindoc
494 Promote a function to a monad, scanning the monadic arguments from
495 left to right (cf. \haddockid{liftM2}).
496 \par
497
498 \end{haddockdesc}
499 \begin{haddockdesc}
500 \item[\begin{tabular}{@{}l}
501 ap\ ::\ Monad\ m\ =>\ m\ (a\ ->\ b)\ ->\ m\ a\ ->\ m\ b
502 \end{tabular}]\haddockbegindoc
503 In many situations, the \haddockid{liftM} operations can be replaced by uses of
504 \haddockid{ap}, which promotes function application.
505 \par
506 \begin{quote}
507 {\haddockverb\begin{verbatim}
508 return f `ap` x1 `ap` ... `ap` xn
509 \end{verbatim}}
510 \end{quote}
511 is equivalent to
512 \par
513 \begin{quote}
514 {\haddockverb\begin{verbatim}
515 liftMn f x1 x2 ... xn
516 \end{verbatim}}
517 \end{quote}
518
519 \end{haddockdesc}