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