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