Make Applicative a superclass of Monad
[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     m >>= f = join (fmap f m)
417
418     -- | Sequentially compose two actions, discarding any value produced
419     -- by the first, like sequencing operators (such as the semicolon)
420     -- in imperative languages.
421     (>>)        :: forall a b. m a -> m b -> m b
422     m >> k = m >>= \_ -> k
423     {-# INLINE (>>) #-}
424
425     -- | Inject a value into the monadic type.
426     return      :: a -> m a
427
428     -- | Fail with a message.  This operation is not part of the
429     -- mathematical definition of a monad, but is invoked on pattern-match
430     -- failure in a @do@ expression.
431     fail        :: String -> m a
432     fail s      = error s
433
434 -- | Promote a function to a monad.
435 liftM   :: (Monad m) => (a1 -> r) -> m a1 -> m r
436 liftM f m1              = do { x1 <- m1; return (f x1) }
437
438 -- | Promote a function to a monad, scanning the monadic arguments from
439 -- left to right.  For example,
440 --
441 -- >    liftM2 (+) [0,1] [0,2] = [0,2,1,3]
442 -- >    liftM2 (+) (Just 1) Nothing = Nothing
443 --
444 liftM2  :: (Monad m) => (a1 -> a2 -> r) -> m a1 -> m a2 -> m r
445 liftM2 f m1 m2          = do { x1 <- m1; x2 <- m2; return (f x1 x2) }
446
447 -- | Promote a function to a monad, scanning the monadic arguments from
448 -- left to right (cf. 'liftM2').
449 liftM3  :: (Monad m) => (a1 -> a2 -> a3 -> r) -> m a1 -> m a2 -> m a3 -> m r
450 liftM3 f m1 m2 m3       = do { x1 <- m1; x2 <- m2; x3 <- m3; return (f x1 x2 x3) }
451
452 -- | Promote a function to a monad, scanning the monadic arguments from
453 -- left to right (cf. 'liftM2').
454 liftM4  :: (Monad m) => (a1 -> a2 -> a3 -> a4 -> r) -> m a1 -> m a2 -> m a3 -> m a4 -> m r
455 liftM4 f m1 m2 m3 m4    = do { x1 <- m1; x2 <- m2; x3 <- m3; x4 <- m4; return (f x1 x2 x3 x4) }
456
457 -- | Promote a function to a monad, scanning the monadic arguments from
458 -- left to right (cf. 'liftM2').
459 liftM5  :: (Monad m) => (a1 -> a2 -> a3 -> a4 -> a5 -> r) -> m a1 -> m a2 -> m a3 -> m a4 -> m a5 -> m r
460 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) }
461
462 {-# INLINEABLE liftM #-}
463 {-# SPECIALISE liftM :: (a1->r) -> IO a1 -> IO r #-}
464 {-# INLINEABLE liftM2 #-}
465 {-# SPECIALISE liftM2 :: (a1->a2->r) -> IO a1 -> IO a2 -> IO r #-}
466 {-# INLINEABLE liftM3 #-}
467 {-# SPECIALISE liftM3 :: (a1->a2->a3->r) -> IO a1 -> IO a2 -> IO a3 -> IO r #-}
468 {-# INLINEABLE liftM4 #-}
469 {-# SPECIALISE liftM4 :: (a1->a2->a3->a4->r) -> IO a1 -> IO a2 -> IO a3 -> IO a4 -> IO r #-}
470 {-# INLINEABLE liftM5 #-}
471 {-# SPECIALISE liftM5 :: (a1->a2->a3->a4->a5->r) -> IO a1 -> IO a2 -> IO a3 -> IO a4 -> IO a5 -> IO r #-}
472
473 {- | In many situations, the 'liftM' operations can be replaced by uses of
474 'ap', which promotes function application. 
475
476 >       return f `ap` x1 `ap` ... `ap` xn
477
478 is equivalent to 
479
480 >       liftMn f x1 x2 ... xn
481
482 -}
483
484 ap                :: (Monad m) => m (a -> b) -> m a -> m b
485 ap                =  liftM2 id
486
487 -- instances for Prelude types
488
489 instance Functor ((->) r) where
490     fmap = (.)
491
492 instance Applicative ((->) a) where
493     pure = const
494     (<*>) f g x = f x (g x)
495
496 instance Monad ((->) r) where
497     return = const
498     f >>= k = \ r -> k (f r) r
499
500 instance Functor ((,) a) where
501     fmap f (x,y) = (x, f y)
502
503 \end{code}
504
505
506 %*********************************************************
507 %*                                                      *
508 \subsection{The list type}
509 %*                                                      *
510 %*********************************************************
511
512 \begin{code}
513 instance Functor [] where
514     fmap = map
515
516 instance Applicative [] where
517     pure = return
518     (<*>) = ap
519
520 instance  Monad []  where
521     m >>= k             = foldr ((++) . k) [] m
522     m >> k              = foldr ((++) . (\ _ -> k)) [] m
523     return x            = [x]
524     fail _              = []
525 \end{code}
526
527 A few list functions that appear here because they are used here.
528 The rest of the prelude list functions are in GHC.List.
529
530 ----------------------------------------------
531 --      foldr/build/augment
532 ----------------------------------------------
533
534 \begin{code}
535 -- | 'foldr', applied to a binary operator, a starting value (typically
536 -- the right-identity of the operator), and a list, reduces the list
537 -- using the binary operator, from right to left:
538 --
539 -- > foldr f z [x1, x2, ..., xn] == x1 `f` (x2 `f` ... (xn `f` z)...)
540
541 foldr            :: (a -> b -> b) -> b -> [a] -> b
542 -- foldr _ z []     =  z
543 -- foldr f z (x:xs) =  f x (foldr f z xs)
544 {-# INLINE [0] foldr #-}
545 -- Inline only in the final stage, after the foldr/cons rule has had a chance
546 -- Also note that we inline it when it has *two* parameters, which are the
547 -- ones we are keen about specialising!
548 foldr k z = go
549           where
550             go []     = z
551             go (y:ys) = y `k` go ys
552
553 -- | A list producer that can be fused with 'foldr'.
554 -- This function is merely
555 --
556 -- >    build g = g (:) []
557 --
558 -- but GHC's simplifier will transform an expression of the form
559 -- @'foldr' k z ('build' g)@, which may arise after inlining, to @g k z@,
560 -- which avoids producing an intermediate list.
561
562 build   :: forall a. (forall b. (a -> b -> b) -> b -> b) -> [a]
563 {-# INLINE [1] build #-}
564         -- The INLINE is important, even though build is tiny,
565         -- because it prevents [] getting inlined in the version that
566         -- appears in the interface file.  If [] *is* inlined, it
567         -- won't match with [] appearing in rules in an importing module.
568         --
569         -- The "1" says to inline in phase 1
570
571 build g = g (:) []
572
573 -- | A list producer that can be fused with 'foldr'.
574 -- This function is merely
575 --
576 -- >    augment g xs = g (:) xs
577 --
578 -- but GHC's simplifier will transform an expression of the form
579 -- @'foldr' k z ('augment' g xs)@, which may arise after inlining, to
580 -- @g k ('foldr' k z xs)@, which avoids producing an intermediate list.
581
582 augment :: forall a. (forall b. (a->b->b) -> b -> b) -> [a] -> [a]
583 {-# INLINE [1] augment #-}
584 augment g xs = g (:) xs
585
586 {-# RULES
587 "fold/build"    forall k z (g::forall b. (a->b->b) -> b -> b) .
588                 foldr k z (build g) = g k z
589
590 "foldr/augment" forall k z xs (g::forall b. (a->b->b) -> b -> b) .
591                 foldr k z (augment g xs) = g k (foldr k z xs)
592
593 "foldr/id"                        foldr (:) [] = \x  -> x
594 "foldr/app"     [1] forall ys. foldr (:) ys = \xs -> xs ++ ys
595         -- Only activate this from phase 1, because that's
596         -- when we disable the rule that expands (++) into foldr
597
598 -- The foldr/cons rule looks nice, but it can give disastrously
599 -- bloated code when commpiling
600 --      array (a,b) [(1,2), (2,2), (3,2), ...very long list... ]
601 -- i.e. when there are very very long literal lists
602 -- So I've disabled it for now. We could have special cases
603 -- for short lists, I suppose.
604 -- "foldr/cons" forall k z x xs. foldr k z (x:xs) = k x (foldr k z xs)
605
606 "foldr/single"  forall k z x. foldr k z [x] = k x z
607 "foldr/nil"     forall k z.   foldr k z []  = z
608
609 "augment/build" forall (g::forall b. (a->b->b) -> b -> b)
610                        (h::forall b. (a->b->b) -> b -> b) .
611                        augment g (build h) = build (\c n -> g c (h c n))
612 "augment/nil"   forall (g::forall b. (a->b->b) -> b -> b) .
613                         augment g [] = build g
614  #-}
615
616 -- This rule is true, but not (I think) useful:
617 --      augment g (augment h t) = augment (\cn -> g c (h c n)) t
618 \end{code}
619
620
621 ----------------------------------------------
622 --              map
623 ----------------------------------------------
624
625 \begin{code}
626 -- | 'map' @f xs@ is the list obtained by applying @f@ to each element
627 -- of @xs@, i.e.,
628 --
629 -- > map f [x1, x2, ..., xn] == [f x1, f x2, ..., f xn]
630 -- > map f [x1, x2, ...] == [f x1, f x2, ...]
631
632 map :: (a -> b) -> [a] -> [b]
633 {-# NOINLINE [1] map #-}    -- We want the RULE to fire first.
634                             -- It's recursive, so won't inline anyway,
635                             -- but saying so is more explicit
636 map _ []     = []
637 map f (x:xs) = f x : map f xs
638
639 -- Note eta expanded
640 mapFB ::  (elt -> lst -> lst) -> (a -> elt) -> a -> lst -> lst
641 {-# INLINE [0] mapFB #-}
642 mapFB c f = \x ys -> c (f x) ys
643
644 -- The rules for map work like this.
645 --
646 -- Up to (but not including) phase 1, we use the "map" rule to
647 -- rewrite all saturated applications of map with its build/fold
648 -- form, hoping for fusion to happen.
649 -- In phase 1 and 0, we switch off that rule, inline build, and
650 -- switch on the "mapList" rule, which rewrites the foldr/mapFB
651 -- thing back into plain map.
652 --
653 -- It's important that these two rules aren't both active at once
654 -- (along with build's unfolding) else we'd get an infinite loop
655 -- in the rules.  Hence the activation control below.
656 --
657 -- The "mapFB" rule optimises compositions of map.
658 --
659 -- This same pattern is followed by many other functions:
660 -- e.g. append, filter, iterate, repeat, etc.
661
662 {-# RULES
663 "map"       [~1] forall f xs.   map f xs                = build (\c n -> foldr (mapFB c f) n xs)
664 "mapList"   [1]  forall f.      foldr (mapFB (:) f) []  = map f
665 "mapFB"     forall c f g.       mapFB (mapFB c f) g     = mapFB c (f.g)
666   #-}
667
668 -- There's also a rule for Map and Data.Coerce. See "Safe Coercions",
669 -- section 6.4:
670 --
671 --   http://research.microsoft.com/en-us/um/people/simonpj/papers/ext-f/coercible.pdf
672
673 {-# RULES "map/coerce" [1] map coerce = coerce #-}
674
675 \end{code}
676
677
678 ----------------------------------------------
679 --              append
680 ----------------------------------------------
681 \begin{code}
682 -- | Append two lists, i.e.,
683 --
684 -- > [x1, ..., xm] ++ [y1, ..., yn] == [x1, ..., xm, y1, ..., yn]
685 -- > [x1, ..., xm] ++ [y1, ...] == [x1, ..., xm, y1, ...]
686 --
687 -- If the first list is not finite, the result is the first list.
688
689 (++) :: [a] -> [a] -> [a]
690 {-# NOINLINE [1] (++) #-}    -- We want the RULE to fire first.
691                              -- It's recursive, so won't inline anyway,
692                              -- but saying so is more explicit
693 (++) []     ys = ys
694 (++) (x:xs) ys = x : xs ++ ys
695
696 {-# RULES
697 "++"    [~1] forall xs ys. xs ++ ys = augment (\c n -> foldr c n xs) ys
698   #-}
699
700 \end{code}
701
702
703 %*********************************************************
704 %*                                                      *
705 \subsection{Type @Bool@}
706 %*                                                      *
707 %*********************************************************
708
709 \begin{code}
710 -- |'otherwise' is defined as the value 'True'.  It helps to make
711 -- guards more readable.  eg.
712 --
713 -- >  f x | x < 0     = ...
714 -- >      | otherwise = ...
715 otherwise               :: Bool
716 otherwise               =  True
717 \end{code}
718
719 %*********************************************************
720 %*                                                      *
721 \subsection{Type @Char@ and @String@}
722 %*                                                      *
723 %*********************************************************
724
725 \begin{code}
726 -- | A 'String' is a list of characters.  String constants in Haskell are values
727 -- of type 'String'.
728 --
729 type String = [Char]
730
731 unsafeChr :: Int -> Char
732 unsafeChr (I# i#) = C# (chr# i#)
733
734 -- | The 'Prelude.fromEnum' method restricted to the type 'Data.Char.Char'.
735 ord :: Char -> Int
736 ord (C# c#) = I# (ord# c#)
737 \end{code}
738
739 String equality is used when desugaring pattern-matches against strings.
740
741 \begin{code}
742 eqString :: String -> String -> Bool
743 eqString []       []       = True
744 eqString (c1:cs1) (c2:cs2) = c1 == c2 && cs1 `eqString` cs2
745 eqString _        _        = False
746
747 {-# RULES "eqString" (==) = eqString #-}
748 -- eqString also has a BuiltInRule in PrelRules.lhs:
749 --      eqString (unpackCString# (Lit s1)) (unpackCString# (Lit s2) = s1==s2
750 \end{code}
751
752
753 %*********************************************************
754 %*                                                      *
755 \subsection{Type @Int@}
756 %*                                                      *
757 %*********************************************************
758
759 \begin{code}
760 maxInt, minInt :: Int
761
762 {- Seems clumsy. Should perhaps put minInt and MaxInt directly into MachDeps.h -}
763 #if WORD_SIZE_IN_BITS == 31
764 minInt  = I# (-0x40000000#)
765 maxInt  = I# 0x3FFFFFFF#
766 #elif WORD_SIZE_IN_BITS == 32
767 minInt  = I# (-0x80000000#)
768 maxInt  = I# 0x7FFFFFFF#
769 #else
770 minInt  = I# (-0x8000000000000000#)
771 maxInt  = I# 0x7FFFFFFFFFFFFFFF#
772 #endif
773 \end{code}
774
775
776 %*********************************************************
777 %*                                                      *
778 \subsection{The function type}
779 %*                                                      *
780 %*********************************************************
781
782 \begin{code}
783 -- | Identity function.
784 id                      :: a -> a
785 id x                    =  x
786
787 -- Assertion function.  This simply ignores its boolean argument.
788 -- The compiler may rewrite it to @('assertError' line)@.
789
790 -- | If the first argument evaluates to 'True', then the result is the
791 -- second argument.  Otherwise an 'AssertionFailed' exception is raised,
792 -- containing a 'String' with the source file and line number of the
793 -- call to 'assert'.
794 --
795 -- Assertions can normally be turned on or off with a compiler flag
796 -- (for GHC, assertions are normally on unless optimisation is turned on
797 -- with @-O@ or the @-fignore-asserts@
798 -- option is given).  When assertions are turned off, the first
799 -- argument to 'assert' is ignored, and the second argument is
800 -- returned as the result.
801
802 --      SLPJ: in 5.04 etc 'assert' is in GHC.Prim,
803 --      but from Template Haskell onwards it's simply
804 --      defined here in Base.lhs
805 assert :: Bool -> a -> a
806 assert _pred r = r
807
808 breakpoint :: a -> a
809 breakpoint r = r
810
811 breakpointCond :: Bool -> a -> a
812 breakpointCond _ r = r
813
814 data Opaque = forall a. O a
815
816 -- | Constant function.
817 const                   :: a -> b -> a
818 const x _               =  x
819
820 -- | Function composition.
821 {-# INLINE (.) #-}
822 -- Make sure it has TWO args only on the left, so that it inlines
823 -- when applied to two functions, even if there is no final argument
824 (.)    :: (b -> c) -> (a -> b) -> a -> c
825 (.) f g = \x -> f (g x)
826
827 -- | @'flip' f@ takes its (first) two arguments in the reverse order of @f@.
828 flip                    :: (a -> b -> c) -> b -> a -> c
829 flip f x y              =  f y x
830
831 -- | Application operator.  This operator is redundant, since ordinary
832 -- application @(f x)@ means the same as @(f '$' x)@. However, '$' has
833 -- low, right-associative binding precedence, so it sometimes allows
834 -- parentheses to be omitted; for example:
835 --
836 -- >     f $ g $ h x  =  f (g (h x))
837 --
838 -- It is also useful in higher-order situations, such as @'map' ('$' 0) xs@,
839 -- or @'Data.List.zipWith' ('$') fs xs@.
840 {-# INLINE ($) #-}
841 ($)                     :: (a -> b) -> a -> b
842 f $ x                   =  f x
843
844 -- | @'until' p f@ yields the result of applying @f@ until @p@ holds.
845 until                   :: (a -> Bool) -> (a -> a) -> a -> a
846 until p f = go
847   where
848     go x | p x          = x
849          | otherwise    = go (f x)
850
851 -- | 'asTypeOf' is a type-restricted version of 'const'.  It is usually
852 -- used as an infix operator, and its typing forces its first argument
853 -- (which is usually overloaded) to have the same type as the second.
854 asTypeOf                :: a -> a -> a
855 asTypeOf                =  const
856 \end{code}
857
858 %*********************************************************
859 %*                                                      *
860 \subsection{@Functor@ and @Monad@ instances for @IO@}
861 %*                                                      *
862 %*********************************************************
863
864 \begin{code}
865 instance  Functor IO where
866    fmap f x = x >>= (return . f)
867
868 instance Applicative IO where
869     pure = return
870     (<*>) = ap
871
872 instance  Monad IO  where
873     {-# INLINE return #-}
874     {-# INLINE (>>)   #-}
875     {-# INLINE (>>=)  #-}
876     m >> k    = m >>= \ _ -> k
877     return    = returnIO
878     (>>=)     = bindIO
879     fail s    = failIO s
880
881 returnIO :: a -> IO a
882 returnIO x = IO $ \ s -> (# s, x #)
883
884 bindIO :: IO a -> (a -> IO b) -> IO b
885 bindIO (IO m) k = IO $ \ s -> case m s of (# new_s, a #) -> unIO (k a) new_s
886
887 thenIO :: IO a -> IO b -> IO b
888 thenIO (IO m) k = IO $ \ s -> case m s of (# new_s, _ #) -> unIO k new_s
889
890 unIO :: IO a -> (State# RealWorld -> (# State# RealWorld, a #))
891 unIO (IO a) = a
892 \end{code}
893
894 %*********************************************************
895 %*                                                      *
896 \subsection{@getTag@}
897 %*                                                      *
898 %*********************************************************
899
900 Returns the 'tag' of a constructor application; this function is used
901 by the deriving code for Eq, Ord and Enum.
902
903 The primitive dataToTag# requires an evaluated constructor application
904 as its argument, so we provide getTag as a wrapper that performs the
905 evaluation before calling dataToTag#.  We could have dataToTag#
906 evaluate its argument, but we prefer to do it this way because (a)
907 dataToTag# can be an inline primop if it doesn't need to do any
908 evaluation, and (b) we want to expose the evaluation to the
909 simplifier, because it might be possible to eliminate the evaluation
910 in the case when the argument is already known to be evaluated.
911
912 \begin{code}
913 {-# INLINE getTag #-}
914 getTag :: a -> Int#
915 getTag x = x `seq` dataToTag# x
916 \end{code}
917
918 %*********************************************************
919 %*                                                      *
920 \subsection{Numeric primops}
921 %*                                                      *
922 %*********************************************************
923
924 Definitions of the boxed PrimOps; these will be
925 used in the case of partial applications, etc.
926
927 \begin{code}
928 {-# INLINE quotInt #-}
929 {-# INLINE remInt #-}
930
931 quotInt, remInt, divInt, modInt :: Int -> Int -> Int
932 (I# x) `quotInt`  (I# y) = I# (x `quotInt#` y)
933 (I# x) `remInt`   (I# y) = I# (x `remInt#`  y)
934 (I# x) `divInt`   (I# y) = I# (x `divInt#`  y)
935 (I# x) `modInt`   (I# y) = I# (x `modInt#`  y)
936
937 quotRemInt :: Int -> Int -> (Int, Int)
938 (I# x) `quotRemInt` (I# y) = case x `quotRemInt#` y of
939                              (# q, r #) ->
940                                  (I# q, I# r)
941
942 divModInt :: Int -> Int -> (Int, Int)
943 (I# x) `divModInt` (I# y) = case x `divModInt#` y of
944                             (# q, r #) -> (I# q, I# r)
945
946 divModInt# :: Int# -> Int# -> (# Int#, Int# #)
947 x# `divModInt#` y#
948  | isTrue# (x# ># 0#) && isTrue# (y# <# 0#) =
949                                     case (x# -# 1#) `quotRemInt#` y# of
950                                       (# q, r #) -> (# q -# 1#, r +# y# +# 1# #)
951  | isTrue# (x# <# 0#) && isTrue# (y# ># 0#) =
952                                     case (x# +# 1#) `quotRemInt#` y# of
953                                       (# q, r #) -> (# q -# 1#, r +# y# -# 1# #)
954  | otherwise                                =
955                                     x# `quotRemInt#` y#
956
957 -- Wrappers for the shift operations.  The uncheckedShift# family are
958 -- undefined when the amount being shifted by is greater than the size
959 -- in bits of Int#, so these wrappers perform a check and return
960 -- either zero or -1 appropriately.
961 --
962 -- Note that these wrappers still produce undefined results when the
963 -- second argument (the shift amount) is negative.
964
965 -- | Shift the argument left by the specified number of bits
966 -- (which must be non-negative).
967 shiftL# :: Word# -> Int# -> Word#
968 a `shiftL#` b   | isTrue# (b >=# WORD_SIZE_IN_BITS#) = 0##
969                 | otherwise                          = a `uncheckedShiftL#` b
970
971 -- | Shift the argument right by the specified number of bits
972 -- (which must be non-negative).
973 -- The "RL" means "right, logical" (as opposed to RA for arithmetic)
974 -- (although an arithmetic right shift wouldn't make sense for Word#)
975 shiftRL# :: Word# -> Int# -> Word#
976 a `shiftRL#` b  | isTrue# (b >=# WORD_SIZE_IN_BITS#) = 0##
977                 | otherwise                          = a `uncheckedShiftRL#` b
978
979 -- | Shift the argument left by the specified number of bits
980 -- (which must be non-negative).
981 iShiftL# :: Int# -> Int# -> Int#
982 a `iShiftL#` b  | isTrue# (b >=# WORD_SIZE_IN_BITS#) = 0#
983                 | otherwise                          = a `uncheckedIShiftL#` b
984
985 -- | Shift the argument right (signed) by the specified number of bits
986 -- (which must be non-negative).
987 -- The "RA" means "right, arithmetic" (as opposed to RL for logical)
988 iShiftRA# :: Int# -> Int# -> Int#
989 a `iShiftRA#` b | isTrue# (b >=# WORD_SIZE_IN_BITS#) = if isTrue# (a <# 0#)
990                                                           then (-1#)
991                                                           else 0#
992                 | otherwise                          = a `uncheckedIShiftRA#` b
993
994 -- | Shift the argument right (unsigned) by the specified number of bits
995 -- (which must be non-negative).
996 -- The "RL" means "right, logical" (as opposed to RA for arithmetic)
997 iShiftRL# :: Int# -> Int# -> Int#
998 a `iShiftRL#` b | isTrue# (b >=# WORD_SIZE_IN_BITS#) = 0#
999                 | otherwise                          = a `uncheckedIShiftRL#` b
1000
1001 -- Rules for C strings (the functions themselves are now in GHC.CString)
1002 {-# RULES
1003 "unpack"       [~1] forall a   . unpackCString# a             = build (unpackFoldrCString# a)
1004 "unpack-list"  [1]  forall a   . unpackFoldrCString# a (:) [] = unpackCString# a
1005 "unpack-append"     forall a n . unpackFoldrCString# a (:) n  = unpackAppendCString# a n
1006
1007 -- There's a built-in rule (in PrelRules.lhs) for
1008 --      unpackFoldr "foo" c (unpackFoldr "baz" c n)  =  unpackFoldr "foobaz" c n
1009
1010   #-}
1011 \end{code}
1012
1013
1014 #ifdef __HADDOCK__
1015 \begin{code}
1016 -- | A special argument for the 'Control.Monad.ST.ST' type constructor,
1017 -- indexing a state embedded in the 'Prelude.IO' monad by
1018 -- 'Control.Monad.ST.stToIO'.
1019 data RealWorld
1020 \end{code}
1021 #endif