Generalise `Control.Monad.{when,unless,guard}`
[ghc.git] / libraries / base / GHC / Base.lhs
1 \section[GHC.Base]{Module @GHC.Base@}
2
3 The overall structure of the GHC Prelude is a bit tricky.
4
5   a) We want to avoid "orphan modules", i.e. ones with instance
6         decls that don't belong either to a tycon or a class
7         defined in the same module
8
9   b) We want to avoid giant modules
10
11 So the rough structure is as follows, in (linearised) dependency order
12
13
14 GHC.Prim        Has no implementation.  It defines built-in things, and
15                 by importing it you bring them into scope.
16                 The source file is GHC.Prim.hi-boot, which is just
17                 copied to make GHC.Prim.hi
18
19 GHC.Base        Classes: Eq, Ord, Functor, Monad
20                 Types:   list, (), Int, Bool, Ordering, Char, String
21
22 Data.Tuple      Types: tuples, plus instances for GHC.Base classes
23
24 GHC.Show        Class: Show, plus instances for GHC.Base/GHC.Tup types
25
26 GHC.Enum        Class: Enum,  plus instances for GHC.Base/GHC.Tup types
27
28 Data.Maybe      Type: Maybe, plus instances for GHC.Base classes
29
30 GHC.List        List functions
31
32 GHC.Num         Class: Num, plus instances for Int
33                 Type:  Integer, plus instances for all classes so far (Eq, Ord, Num, Show)
34
35                 Integer is needed here because it is mentioned in the signature
36                 of 'fromInteger' in class Num
37
38 GHC.Real        Classes: Real, Integral, Fractional, RealFrac
39                          plus instances for Int, Integer
40                 Types:  Ratio, Rational
41                         plus intances for classes so far
42
43                 Rational is needed here because it is mentioned in the signature
44                 of 'toRational' in class Real
45
46 GHC.ST  The ST monad, instances and a few helper functions
47
48 Ix              Classes: Ix, plus instances for Int, Bool, Char, Integer, Ordering, tuples
49
50 GHC.Arr         Types: Array, MutableArray, MutableVar
51
52                 Arrays are used by a function in GHC.Float
53
54 GHC.Float       Classes: Floating, RealFloat
55                 Types:   Float, Double, plus instances of all classes so far
56
57                 This module contains everything to do with floating point.
58                 It is a big module (900 lines)
59                 With a bit of luck, many modules can be compiled without ever reading GHC.Float.hi
60
61
62 Other Prelude modules are much easier with fewer complex dependencies.
63
64 \begin{code}
65 {-# LANGUAGE Unsafe #-}
66 {-# LANGUAGE CPP
67            , NoImplicitPrelude
68            , BangPatterns
69            , ExplicitForAll
70            , MagicHash
71            , UnboxedTuples
72            , ExistentialQuantification
73            , RankNTypes
74   #-}
75 -- -fno-warn-orphans is needed for things like:
76 -- Orphan rule: "x# -# x#" ALWAYS forall x# :: Int# -# x# x# = 0
77 {-# OPTIONS_GHC -fno-warn-orphans #-}
78 {-# OPTIONS_HADDOCK hide #-}
79
80 -----------------------------------------------------------------------------
81 -- |
82 -- Module      :  GHC.Base
83 -- Copyright   :  (c) The University of Glasgow, 1992-2002
84 -- License     :  see libraries/base/LICENSE
85 --
86 -- Maintainer  :  cvs-ghc@haskell.org
87 -- Stability   :  internal
88 -- Portability :  non-portable (GHC extensions)
89 --
90 -- Basic data types and classes.
91 --
92 -----------------------------------------------------------------------------
93
94 #include "MachDeps.h"
95
96 module GHC.Base
97         (
98         module GHC.Base,
99         module GHC.Classes,
100         module GHC.CString,
101         module GHC.Magic,
102         module GHC.Types,
103         module GHC.Prim,        -- Re-export GHC.Prim and [boot] GHC.Err,
104                                 -- to avoid lots of people having to
105         module GHC.Err          -- import it explicitly
106   )
107         where
108
109 import GHC.Types
110 import GHC.Classes
111 import GHC.CString
112 import GHC.Magic
113 import GHC.Prim
114 import GHC.Err
115 import {-# SOURCE #-} GHC.IO (failIO)
116
117 import GHC.Tuple ()     -- Note [Depend on GHC.Tuple]
118 import GHC.Integer ()   -- Note [Depend on GHC.Integer]
119
120 infixr 9  .
121 infixr 5  ++
122 infixl 4  <$
123 infixl 1  >>, >>=
124 infixr 1  =<<
125 infixr 0  $, $!
126
127 infixl 4 <*>, <*, *>, <**>
128
129 default ()              -- Double isn't available yet
130 \end{code}
131
132 Note [Depend on GHC.Integer]
133 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~
134 The Integer type is special because TidyPgm uses
135 GHC.Integer.Type.mkInteger to construct Integer literal values
136 Currently it reads the interface file whether or not the current
137 module *has* any Integer literals, so it's important that
138 GHC.Integer.Type (in patckage integer-gmp or integer-simple) is
139 compiled before any other module.  (There's a hack in GHC to disable
140 this for packages ghc-prim, integer-gmp, integer-simple, which aren't
141 allowed to contain any Integer literals.)
142
143 Likewise we implicitly need Integer when deriving things like Eq
144 instances.
145
146 The danger is that if the build system doesn't know about the dependency
147 on Integer, it'll compile some base module before GHC.Integer.Type,
148 resulting in:
149   Failed to load interface for ‘GHC.Integer.Type’
150     There are files missing in the ‘integer-gmp’ package,
151
152 Bottom line: we make GHC.Base depend on GHC.Integer; and everything
153 else either depends on GHC.Base, or does not have NoImplicitPrelude
154 (and hence depends on Prelude).
155
156 Note [Depend on GHC.Tuple]
157 ~~~~~~~~~~~~~~~~~~~~~~~~~~
158 Similarly, tuple syntax (or ()) creates an implicit dependency on
159 GHC.Tuple, so we use the same rule as for Integer --- see Note [Depend on
160 GHC.Integer] --- to explain this to the build system.  We make GHC.Base
161 depend on GHC.Tuple, and everything else depends on GHC.Base or Prelude.
162
163 %*********************************************************
164 %*                                                      *
165 \subsection{DEBUGGING STUFF}
166 %*  (for use when compiling GHC.Base itself doesn't work)
167 %*                                                      *
168 %*********************************************************
169
170 \begin{code}
171 {-
172 data  Bool  =  False | True
173 data Ordering = LT | EQ | GT
174 data Char = C# Char#
175 type  String = [Char]
176 data Int = I# Int#
177 data  ()  =  ()
178 data [] a = MkNil
179
180 not True = False
181 (&&) True True = True
182 otherwise = True
183
184 build = error "urk"
185 foldr = error "urk"
186 -}
187
188 \end{code}
189
190 %*********************************************************
191 %*                                                      *
192 \subsection{The Maybe type}
193 %*                                                      *
194 %*********************************************************
195 \begin{code}
196
197 -- | The 'Maybe' type encapsulates an optional value.  A value of type
198 -- @'Maybe' a@ either contains a value of type @a@ (represented as @'Just' a@),
199 -- or it is empty (represented as 'Nothing').  Using 'Maybe' is a good way to
200 -- deal with errors or exceptional cases without resorting to drastic
201 -- measures such as 'error'.
202 --
203 -- The 'Maybe' type is also a monad.  It is a simple kind of error
204 -- monad, where all errors are represented by 'Nothing'.  A richer
205 -- error monad can be built using the 'Data.Either.Either' type.
206 --
207 data  Maybe a  =  Nothing | Just a
208   deriving (Eq, Ord)
209
210 \end{code}
211
212 %*********************************************************
213 %*                                                      *
214 \subsection{Monoids}
215 %*                                                      *
216 %*********************************************************
217 \begin{code}
218
219 -- ---------------------------------------------------------------------------
220 -- | The class of monoids (types with an associative binary operation that
221 -- has an identity).  Instances should satisfy the following laws:
222 --
223 --  * @mappend mempty x = x@
224 --
225 --  * @mappend x mempty = x@
226 --
227 --  * @mappend x (mappend y z) = mappend (mappend x y) z@
228 --
229 --  * @mconcat = 'foldr' mappend mempty@
230 --
231 -- The method names refer to the monoid of lists under concatenation,
232 -- but there are many other instances.
233 --
234 -- Minimal complete definition: 'mempty' and 'mappend'.
235 --
236 -- Some types can be viewed as a monoid in more than one way,
237 -- e.g. both addition and multiplication on numbers.
238 -- In such cases we often define @newtype@s and make those instances
239 -- of 'Monoid', e.g. 'Sum' and 'Product'.
240
241 class Monoid a where
242         mempty  :: a
243         -- ^ Identity of 'mappend'
244         mappend :: a -> a -> a
245         -- ^ An associative operation
246         mconcat :: [a] -> a
247
248         -- ^ Fold a list using the monoid.
249         -- For most types, the default definition for 'mconcat' will be
250         -- used, but the function is included in the class definition so
251         -- that an optimized version can be provided for specific types.
252
253         mconcat = foldr mappend mempty
254
255 instance Monoid [a] where
256         mempty  = []
257         mappend = (++)
258
259 instance Monoid b => Monoid (a -> b) where
260         mempty _ = mempty
261         mappend f g x = f x `mappend` g x
262
263 instance Monoid () where
264         -- Should it be strict?
265         mempty        = ()
266         _ `mappend` _ = ()
267         mconcat _     = ()
268
269 instance (Monoid a, Monoid b) => Monoid (a,b) where
270         mempty = (mempty, mempty)
271         (a1,b1) `mappend` (a2,b2) =
272                 (a1 `mappend` a2, b1 `mappend` b2)
273
274 instance (Monoid a, Monoid b, Monoid c) => Monoid (a,b,c) where
275         mempty = (mempty, mempty, mempty)
276         (a1,b1,c1) `mappend` (a2,b2,c2) =
277                 (a1 `mappend` a2, b1 `mappend` b2, c1 `mappend` c2)
278
279 instance (Monoid a, Monoid b, Monoid c, Monoid d) => Monoid (a,b,c,d) where
280         mempty = (mempty, mempty, mempty, mempty)
281         (a1,b1,c1,d1) `mappend` (a2,b2,c2,d2) =
282                 (a1 `mappend` a2, b1 `mappend` b2,
283                  c1 `mappend` c2, d1 `mappend` d2)
284
285 instance (Monoid a, Monoid b, Monoid c, Monoid d, Monoid e) =>
286                 Monoid (a,b,c,d,e) where
287         mempty = (mempty, mempty, mempty, mempty, mempty)
288         (a1,b1,c1,d1,e1) `mappend` (a2,b2,c2,d2,e2) =
289                 (a1 `mappend` a2, b1 `mappend` b2, c1 `mappend` c2,
290                  d1 `mappend` d2, e1 `mappend` e2)
291
292 -- lexicographical ordering
293 instance Monoid Ordering where
294         mempty         = EQ
295         LT `mappend` _ = LT
296         EQ `mappend` y = y
297         GT `mappend` _ = GT
298
299 -- | Lift a semigroup into 'Maybe' forming a 'Monoid' according to
300 -- <http://en.wikipedia.org/wiki/Monoid>: \"Any semigroup @S@ may be
301 -- turned into a monoid simply by adjoining an element @e@ not in @S@
302 -- and defining @e*e = e@ and @e*s = s = s*e@ for all @s ∈ S@.\" Since
303 -- there is no \"Semigroup\" typeclass providing just 'mappend', we
304 -- use 'Monoid' instead.
305 instance Monoid a => Monoid (Maybe a) where
306   mempty = Nothing
307   Nothing `mappend` m = m
308   m `mappend` Nothing = m
309   Just m1 `mappend` Just m2 = Just (m1 `mappend` m2)
310
311 instance Monoid a => Applicative ((,) a) where
312     pure x = (mempty, x)
313     (u, f) <*> (v, x) = (u `mappend` v, f x)
314 \end{code}
315
316
317 %*********************************************************
318 %*                                                      *
319 \subsection{Monadic classes @Functor@, @Applicative@, @Monad@ }
320 %*                                                      *
321 %*********************************************************
322
323 \begin{code}
324 {- | The 'Functor' class is used for types that can be mapped over.
325 Instances of 'Functor' should satisfy the following laws:
326
327 > fmap id  ==  id
328 > fmap (f . g)  ==  fmap f . fmap g
329
330 The instances of 'Functor' for lists, 'Data.Maybe.Maybe' and 'System.IO.IO'
331 satisfy these laws.
332 -}
333
334 class  Functor f  where
335     fmap        :: (a -> b) -> f a -> f b
336
337     -- | Replace all locations in the input with the same value.
338     -- The default definition is @'fmap' . 'const'@, but this may be
339     -- overridden with a more efficient version.
340     (<$)        :: a -> f b -> f a
341     (<$)        =  fmap . const
342
343 -- | A functor with application, providing operations to
344 --
345 -- * embed pure expressions ('pure'), and
346 --
347 -- * sequence computations and combine their results ('<*>').
348 --
349 -- A minimal complete definition must include implementations of these
350 -- functions satisfying the following laws:
351 --
352 -- [/identity/]
353 --
354 --      @'pure' 'id' '<*>' v = v@
355 --
356 -- [/composition/]
357 --
358 --      @'pure' (.) '<*>' u '<*>' v '<*>' w = u '<*>' (v '<*>' w)@
359 --
360 -- [/homomorphism/]
361 --
362 --      @'pure' f '<*>' 'pure' x = 'pure' (f x)@
363 --
364 -- [/interchange/]
365 --
366 --      @u '<*>' 'pure' y = 'pure' ('$' y) '<*>' u@
367 --
368 -- The other methods have the following default definitions, which may
369 -- be overridden with equivalent specialized implementations:
370 --
371 --   * @u '*>' v = 'pure' ('const' 'id') '<*>' u '<*>' v@
372 --
373 --   * @u '<*' v = 'pure' 'const' '<*>' u '<*>' v@
374 --
375 -- As a consequence of these laws, the 'Functor' instance for @f@ will satisfy
376 --
377 --   * @'fmap' f x = 'pure' f '<*>' x@
378 --
379 -- If @f@ is also a 'Monad', it should satisfy
380 --
381 --   * @'pure' = 'return'@
382 --
383 --   * @('<*>') = 'ap'@
384 --
385 -- (which implies that 'pure' and '<*>' satisfy the applicative functor laws).
386
387 class Functor f => Applicative f where
388     -- | Lift a value.
389     pure :: a -> f a
390
391     -- | Sequential application.
392     (<*>) :: f (a -> b) -> f a -> f b
393
394     -- | Sequence actions, discarding the value of the first argument.
395     (*>) :: f a -> f b -> f b
396     (*>) = liftA2 (const id)
397
398     -- | Sequence actions, discarding the value of the second argument.
399     (<*) :: f a -> f b -> f a
400     (<*) = liftA2 const
401
402 -- | A variant of '<*>' with the arguments reversed.
403 (<**>) :: Applicative f => f a -> f (a -> b) -> f b
404 (<**>) = liftA2 (flip ($))
405
406 -- | Lift a function to actions.
407 -- This function may be used as a value for `fmap` in a `Functor` instance.
408 liftA :: Applicative f => (a -> b) -> f a -> f b
409 liftA f a = pure f <*> a
410
411 -- | Lift a binary function to actions.
412 liftA2 :: Applicative f => (a -> b -> c) -> f a -> f b -> f c
413 liftA2 f a b = (fmap f a) <*> b
414
415 -- | Lift a ternary function to actions.
416 liftA3 :: Applicative f => (a -> b -> c -> d) -> f a -> f b -> f c -> f d
417 liftA3 f a b c = (fmap f a) <*> b <*> c
418
419 {- | The 'Monad' class defines the basic operations over a /monad/,
420 a concept from a branch of mathematics known as /category theory/.
421 From the perspective of a Haskell programmer, however, it is best to
422 think of a monad as an /abstract datatype/ of actions.
423 Haskell's @do@ expressions provide a convenient syntax for writing
424 monadic expressions.
425
426 Minimal complete definition: '>>=' and 'return'.
427
428 Instances of 'Monad' should satisfy the following laws:
429
430 > return a >>= k  ==  k a
431 > m >>= return  ==  m
432 > m >>= (\x -> k x >>= h)  ==  (m >>= k) >>= h
433
434 Instances of both 'Monad' and 'Functor' should additionally satisfy the law:
435
436 > fmap f xs  ==  xs >>= return . f
437
438 The instances of 'Monad' for lists, 'Data.Maybe.Maybe' and 'System.IO.IO'
439 defined in the "Prelude" satisfy these laws.
440 -}
441
442 -- | The 'join' function is the conventional monad join operator. It
443 -- is used to remove one level of monadic structure, projecting its
444 -- bound argument into the outer level.
445 join              :: (Monad m) => m (m a) -> m a
446 join x            =  x >>= id
447
448 class Applicative m => Monad m where
449     -- | Sequentially compose two actions, passing any value produced
450     -- by the first as an argument to the second.
451     (>>=)       :: forall a b. m a -> (a -> m b) -> m b
452
453     -- | Sequentially compose two actions, discarding any value produced
454     -- by the first, like sequencing operators (such as the semicolon)
455     -- in imperative languages.
456     (>>)        :: forall a b. m a -> m b -> m b
457     m >> k = m >>= \_ -> k -- See Note [Recursive bindings for Applicative/Monad]
458     {-# INLINE (>>) #-}
459
460     -- | Inject a value into the monadic type.
461     return      :: a -> m a
462
463     -- | Fail with a message.  This operation is not part of the
464     -- mathematical definition of a monad, but is invoked on pattern-match
465     -- failure in a @do@ expression.
466     fail        :: String -> m a
467     fail s      = error s
468
469 {- Note [Recursive bindings for Applicative/Monad]
470 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
471
472 The original Applicative/Monad proposal stated that after
473 implementation, the designated implementation of (>>) would become
474
475   (>>) :: forall a b. m a -> m b -> m b
476   (>>) = (*>)
477
478 by default. You might be inclined to change this to reflect the stated
479 proposal, but you really shouldn't! Why? Because people tend to define
480 such instances the /other/ way around: in particular, it is perfectly
481 legitimate to define an instance of Applicative (*>) in terms of (>>),
482 which would lead to an infinite loop for the default implementation of
483 Monad! And people do this in the wild.
484
485 This turned into a nasty bug that was tricky to track down, and rather
486 than eliminate it everywhere upstream, it's easier to just retain the
487 original default.
488
489 -}
490
491 -- | Same as '>>=', but with the arguments interchanged.
492 {-# SPECIALISE (=<<) :: (a -> [b]) -> [a] -> [b] #-}
493 (=<<)           :: Monad m => (a -> m b) -> m a -> m b
494 f =<< x         = x >>= f
495
496 -- | Conditional execution of 'Applicative' expressions. For example,
497 --
498 -- > when debug (putStrLn "Debugging")
499 --
500 -- will output the string @Debugging@ if the Boolean value @debug@
501 -- is 'True', and otherwise do nothing.
502 when      :: (Applicative f) => Bool -> f () -> f ()
503 {-# INLINEABLE when #-}
504 {-# SPECIALISE when :: Bool -> IO () -> IO () #-}
505 {-# SPECIALISE when :: Bool -> Maybe () -> Maybe () #-}
506 when p s  = if p then s else pure ()
507
508 -- | Evaluate each action in the sequence from left to right,
509 -- and collect the results.
510 sequence :: Monad m => [m a] -> m [a]
511 {-# INLINE sequence #-}
512 sequence ms = foldr k (return []) ms
513             where
514               k m m' = do { x <- m; xs <- m'; return (x:xs) }
515
516 -- | @'mapM' f@ is equivalent to @'sequence' . 'map' f@.
517 mapM :: Monad m => (a -> m b) -> [a] -> m [b]
518 {-# INLINE mapM #-}
519 mapM f as       =  sequence (map f as)
520
521 -- | Promote a function to a monad.
522 liftM   :: (Monad m) => (a1 -> r) -> m a1 -> m r
523 liftM f m1              = do { x1 <- m1; return (f x1) }
524
525 -- | Promote a function to a monad, scanning the monadic arguments from
526 -- left to right.  For example,
527 --
528 -- >    liftM2 (+) [0,1] [0,2] = [0,2,1,3]
529 -- >    liftM2 (+) (Just 1) Nothing = Nothing
530 --
531 liftM2  :: (Monad m) => (a1 -> a2 -> r) -> m a1 -> m a2 -> m r
532 liftM2 f m1 m2          = do { x1 <- m1; x2 <- m2; return (f x1 x2) }
533
534 -- | Promote a function to a monad, scanning the monadic arguments from
535 -- left to right (cf. 'liftM2').
536 liftM3  :: (Monad m) => (a1 -> a2 -> a3 -> r) -> m a1 -> m a2 -> m a3 -> m r
537 liftM3 f m1 m2 m3       = do { x1 <- m1; x2 <- m2; x3 <- m3; return (f x1 x2 x3) }
538
539 -- | Promote a function to a monad, scanning the monadic arguments from
540 -- left to right (cf. 'liftM2').
541 liftM4  :: (Monad m) => (a1 -> a2 -> a3 -> a4 -> r) -> m a1 -> m a2 -> m a3 -> m a4 -> m r
542 liftM4 f m1 m2 m3 m4    = do { x1 <- m1; x2 <- m2; x3 <- m3; x4 <- m4; return (f x1 x2 x3 x4) }
543
544 -- | Promote a function to a monad, scanning the monadic arguments from
545 -- left to right (cf. 'liftM2').
546 liftM5  :: (Monad m) => (a1 -> a2 -> a3 -> a4 -> a5 -> r) -> m a1 -> m a2 -> m a3 -> m a4 -> m a5 -> m r
547 liftM5 f m1 m2 m3 m4 m5 = do { x1 <- m1; x2 <- m2; x3 <- m3; x4 <- m4; x5 <- m5; return (f x1 x2 x3 x4 x5) }
548
549 {-# INLINEABLE liftM #-}
550 {-# SPECIALISE liftM :: (a1->r) -> IO a1 -> IO r #-}
551 {-# SPECIALISE liftM :: (a1->r) -> Maybe a1 -> Maybe r #-}
552 {-# INLINEABLE liftM2 #-}
553 {-# SPECIALISE liftM2 :: (a1->a2->r) -> IO a1 -> IO a2 -> IO r #-}
554 {-# SPECIALISE liftM2 :: (a1->a2->r) -> Maybe a1 -> Maybe a2 -> Maybe r #-}
555 {-# INLINEABLE liftM3 #-}
556 {-# SPECIALISE liftM3 :: (a1->a2->a3->r) -> IO a1 -> IO a2 -> IO a3 -> IO r #-}
557 {-# SPECIALISE liftM3 :: (a1->a2->a3->r) -> Maybe a1 -> Maybe a2 -> Maybe a3 -> Maybe r #-}
558 {-# INLINEABLE liftM4 #-}
559 {-# SPECIALISE liftM4 :: (a1->a2->a3->a4->r) -> IO a1 -> IO a2 -> IO a3 -> IO a4 -> IO r #-}
560 {-# SPECIALISE liftM4 :: (a1->a2->a3->a4->r) -> Maybe a1 -> Maybe a2 -> Maybe a3 -> Maybe a4 -> Maybe r #-}
561 {-# INLINEABLE liftM5 #-}
562 {-# SPECIALISE liftM5 :: (a1->a2->a3->a4->a5->r) -> IO a1 -> IO a2 -> IO a3 -> IO a4 -> IO a5 -> IO r #-}
563 {-# SPECIALISE liftM5 :: (a1->a2->a3->a4->a5->r) -> Maybe a1 -> Maybe a2 -> Maybe a3 -> Maybe a4 -> Maybe a5 -> Maybe r #-}
564
565 {- | In many situations, the 'liftM' operations can be replaced by uses of
566 'ap', which promotes function application.
567
568 >       return f `ap` x1 `ap` ... `ap` xn
569
570 is equivalent to
571
572 >       liftMn f x1 x2 ... xn
573
574 -}
575
576 ap                :: (Monad m) => m (a -> b) -> m a -> m b
577 ap                =  liftM2 id
578
579 -- instances for Prelude types
580
581 instance Functor ((->) r) where
582     fmap = (.)
583
584 instance Applicative ((->) a) where
585     pure = const
586     (<*>) f g x = f x (g x)
587
588 instance Monad ((->) r) where
589     return = const
590     f >>= k = \ r -> k (f r) r
591
592 instance Functor ((,) a) where
593     fmap f (x,y) = (x, f y)
594
595
596 instance  Functor Maybe  where
597     fmap _ Nothing       = Nothing
598     fmap f (Just a)      = Just (f a)
599
600 instance Applicative Maybe where
601     pure = return
602     (<*>) = ap
603
604 instance  Monad Maybe  where
605     (Just x) >>= k      = k x
606     Nothing  >>= _      = Nothing
607
608     (Just _) >>  k      = k
609     Nothing  >>  _      = Nothing
610
611     return              = Just
612     fail _              = Nothing
613
614 -- -----------------------------------------------------------------------------
615 -- The Alternative class definition
616
617 infixl 3 <|>
618
619 -- | A monoid on applicative functors.
620 --
621 -- Minimal complete definition: 'empty' and '<|>'.
622 --
623 -- If defined, 'some' and 'many' should be the least solutions
624 -- of the equations:
625 --
626 -- * @some v = (:) '<$>' v '<*>' many v@
627 --
628 -- * @many v = some v '<|>' 'pure' []@
629 class Applicative f => Alternative f where
630     -- | The identity of '<|>'
631     empty :: f a
632     -- | An associative binary operation
633     (<|>) :: f a -> f a -> f a
634
635     -- | One or more.
636     some :: f a -> f [a]
637     some v = some_v
638       where
639         many_v = some_v <|> pure []
640         some_v = (fmap (:) v) <*> many_v
641
642     -- | Zero or more.
643     many :: f a -> f [a]
644     many v = many_v
645       where
646         many_v = some_v <|> pure []
647         some_v = (fmap (:) v) <*> many_v
648
649
650 instance Alternative Maybe where
651     empty = Nothing
652     Nothing <|> r = r
653     l       <|> _ = l
654
655 -- -----------------------------------------------------------------------------
656 -- The MonadPlus class definition
657
658 -- | Monads that also support choice and failure.
659 class (Alternative m, Monad m) => MonadPlus m where
660    -- | the identity of 'mplus'.  It should also satisfy the equations
661    --
662    -- > mzero >>= f  =  mzero
663    -- > v >> mzero   =  mzero
664    --
665    mzero :: m a
666    mzero = empty
667
668    -- | an associative operation
669    mplus :: m a -> m a -> m a
670    mplus = (<|>)
671
672 instance MonadPlus Maybe where
673    mzero = Nothing
674
675    Nothing `mplus` ys  = ys
676    xs      `mplus` _ys = xs
677 \end{code}
678
679
680 %*********************************************************
681 %*                                                      *
682 \subsection{The list type}
683 %*                                                      *
684 %*********************************************************
685
686 \begin{code}
687 instance Functor [] where
688     fmap = map
689
690 instance Applicative [] where
691     pure = return
692     (<*>) = ap
693
694 instance  Monad []  where
695     m >>= k             = foldr ((++) . k) [] m
696     m >> k              = foldr ((++) . (\ _ -> k)) [] m
697     return x            = [x]
698     fail _              = []
699
700 instance Alternative [] where
701     empty = []
702     (<|>) = (++)
703
704 instance MonadPlus [] where
705    mzero = []
706    mplus = (++)
707 \end{code}
708
709 A few list functions that appear here because they are used here.
710 The rest of the prelude list functions are in GHC.List.
711
712 ----------------------------------------------
713 --      foldr/build/augment
714 ----------------------------------------------
715
716 \begin{code}
717 -- | 'foldr', applied to a binary operator, a starting value (typically
718 -- the right-identity of the operator), and a list, reduces the list
719 -- using the binary operator, from right to left:
720 --
721 -- > foldr f z [x1, x2, ..., xn] == x1 `f` (x2 `f` ... (xn `f` z)...)
722
723 foldr            :: (a -> b -> b) -> b -> [a] -> b
724 -- foldr _ z []     =  z
725 -- foldr f z (x:xs) =  f x (foldr f z xs)
726 {-# INLINE [0] foldr #-}
727 -- Inline only in the final stage, after the foldr/cons rule has had a chance
728 -- Also note that we inline it when it has *two* parameters, which are the
729 -- ones we are keen about specialising!
730 foldr k z = go
731           where
732             go []     = z
733             go (y:ys) = y `k` go ys
734
735 -- | A list producer that can be fused with 'foldr'.
736 -- This function is merely
737 --
738 -- >    build g = g (:) []
739 --
740 -- but GHC's simplifier will transform an expression of the form
741 -- @'foldr' k z ('build' g)@, which may arise after inlining, to @g k z@,
742 -- which avoids producing an intermediate list.
743
744 build   :: forall a. (forall b. (a -> b -> b) -> b -> b) -> [a]
745 {-# INLINE [1] build #-}
746         -- The INLINE is important, even though build is tiny,
747         -- because it prevents [] getting inlined in the version that
748         -- appears in the interface file.  If [] *is* inlined, it
749         -- won't match with [] appearing in rules in an importing module.
750         --
751         -- The "1" says to inline in phase 1
752
753 build g = g (:) []
754
755 -- | A list producer that can be fused with 'foldr'.
756 -- This function is merely
757 --
758 -- >    augment g xs = g (:) xs
759 --
760 -- but GHC's simplifier will transform an expression of the form
761 -- @'foldr' k z ('augment' g xs)@, which may arise after inlining, to
762 -- @g k ('foldr' k z xs)@, which avoids producing an intermediate list.
763
764 augment :: forall a. (forall b. (a->b->b) -> b -> b) -> [a] -> [a]
765 {-# INLINE [1] augment #-}
766 augment g xs = g (:) xs
767
768 {-# RULES
769 "fold/build"    forall k z (g::forall b. (a->b->b) -> b -> b) .
770                 foldr k z (build g) = g k z
771
772 "foldr/augment" forall k z xs (g::forall b. (a->b->b) -> b -> b) .
773                 foldr k z (augment g xs) = g k (foldr k z xs)
774
775 "foldr/id"                        foldr (:) [] = \x  -> x
776 "foldr/app"     [1] forall ys. foldr (:) ys = \xs -> xs ++ ys
777         -- Only activate this from phase 1, because that's
778         -- when we disable the rule that expands (++) into foldr
779
780 -- The foldr/cons rule looks nice, but it can give disastrously
781 -- bloated code when commpiling
782 --      array (a,b) [(1,2), (2,2), (3,2), ...very long list... ]
783 -- i.e. when there are very very long literal lists
784 -- So I've disabled it for now. We could have special cases
785 -- for short lists, I suppose.
786 -- "foldr/cons" forall k z x xs. foldr k z (x:xs) = k x (foldr k z xs)
787
788 "foldr/single"  forall k z x. foldr k z [x] = k x z
789 "foldr/nil"     forall k z.   foldr k z []  = z
790
791 "augment/build" forall (g::forall b. (a->b->b) -> b -> b)
792                        (h::forall b. (a->b->b) -> b -> b) .
793                        augment g (build h) = build (\c n -> g c (h c n))
794 "augment/nil"   forall (g::forall b. (a->b->b) -> b -> b) .
795                         augment g [] = build g
796  #-}
797
798 -- This rule is true, but not (I think) useful:
799 --      augment g (augment h t) = augment (\cn -> g c (h c n)) t
800 \end{code}
801
802
803 ----------------------------------------------
804 --              map
805 ----------------------------------------------
806
807 \begin{code}
808 -- | 'map' @f xs@ is the list obtained by applying @f@ to each element
809 -- of @xs@, i.e.,
810 --
811 -- > map f [x1, x2, ..., xn] == [f x1, f x2, ..., f xn]
812 -- > map f [x1, x2, ...] == [f x1, f x2, ...]
813
814 map :: (a -> b) -> [a] -> [b]
815 {-# NOINLINE [1] map #-}    -- We want the RULE to fire first.
816                             -- It's recursive, so won't inline anyway,
817                             -- but saying so is more explicit
818 map _ []     = []
819 map f (x:xs) = f x : map f xs
820
821 -- Note eta expanded
822 mapFB ::  (elt -> lst -> lst) -> (a -> elt) -> a -> lst -> lst
823 {-# INLINE [0] mapFB #-}
824 mapFB c f = \x ys -> c (f x) ys
825
826 -- The rules for map work like this.
827 --
828 -- Up to (but not including) phase 1, we use the "map" rule to
829 -- rewrite all saturated applications of map with its build/fold
830 -- form, hoping for fusion to happen.
831 -- In phase 1 and 0, we switch off that rule, inline build, and
832 -- switch on the "mapList" rule, which rewrites the foldr/mapFB
833 -- thing back into plain map.
834 --
835 -- It's important that these two rules aren't both active at once
836 -- (along with build's unfolding) else we'd get an infinite loop
837 -- in the rules.  Hence the activation control below.
838 --
839 -- The "mapFB" rule optimises compositions of map.
840 --
841 -- This same pattern is followed by many other functions:
842 -- e.g. append, filter, iterate, repeat, etc.
843
844 {-# RULES
845 "map"       [~1] forall f xs.   map f xs                = build (\c n -> foldr (mapFB c f) n xs)
846 "mapList"   [1]  forall f.      foldr (mapFB (:) f) []  = map f
847 "mapFB"     forall c f g.       mapFB (mapFB c f) g     = mapFB c (f.g)
848   #-}
849
850 -- There's also a rule for Map and Data.Coerce. See "Safe Coercions",
851 -- section 6.4:
852 --
853 --   http://research.microsoft.com/en-us/um/people/simonpj/papers/ext-f/coercible.pdf
854
855 {-# RULES "map/coerce" [1] map coerce = coerce #-}
856
857 \end{code}
858
859
860 ----------------------------------------------
861 --              append
862 ----------------------------------------------
863 \begin{code}
864 -- | Append two lists, i.e.,
865 --
866 -- > [x1, ..., xm] ++ [y1, ..., yn] == [x1, ..., xm, y1, ..., yn]
867 -- > [x1, ..., xm] ++ [y1, ...] == [x1, ..., xm, y1, ...]
868 --
869 -- If the first list is not finite, the result is the first list.
870
871 (++) :: [a] -> [a] -> [a]
872 {-# NOINLINE [1] (++) #-}    -- We want the RULE to fire first.
873                              -- It's recursive, so won't inline anyway,
874                              -- but saying so is more explicit
875 (++) []     ys = ys
876 (++) (x:xs) ys = x : xs ++ ys
877
878 {-# RULES
879 "++"    [~1] forall xs ys. xs ++ ys = augment (\c n -> foldr c n xs) ys
880   #-}
881
882 \end{code}
883
884
885 %*********************************************************
886 %*                                                      *
887 \subsection{Type @Bool@}
888 %*                                                      *
889 %*********************************************************
890
891 \begin{code}
892 -- |'otherwise' is defined as the value 'True'.  It helps to make
893 -- guards more readable.  eg.
894 --
895 -- >  f x | x < 0     = ...
896 -- >      | otherwise = ...
897 otherwise               :: Bool
898 otherwise               =  True
899 \end{code}
900
901 %*********************************************************
902 %*                                                      *
903 \subsection{Type @Char@ and @String@}
904 %*                                                      *
905 %*********************************************************
906
907 \begin{code}
908 -- | A 'String' is a list of characters.  String constants in Haskell are values
909 -- of type 'String'.
910 --
911 type String = [Char]
912
913 unsafeChr :: Int -> Char
914 unsafeChr (I# i#) = C# (chr# i#)
915
916 -- | The 'Prelude.fromEnum' method restricted to the type 'Data.Char.Char'.
917 ord :: Char -> Int
918 ord (C# c#) = I# (ord# c#)
919 \end{code}
920
921 String equality is used when desugaring pattern-matches against strings.
922
923 \begin{code}
924 eqString :: String -> String -> Bool
925 eqString []       []       = True
926 eqString (c1:cs1) (c2:cs2) = c1 == c2 && cs1 `eqString` cs2
927 eqString _        _        = False
928
929 {-# RULES "eqString" (==) = eqString #-}
930 -- eqString also has a BuiltInRule in PrelRules.lhs:
931 --      eqString (unpackCString# (Lit s1)) (unpackCString# (Lit s2) = s1==s2
932 \end{code}
933
934
935 %*********************************************************
936 %*                                                      *
937 \subsection{Type @Int@}
938 %*                                                      *
939 %*********************************************************
940
941 \begin{code}
942 maxInt, minInt :: Int
943
944 {- Seems clumsy. Should perhaps put minInt and MaxInt directly into MachDeps.h -}
945 #if WORD_SIZE_IN_BITS == 31
946 minInt  = I# (-0x40000000#)
947 maxInt  = I# 0x3FFFFFFF#
948 #elif WORD_SIZE_IN_BITS == 32
949 minInt  = I# (-0x80000000#)
950 maxInt  = I# 0x7FFFFFFF#
951 #else
952 minInt  = I# (-0x8000000000000000#)
953 maxInt  = I# 0x7FFFFFFFFFFFFFFF#
954 #endif
955 \end{code}
956
957
958 %*********************************************************
959 %*                                                      *
960 \subsection{The function type}
961 %*                                                      *
962 %*********************************************************
963
964 \begin{code}
965 -- | Identity function.
966 id                      :: a -> a
967 id x                    =  x
968
969 -- Assertion function.  This simply ignores its boolean argument.
970 -- The compiler may rewrite it to @('assertError' line)@.
971
972 -- | If the first argument evaluates to 'True', then the result is the
973 -- second argument.  Otherwise an 'AssertionFailed' exception is raised,
974 -- containing a 'String' with the source file and line number of the
975 -- call to 'assert'.
976 --
977 -- Assertions can normally be turned on or off with a compiler flag
978 -- (for GHC, assertions are normally on unless optimisation is turned on
979 -- with @-O@ or the @-fignore-asserts@
980 -- option is given).  When assertions are turned off, the first
981 -- argument to 'assert' is ignored, and the second argument is
982 -- returned as the result.
983
984 --      SLPJ: in 5.04 etc 'assert' is in GHC.Prim,
985 --      but from Template Haskell onwards it's simply
986 --      defined here in Base.lhs
987 assert :: Bool -> a -> a
988 assert _pred r = r
989
990 breakpoint :: a -> a
991 breakpoint r = r
992
993 breakpointCond :: Bool -> a -> a
994 breakpointCond _ r = r
995
996 data Opaque = forall a. O a
997
998 -- | Constant function.
999 const                   :: a -> b -> a
1000 const x _               =  x
1001
1002 -- | Function composition.
1003 {-# INLINE (.) #-}
1004 -- Make sure it has TWO args only on the left, so that it inlines
1005 -- when applied to two functions, even if there is no final argument
1006 (.)    :: (b -> c) -> (a -> b) -> a -> c
1007 (.) f g = \x -> f (g x)
1008
1009 -- | @'flip' f@ takes its (first) two arguments in the reverse order of @f@.
1010 flip                    :: (a -> b -> c) -> b -> a -> c
1011 flip f x y              =  f y x
1012
1013 -- | Application operator.  This operator is redundant, since ordinary
1014 -- application @(f x)@ means the same as @(f '$' x)@. However, '$' has
1015 -- low, right-associative binding precedence, so it sometimes allows
1016 -- parentheses to be omitted; for example:
1017 --
1018 -- >     f $ g $ h x  =  f (g (h x))
1019 --
1020 -- It is also useful in higher-order situations, such as @'map' ('$' 0) xs@,
1021 -- or @'Data.List.zipWith' ('$') fs xs@.
1022 {-# INLINE ($) #-}
1023 ($)                     :: (a -> b) -> a -> b
1024 f $ x                   =  f x
1025
1026 -- | Strict (call-by-value) application, defined in terms of 'seq'.
1027 ($!)                    :: (a -> b) -> a -> b
1028 f $! x                  = let !vx = x in f vx  -- see #2273
1029
1030 -- | @'until' p f@ yields the result of applying @f@ until @p@ holds.
1031 until                   :: (a -> Bool) -> (a -> a) -> a -> a
1032 until p f = go
1033   where
1034     go x | p x          = x
1035          | otherwise    = go (f x)
1036
1037 -- | 'asTypeOf' is a type-restricted version of 'const'.  It is usually
1038 -- used as an infix operator, and its typing forces its first argument
1039 -- (which is usually overloaded) to have the same type as the second.
1040 asTypeOf                :: a -> a -> a
1041 asTypeOf                =  const
1042 \end{code}
1043
1044 %*********************************************************
1045 %*                                                      *
1046 \subsection{@Functor@ and @Monad@ instances for @IO@}
1047 %*                                                      *
1048 %*********************************************************
1049
1050 \begin{code}
1051 instance  Functor IO where
1052    fmap f x = x >>= (return . f)
1053
1054 instance Applicative IO where
1055     pure = return
1056     (<*>) = ap
1057
1058 instance  Monad IO  where
1059     {-# INLINE return #-}
1060     {-# INLINE (>>)   #-}
1061     {-# INLINE (>>=)  #-}
1062     m >> k    = m >>= \ _ -> k
1063     return    = returnIO
1064     (>>=)     = bindIO
1065     fail s    = failIO s
1066
1067 returnIO :: a -> IO a
1068 returnIO x = IO $ \ s -> (# s, x #)
1069
1070 bindIO :: IO a -> (a -> IO b) -> IO b
1071 bindIO (IO m) k = IO $ \ s -> case m s of (# new_s, a #) -> unIO (k a) new_s
1072
1073 thenIO :: IO a -> IO b -> IO b
1074 thenIO (IO m) k = IO $ \ s -> case m s of (# new_s, _ #) -> unIO k new_s
1075
1076 unIO :: IO a -> (State# RealWorld -> (# State# RealWorld, a #))
1077 unIO (IO a) = a
1078 \end{code}
1079
1080 %*********************************************************
1081 %*                                                      *
1082 \subsection{@getTag@}
1083 %*                                                      *
1084 %*********************************************************
1085
1086 Returns the 'tag' of a constructor application; this function is used
1087 by the deriving code for Eq, Ord and Enum.
1088
1089 The primitive dataToTag# requires an evaluated constructor application
1090 as its argument, so we provide getTag as a wrapper that performs the
1091 evaluation before calling dataToTag#.  We could have dataToTag#
1092 evaluate its argument, but we prefer to do it this way because (a)
1093 dataToTag# can be an inline primop if it doesn't need to do any
1094 evaluation, and (b) we want to expose the evaluation to the
1095 simplifier, because it might be possible to eliminate the evaluation
1096 in the case when the argument is already known to be evaluated.
1097
1098 \begin{code}
1099 {-# INLINE getTag #-}
1100 getTag :: a -> Int#
1101 getTag x = x `seq` dataToTag# x
1102 \end{code}
1103
1104 %*********************************************************
1105 %*                                                      *
1106 \subsection{Numeric primops}
1107 %*                                                      *
1108 %*********************************************************
1109
1110 Definitions of the boxed PrimOps; these will be
1111 used in the case of partial applications, etc.
1112
1113 \begin{code}
1114 {-# INLINE quotInt #-}
1115 {-# INLINE remInt #-}
1116
1117 quotInt, remInt, divInt, modInt :: Int -> Int -> Int
1118 (I# x) `quotInt`  (I# y) = I# (x `quotInt#` y)
1119 (I# x) `remInt`   (I# y) = I# (x `remInt#`  y)
1120 (I# x) `divInt`   (I# y) = I# (x `divInt#`  y)
1121 (I# x) `modInt`   (I# y) = I# (x `modInt#`  y)
1122
1123 quotRemInt :: Int -> Int -> (Int, Int)
1124 (I# x) `quotRemInt` (I# y) = case x `quotRemInt#` y of
1125                              (# q, r #) ->
1126                                  (I# q, I# r)
1127
1128 divModInt :: Int -> Int -> (Int, Int)
1129 (I# x) `divModInt` (I# y) = case x `divModInt#` y of
1130                             (# q, r #) -> (I# q, I# r)
1131
1132 divModInt# :: Int# -> Int# -> (# Int#, Int# #)
1133 x# `divModInt#` y#
1134  | isTrue# (x# ># 0#) && isTrue# (y# <# 0#) =
1135                                     case (x# -# 1#) `quotRemInt#` y# of
1136                                       (# q, r #) -> (# q -# 1#, r +# y# +# 1# #)
1137  | isTrue# (x# <# 0#) && isTrue# (y# ># 0#) =
1138                                     case (x# +# 1#) `quotRemInt#` y# of
1139                                       (# q, r #) -> (# q -# 1#, r +# y# -# 1# #)
1140  | otherwise                                =
1141                                     x# `quotRemInt#` y#
1142
1143 -- Wrappers for the shift operations.  The uncheckedShift# family are
1144 -- undefined when the amount being shifted by is greater than the size
1145 -- in bits of Int#, so these wrappers perform a check and return
1146 -- either zero or -1 appropriately.
1147 --
1148 -- Note that these wrappers still produce undefined results when the
1149 -- second argument (the shift amount) is negative.
1150
1151 -- | Shift the argument left by the specified number of bits
1152 -- (which must be non-negative).
1153 shiftL# :: Word# -> Int# -> Word#
1154 a `shiftL#` b   | isTrue# (b >=# WORD_SIZE_IN_BITS#) = 0##
1155                 | otherwise                          = a `uncheckedShiftL#` b
1156
1157 -- | Shift the argument right by the specified number of bits
1158 -- (which must be non-negative).
1159 -- The "RL" means "right, logical" (as opposed to RA for arithmetic)
1160 -- (although an arithmetic right shift wouldn't make sense for Word#)
1161 shiftRL# :: Word# -> Int# -> Word#
1162 a `shiftRL#` b  | isTrue# (b >=# WORD_SIZE_IN_BITS#) = 0##
1163                 | otherwise                          = a `uncheckedShiftRL#` b
1164
1165 -- | Shift the argument left by the specified number of bits
1166 -- (which must be non-negative).
1167 iShiftL# :: Int# -> Int# -> Int#
1168 a `iShiftL#` b  | isTrue# (b >=# WORD_SIZE_IN_BITS#) = 0#
1169                 | otherwise                          = a `uncheckedIShiftL#` b
1170
1171 -- | Shift the argument right (signed) by the specified number of bits
1172 -- (which must be non-negative).
1173 -- The "RA" means "right, arithmetic" (as opposed to RL for logical)
1174 iShiftRA# :: Int# -> Int# -> Int#
1175 a `iShiftRA#` b | isTrue# (b >=# WORD_SIZE_IN_BITS#) = if isTrue# (a <# 0#)
1176                                                           then (-1#)
1177                                                           else 0#
1178                 | otherwise                          = a `uncheckedIShiftRA#` b
1179
1180 -- | Shift the argument right (unsigned) by the specified number of bits
1181 -- (which must be non-negative).
1182 -- The "RL" means "right, logical" (as opposed to RA for arithmetic)
1183 iShiftRL# :: Int# -> Int# -> Int#
1184 a `iShiftRL#` b | isTrue# (b >=# WORD_SIZE_IN_BITS#) = 0#
1185                 | otherwise                          = a `uncheckedIShiftRL#` b
1186
1187 -- Rules for C strings (the functions themselves are now in GHC.CString)
1188 {-# RULES
1189 "unpack"       [~1] forall a   . unpackCString# a             = build (unpackFoldrCString# a)
1190 "unpack-list"  [1]  forall a   . unpackFoldrCString# a (:) [] = unpackCString# a
1191 "unpack-append"     forall a n . unpackFoldrCString# a (:) n  = unpackAppendCString# a n
1192
1193 -- There's a built-in rule (in PrelRules.lhs) for
1194 --      unpackFoldr "foo" c (unpackFoldr "baz" c n)  =  unpackFoldr "foobaz" c n
1195
1196   #-}
1197 \end{code}
1198
1199
1200 #ifdef __HADDOCK__
1201 \begin{code}
1202 -- | A special argument for the 'Control.Monad.ST.ST' type constructor,
1203 -- indexing a state embedded in the 'Prelude.IO' monad by
1204 -- 'Control.Monad.ST.stToIO'.
1205 data RealWorld
1206 \end{code}
1207 #endif