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