Make Applicative a superclass of Monad
[ghc.git] / libraries / base / Control / Monad.hs
1 {-# LANGUAGE Trustworthy #-}
2 {-# LANGUAGE NoImplicitPrelude #-}
3
4 -----------------------------------------------------------------------------
5 -- |
6 -- Module : Control.Monad
7 -- Copyright : (c) The University of Glasgow 2001
8 -- License : BSD-style (see the file libraries/base/LICENSE)
9 --
10 -- Maintainer : libraries@haskell.org
11 -- Stability : provisional
12 -- Portability : portable
13 --
14 -- The 'Functor', 'Monad' and 'MonadPlus' classes,
15 -- with some useful operations on monads.
16
17 module Control.Monad
18 (
19 -- * Functor and monad classes
20
21 Functor(fmap)
22 , Monad((>>=), (>>), return, fail)
23 , Alternative(empty, (<|>), some, many)
24 , MonadPlus(mzero, mplus)
25 -- * Functions
26
27 -- ** Naming conventions
28 -- $naming
29
30 -- ** Basic @Monad@ functions
31
32 , mapM
33 , mapM_
34 , forM
35 , forM_
36 , sequence
37 , sequence_
38 , (=<<)
39 , (>=>)
40 , (<=<)
41 , forever
42 , void
43
44 -- ** Generalisations of list functions
45
46 , join
47 , msum
48 , mfilter
49 , filterM
50 , mapAndUnzipM
51 , zipWithM
52 , zipWithM_
53 , foldM
54 , foldM_
55 , replicateM
56 , replicateM_
57
58 -- ** Conditional execution of monadic expressions
59
60 , guard
61 , when
62 , unless
63
64 -- ** Monadic lifting operators
65
66 , liftM
67 , liftM2
68 , liftM3
69 , liftM4
70 , liftM5
71
72 , ap
73
74 -- ** Strict monadic functions
75
76 , (<$!>)
77 ) where
78
79 import Data.Maybe
80
81 import GHC.List
82 import GHC.Base
83
84 infixr 1 =<<
85 infixl 3 <|>
86
87 -- -----------------------------------------------------------------------------
88 -- Prelude monad functions
89
90 -- | Same as '>>=', but with the arguments interchanged.
91 {-# SPECIALISE (=<<) :: (a -> [b]) -> [a] -> [b] #-}
92 (=<<) :: Monad m => (a -> m b) -> m a -> m b
93 f =<< x = x >>= f
94
95 -- | Evaluate each action in the sequence from left to right,
96 -- and collect the results.
97 sequence :: Monad m => [m a] -> m [a]
98 {-# INLINE sequence #-}
99 sequence ms = foldr k (return []) ms
100 where
101 k m m' = do { x <- m; xs <- m'; return (x:xs) }
102
103 -- | Evaluate each action in the sequence from left to right,
104 -- and ignore the results.
105 sequence_ :: Monad m => [m a] -> m ()
106 {-# INLINE sequence_ #-}
107 sequence_ ms = foldr (>>) (return ()) ms
108
109 -- | @'mapM' f@ is equivalent to @'sequence' . 'map' f@.
110 mapM :: Monad m => (a -> m b) -> [a] -> m [b]
111 {-# INLINE mapM #-}
112 mapM f as = sequence (map f as)
113
114 -- | @'mapM_' f@ is equivalent to @'sequence_' . 'map' f@.
115 mapM_ :: Monad m => (a -> m b) -> [a] -> m ()
116 {-# INLINE mapM_ #-}
117 mapM_ f as = sequence_ (map f as)
118
119 -- -----------------------------------------------------------------------------
120 -- The Alternative class definition
121
122 -- | A monoid on applicative functors.
123 --
124 -- Minimal complete definition: 'empty' and '<|>'.
125 --
126 -- If defined, 'some' and 'many' should be the least solutions
127 -- of the equations:
128 --
129 -- * @some v = (:) '<$>' v '<*>' many v@
130 --
131 -- * @many v = some v '<|>' 'pure' []@
132 class Applicative f => Alternative f where
133 -- | The identity of '<|>'
134 empty :: f a
135 -- | An associative binary operation
136 (<|>) :: f a -> f a -> f a
137
138 -- | One or more.
139 some :: f a -> f [a]
140 some v = some_v
141 where
142 many_v = some_v <|> pure []
143 some_v = (fmap (:) v) <*> many_v
144
145 -- | Zero or more.
146 many :: f a -> f [a]
147 many v = many_v
148 where
149 many_v = some_v <|> pure []
150 some_v = (fmap (:) v) <*> many_v
151
152 instance Alternative Maybe where
153 empty = Nothing
154 Nothing <|> r = r
155 l <|> _ = l
156
157 instance Alternative [] where
158 empty = []
159 (<|>) = (++)
160
161
162 -- -----------------------------------------------------------------------------
163 -- The MonadPlus class definition
164
165 -- | Monads that also support choice and failure.
166 class (Alternative m, Monad m) => MonadPlus m where
167 -- | the identity of 'mplus'. It should also satisfy the equations
168 --
169 -- > mzero >>= f = mzero
170 -- > v >> mzero = mzero
171 --
172 mzero :: m a
173 mzero = empty
174
175 -- | an associative operation
176 mplus :: m a -> m a -> m a
177 mplus = (<|>)
178
179 instance MonadPlus [] where
180 mzero = []
181 mplus = (++)
182
183 instance MonadPlus Maybe where
184 mzero = Nothing
185
186 Nothing `mplus` ys = ys
187 xs `mplus` _ys = xs
188
189 -- -----------------------------------------------------------------------------
190 -- Functions mandated by the Prelude
191
192 -- | @'guard' b@ is @'return' ()@ if @b@ is 'True',
193 -- and 'mzero' if @b@ is 'False'.
194 guard :: (MonadPlus m) => Bool -> m ()
195 guard True = return ()
196 guard False = mzero
197
198 -- | This generalizes the list-based 'filter' function.
199
200 filterM :: (Monad m) => (a -> m Bool) -> [a] -> m [a]
201 filterM _ [] = return []
202 filterM p (x:xs) = do
203 flg <- p x
204 ys <- filterM p xs
205 return (if flg then x:ys else ys)
206
207 -- | 'forM' is 'mapM' with its arguments flipped
208 forM :: Monad m => [a] -> (a -> m b) -> m [b]
209 {-# INLINE forM #-}
210 forM = flip mapM
211
212 -- | 'forM_' is 'mapM_' with its arguments flipped
213 forM_ :: Monad m => [a] -> (a -> m b) -> m ()
214 {-# INLINE forM_ #-}
215 forM_ = flip mapM_
216
217 -- | This generalizes the list-based 'concat' function.
218
219 msum :: MonadPlus m => [m a] -> m a
220 {-# INLINE msum #-}
221 msum = foldr mplus mzero
222
223 infixr 1 <=<, >=>
224
225 -- | Left-to-right Kleisli composition of monads.
226 (>=>) :: Monad m => (a -> m b) -> (b -> m c) -> (a -> m c)
227 f >=> g = \x -> f x >>= g
228
229 -- | Right-to-left Kleisli composition of monads. @('>=>')@, with the arguments flipped
230 (<=<) :: Monad m => (b -> m c) -> (a -> m b) -> (a -> m c)
231 (<=<) = flip (>=>)
232
233 -- | @'forever' act@ repeats the action infinitely.
234 forever :: (Monad m) => m a -> m b
235 {-# INLINE forever #-}
236 forever a = let a' = a >> a' in a'
237 -- Use explicit sharing here, as it is prevents a space leak regardless of
238 -- optimizations.
239
240 -- | @'void' value@ discards or ignores the result of evaluation, such as the return value of an 'IO' action.
241 void :: Functor f => f a -> f ()
242 void = fmap (const ())
243
244 -- -----------------------------------------------------------------------------
245 -- Other monad functions
246
247 -- | The 'mapAndUnzipM' function maps its first argument over a list, returning
248 -- the result as a pair of lists. This function is mainly used with complicated
249 -- data structures or a state-transforming monad.
250 mapAndUnzipM :: (Monad m) => (a -> m (b,c)) -> [a] -> m ([b], [c])
251 {-# INLINE mapAndUnzipM #-}
252 mapAndUnzipM f xs = sequence (map f xs) >>= return . unzip
253
254 -- | The 'zipWithM' function generalizes 'zipWith' to arbitrary monads.
255 zipWithM :: (Monad m) => (a -> b -> m c) -> [a] -> [b] -> m [c]
256 {-# INLINE zipWithM #-}
257 zipWithM f xs ys = sequence (zipWith f xs ys)
258
259 -- | 'zipWithM_' is the extension of 'zipWithM' which ignores the final result.
260 zipWithM_ :: (Monad m) => (a -> b -> m c) -> [a] -> [b] -> m ()
261 {-# INLINE zipWithM_ #-}
262 zipWithM_ f xs ys = sequence_ (zipWith f xs ys)
263
264 {- | The 'foldM' function is analogous to 'foldl', except that its result is
265 encapsulated in a monad. Note that 'foldM' works from left-to-right over
266 the list arguments. This could be an issue where @('>>')@ and the `folded
267 function' are not commutative.
268
269
270 > foldM f a1 [x1, x2, ..., xm]
271
272 ==
273
274 > do
275 > a2 <- f a1 x1
276 > a3 <- f a2 x2
277 > ...
278 > f am xm
279
280 If right-to-left evaluation is required, the input list should be reversed.
281 -}
282
283 foldM :: (Monad m) => (a -> b -> m a) -> a -> [b] -> m a
284 {-# INLINEABLE foldM #-}
285 {-# SPECIALISE foldM :: (a -> b -> IO a) -> a -> [b] -> IO a #-}
286 {-# SPECIALISE foldM :: (a -> b -> Maybe a) -> a -> [b] -> Maybe a #-}
287 foldM _ a [] = return a
288 foldM f a (x:xs) = f a x >>= \fax -> foldM f fax xs
289
290 -- | Like 'foldM', but discards the result.
291 foldM_ :: (Monad m) => (a -> b -> m a) -> a -> [b] -> m ()
292 {-# INLINEABLE foldM_ #-}
293 {-# SPECIALISE foldM_ :: (a -> b -> IO a) -> a -> [b] -> IO () #-}
294 {-# SPECIALISE foldM_ :: (a -> b -> Maybe a) -> a -> [b] -> Maybe () #-}
295 foldM_ f a xs = foldM f a xs >> return ()
296
297 -- | @'replicateM' n act@ performs the action @n@ times,
298 -- gathering the results.
299 replicateM :: (Monad m) => Int -> m a -> m [a]
300 {-# INLINEABLE replicateM #-}
301 {-# SPECIALISE replicateM :: Int -> IO a -> IO [a] #-}
302 {-# SPECIALISE replicateM :: Int -> Maybe a -> Maybe [a] #-}
303 replicateM n x = sequence (replicate n x)
304
305 -- | Like 'replicateM', but discards the result.
306 replicateM_ :: (Monad m) => Int -> m a -> m ()
307 {-# INLINEABLE replicateM_ #-}
308 {-# SPECIALISE replicateM_ :: Int -> IO a -> IO () #-}
309 {-# SPECIALISE replicateM_ :: Int -> Maybe a -> Maybe () #-}
310 replicateM_ n x = sequence_ (replicate n x)
311
312 {- | Conditional execution of monadic expressions. For example,
313
314 > when debug (putStr "Debugging\n")
315
316 will output the string @Debugging\\n@ if the Boolean value @debug@ is 'True',
317 and otherwise do nothing.
318 -}
319
320 when :: (Monad m) => Bool -> m () -> m ()
321 {-# INLINEABLE when #-}
322 {-# SPECIALISE when :: Bool -> IO () -> IO () #-}
323 {-# SPECIALISE when :: Bool -> Maybe () -> Maybe () #-}
324 when p s = if p then s else return ()
325
326 -- | The reverse of 'when'.
327
328 unless :: (Monad m) => Bool -> m () -> m ()
329 {-# INLINEABLE unless #-}
330 {-# SPECIALISE unless :: Bool -> IO () -> IO () #-}
331 {-# SPECIALISE unless :: Bool -> Maybe () -> Maybe () #-}
332 unless p s = if p then return () else s
333
334 infixl 4 <$!>
335
336 -- | Strict version of 'Data.Functor.<$>'.
337 --
338 -- /Since: 4.7.1.0/
339 (<$!>) :: Monad m => (a -> b) -> m a -> m b
340 {-# INLINE (<$!>) #-}
341 f <$!> m = do
342 x <- m
343 let z = f x
344 z `seq` return z
345
346
347 -- -----------------------------------------------------------------------------
348 -- Other MonadPlus functions
349
350 -- | Direct 'MonadPlus' equivalent of 'filter'
351 -- @'filter'@ = @(mfilter:: (a -> Bool) -> [a] -> [a]@
352 -- applicable to any 'MonadPlus', for example
353 -- @mfilter odd (Just 1) == Just 1@
354 -- @mfilter odd (Just 2) == Nothing@
355
356 mfilter :: (MonadPlus m) => (a -> Bool) -> m a -> m a
357 {-# INLINEABLE mfilter #-}
358 mfilter p ma = do
359 a <- ma
360 if p a then return a else mzero
361
362 {- $naming
363
364 The functions in this library use the following naming conventions:
365
366 * A postfix \'@M@\' always stands for a function in the Kleisli category:
367 The monad type constructor @m@ is added to function results
368 (modulo currying) and nowhere else. So, for example,
369
370 > filter :: (a -> Bool) -> [a] -> [a]
371 > filterM :: (Monad m) => (a -> m Bool) -> [a] -> m [a]
372
373 * A postfix \'@_@\' changes the result type from @(m a)@ to @(m ())@.
374 Thus, for example:
375
376 > sequence :: Monad m => [m a] -> m [a]
377 > sequence_ :: Monad m => [m a] -> m ()
378
379 * A prefix \'@m@\' generalizes an existing function to a monadic form.
380 Thus, for example:
381
382 > sum :: Num a => [a] -> a
383 > msum :: MonadPlus m => [m a] -> m a
384
385 -}