pattern_guard_list_comprehension_footnote
[haskell-report.git] / report / monad.verb
1 %**<title>The Haskell 98 Library Report: Monad Utilities</title>
2 %**~header
3 \section{Monad Utilities}
4 \label{Monad}
5
6 \outline{
7 \inputHS{lib-hdrs/Monad}
8 }
9
10 The @Monad@ library defines the @MonadPlus@ class, and 
11 provides some useful operations on monads.
12
13 \subsection{Naming conventions}
14
15 The functions in this library use the following naming conventions:
16 \begin{itemize}
17 \item
18 A postfix ``@M@'' always stands for a function in the Kleisli category:
19 @m@ is added to function results (modulo currying) and nowhere else.
20 So, for example,
21 \bprog
22 @
23   filter  ::            (a ->   Bool) -> [a] ->   [a]
24   filterM :: Monad m => (a -> m Bool) -> [a] -> m [a]
25 @
26 \eprog
27
28 \item A postfix ``@_@'' changes the result type from @(m a)@ to @(m ())@.
29 Thus (in the @Prelude@):
30 \bprog
31 @
32 sequence  :: Monad m => [m a] -> m [a] 
33 sequence_ :: Monad m => [m a] -> m () 
34 @
35 \eprog
36
37 \item A prefix ``@m@'' generalises an existing function to a monadic form.
38 Thus, for example:
39 \bprog
40 @
41   sum  :: Num a       => [a]   -> a
42   msum :: MonadPlus m => [m a] -> m a
43 @
44 \eprog
45 \end{itemize}
46
47 \subsection{Class @MonadPlus@}
48
49 The @MonadPlus@ class is defined as follows:
50 \bprog
51 @
52 class  Monad m => MonadPlus m  where
53     mzero  :: m a
54     mplus  :: m a -> m a -> m a
55 @
56 \eprog
57 The class methods @mzero@ and @mplus@ are the zero and plus
58 of the monad.
59
60 Lists and the @Maybe@ type are instances of @MonadPlus@, thus:
61 \bprog
62 @
63 instance  MonadPlus Maybe  where
64     mzero                 = Nothing
65     Nothing `mplus` ys    = ys
66     xs      `mplus` ys    = xs
67
68 instance  MonadPlus []  where
69     mzero = []
70     mplus = (++)
71 @
72 \eprog
73
74
75 \subsection{Functions}
76
77 The @join@ function is the conventional monad join operator.  It is
78 used to remove one level of monadic structure, projecting its bound
79 argument into the outer level.
80
81 % There is no convincing small-scale example for mapAndUnzipM
82 The @mapAndUnzipM@ function maps its first argument over a list,
83 returning the result as a pair of lists.  This function is mainly used
84 with complicated data structures or a state-transforming monad.
85
86 The @zipWithM@ function generalises @zipWith@ to arbitrary monads.
87 For instance the following function displays a file, prefixing
88 each line with its line number,
89 \par
90 {\small
91 \bprog
92 @
93 listFile :: String -> IO ()
94 listFile nm =
95   do cts <- readFile nm
96      zipWithM_ (\i line -> do putStr (show i); putStr ": "; putStrLn line)
97                [1..]
98                (lines cts)
99 @
100 \eprog
101 }
102 The @foldM@ function is analogous to @foldl@, except that its result
103 is encapsulated in a monad.  Note that @foldM@ works from
104 left-to-right over the list arguments.  This could be an issue where
105 @(>>)@ and the ``folded function'' are not commutative. 
106 \bprog
107 @
108     foldM f a1 [x1, x2, ..., xm ]
109 ==  
110     do
111       a2 <- f a1 x1
112       a3 <- f a2 x2
113       ...
114       f am xm
115 @
116 \eprog
117 If right-to-left
118 evaluation is required, the input list should be reversed.
119
120 % Omitted for now.  These functions are very useful in parsing libraries
121 % - but in a slightly modified form:
122 % o It is conventional to return the _longest_ parse first - not 
123 %   shortest first.
124 % o The function is too strict - you can't get any part of the result
125 %   until the entire parse completes.  The fix is to use the function
126 %   force when defining zeroOrMore.
127 %   
128 %     force :: Parser a -> Parser a
129 %     force (P m) = P (\i -> let x = p i in
130 %                            (fst (head x), snd (head x)) : tail x)
131 %
132 %   but how are we to generalise this to an arbitrary monad?
133 %
134 % The @zeroOrMore@ function performs an action repeatedly - returning
135 % the list of all results obtained.  The @oneOrMore@ function is similar
136 % but the action must succeed at least once.  That is,
137 % \bprog
138 % <at>
139 % zeroOrMore m = zero ++ 
140 %                [ [a0]       | a0 <- m ] ++
141 %                [ [a0,a1]    | a0 <- m, a1 <- m ] ++
142 %                [ [a0,a1,a2] | a0 <- m, a1 <- m, a2 <- m ] ++
143 %                ...
144
145 % oneOrMore m  = [ [a0]       | a0 <- m ] ++
146 %                [ [a0,a1]    | a0 <- m, a1 <- m ] ++
147 %                [ [a0,a1,a2] | a0 <- m, a1 <- m, a2 <- m ] ++
148 %                ...
149 % <at>
150 % \eprog
151
152 The @when@ and @unless@ functions provide conditional execution of
153 monadic expressions.  For example,
154 \bprog
155 @
156 when debug (putStr "Debugging\n")
157 @
158 \eprog
159 will output the string @"Debugging\n"@ if the Boolean value @debug@ is
160 @True@, and otherwise do nothing.
161
162 The monadic lifting operators promote a function to a monad.  The
163 function arguments are scanned left to right.  For example,
164 \bprog
165 @
166 liftM2 (+) [0,1] [0,2] = [0,2,1,3]
167 liftM2 (+) (Just 1) Nothing = Nothing
168 @
169 \eprog
170
171 In many situations, the @liftM@ operations can be replaced by uses
172 of @ap@, which promotes function application.
173 \bprog
174 @
175 return f `ap` x1 `ap` ... `ap` xn
176 @
177 \eprog
178 is equivalent to
179 \bprog
180 @
181 liftMn f x1 x2 ... xn
182 @
183 \eprog
184 \clearpage
185 \subsection{Library {\tt Monad}}
186 \inputHS{lib-code/Monad}
187
188 %**~footer
189