Built-in Natural literals in Core
[ghc.git] / libraries / base / GHC / Base.hs
1 {-
2
3 NOTA BENE: Do NOT use ($) anywhere in this module! The type of ($) is
4 slightly magical (it can return unlifted types), and it is wired in.
5 But, it is also *defined* in this module, with a non-magical type.
6 GHC gets terribly confused (and *hangs*) if you try to use ($) in this
7 module, because it has different types in different scenarios.
8
9 This is not a problem in general, because the type ($), being wired in, is not
10 written out to the interface file, so importing files don't get confused.
11 The problem is only if ($) is used here. So don't!
12
13 ---------------------------------------------
14
15 The overall structure of the GHC Prelude is a bit tricky.
16
17 a) We want to avoid "orphan modules", i.e. ones with instance
18 decls that don't belong either to a tycon or a class
19 defined in the same module
20
21 b) We want to avoid giant modules
22
23 So the rough structure is as follows, in (linearised) dependency order
24
25
26 GHC.Prim Has no implementation. It defines built-in things, and
27 by importing it you bring them into scope.
28 The source file is GHC.Prim.hi-boot, which is just
29 copied to make GHC.Prim.hi
30
31 GHC.Base Classes: Eq, Ord, Functor, Monad
32 Types: list, (), Int, Bool, Ordering, Char, String
33
34 Data.Tuple Types: tuples, plus instances for GHC.Base classes
35
36 GHC.Show Class: Show, plus instances for GHC.Base/GHC.Tup types
37
38 GHC.Enum Class: Enum, plus instances for GHC.Base/GHC.Tup types
39
40 Data.Maybe Type: Maybe, plus instances for GHC.Base classes
41
42 GHC.List List functions
43
44 GHC.Num Class: Num, plus instances for Int
45 Type: Integer, plus instances for all classes so far (Eq, Ord, Num, Show)
46
47 Integer is needed here because it is mentioned in the signature
48 of 'fromInteger' in class Num
49
50 GHC.Real Classes: Real, Integral, Fractional, RealFrac
51 plus instances for Int, Integer
52 Types: Ratio, Rational
53 plus instances for classes so far
54
55 Rational is needed here because it is mentioned in the signature
56 of 'toRational' in class Real
57
58 GHC.ST The ST monad, instances and a few helper functions
59
60 Ix Classes: Ix, plus instances for Int, Bool, Char, Integer, Ordering, tuples
61
62 GHC.Arr Types: Array, MutableArray, MutableVar
63
64 Arrays are used by a function in GHC.Float
65
66 GHC.Float Classes: Floating, RealFloat
67 Types: Float, Double, plus instances of all classes so far
68
69 This module contains everything to do with floating point.
70 It is a big module (900 lines)
71 With a bit of luck, many modules can be compiled without ever reading GHC.Float.hi
72
73
74 Other Prelude modules are much easier with fewer complex dependencies.
75 -}
76
77 {-# LANGUAGE Unsafe #-}
78 {-# LANGUAGE CPP
79 , NoImplicitPrelude
80 , BangPatterns
81 , ExplicitForAll
82 , MagicHash
83 , UnboxedTuples
84 , ExistentialQuantification
85 , RankNTypes
86 , KindSignatures
87 , PolyKinds
88 , DataKinds
89 #-}
90 -- -Wno-orphans is needed for things like:
91 -- Orphan rule: "x# -# x#" ALWAYS forall x# :: Int# -# x# x# = 0
92 {-# OPTIONS_GHC -Wno-orphans #-}
93 {-# OPTIONS_HADDOCK hide #-}
94
95 -----------------------------------------------------------------------------
96 -- |
97 -- Module : GHC.Base
98 -- Copyright : (c) The University of Glasgow, 1992-2002
99 -- License : see libraries/base/LICENSE
100 --
101 -- Maintainer : cvs-ghc@haskell.org
102 -- Stability : internal
103 -- Portability : non-portable (GHC extensions)
104 --
105 -- Basic data types and classes.
106 --
107 -----------------------------------------------------------------------------
108
109 #include "MachDeps.h"
110
111 module GHC.Base
112 (
113 module GHC.Base,
114 module GHC.Classes,
115 module GHC.CString,
116 module GHC.Magic,
117 module GHC.Types,
118 module GHC.Prim, -- Re-export GHC.Prim and [boot] GHC.Err,
119 -- to avoid lots of people having to
120 module GHC.Err, -- import it explicitly
121 module GHC.Maybe
122 )
123 where
124
125 import GHC.Types
126 import GHC.Classes
127 import GHC.CString
128 import GHC.Magic
129 import GHC.Prim
130 import GHC.Err
131 import GHC.Maybe
132 import {-# SOURCE #-} GHC.IO (failIO,mplusIO)
133
134 import GHC.Tuple () -- Note [Depend on GHC.Tuple]
135 import GHC.Integer () -- Note [Depend on GHC.Integer]
136 import GHC.Natural () -- Note [Depend on GHC.Natural]
137
138 -- for 'class Semigroup'
139 import {-# SOURCE #-} GHC.Real (Integral)
140 import {-# SOURCE #-} Data.Semigroup.Internal ( stimesDefault
141 , stimesMaybe
142 , stimesList
143 , stimesIdempotentMonoid
144 )
145
146 infixr 9 .
147 infixr 5 ++
148 infixl 4 <$
149 infixl 1 >>, >>=
150 infixr 1 =<<
151 infixr 0 $, $!
152
153 infixl 4 <*>, <*, *>, <**>
154
155 default () -- Double isn't available yet
156
157 {-
158 Note [Depend on GHC.Integer]
159 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~
160 The Integer type is special because TidyPgm uses
161 GHC.Integer.Type.mkInteger to construct Integer literal values
162 Currently it reads the interface file whether or not the current
163 module *has* any Integer literals, so it's important that
164 GHC.Integer.Type (in package integer-gmp or integer-simple) is
165 compiled before any other module. (There's a hack in GHC to disable
166 this for packages ghc-prim, integer-gmp, integer-simple, which aren't
167 allowed to contain any Integer literals.)
168
169 Likewise we implicitly need Integer when deriving things like Eq
170 instances.
171
172 The danger is that if the build system doesn't know about the dependency
173 on Integer, it'll compile some base module before GHC.Integer.Type,
174 resulting in:
175 Failed to load interface for ‘GHC.Integer.Type’
176 There are files missing in the ‘integer-gmp’ package,
177
178 Bottom line: we make GHC.Base depend on GHC.Integer; and everything
179 else either depends on GHC.Base, or does not have NoImplicitPrelude
180 (and hence depends on Prelude).
181
182 Note [Depend on GHC.Tuple]
183 ~~~~~~~~~~~~~~~~~~~~~~~~~~
184 Similarly, tuple syntax (or ()) creates an implicit dependency on
185 GHC.Tuple, so we use the same rule as for Integer --- see Note [Depend on
186 GHC.Integer] --- to explain this to the build system. We make GHC.Base
187 depend on GHC.Tuple, and everything else depends on GHC.Base or Prelude.
188
189 Note [Depend on GHC.Natural]
190 ~~~~~~~~~~~~~~~~~~~~~~~~~~
191 Similar to GHC.Integer.
192 -}
193
194 #if 0
195 -- for use when compiling GHC.Base itself doesn't work
196 data Bool = False | True
197 data Ordering = LT | EQ | GT
198 data Char = C# Char#
199 type String = [Char]
200 data Int = I# Int#
201 data () = ()
202 data [] a = MkNil
203
204 not True = False
205 (&&) True True = True
206 otherwise = True
207
208 build = errorWithoutStackTrace "urk"
209 foldr = errorWithoutStackTrace "urk"
210 #endif
211
212 infixr 6 <>
213
214 -- | The class of semigroups (types with an associative binary operation).
215 --
216 -- Instances should satisfy the associativity law:
217 --
218 -- * @x '<>' (y '<>' z) = (x '<>' y) '<>' z@
219 --
220 -- @since 4.9.0.0
221 class Semigroup a where
222 -- | An associative operation.
223 (<>) :: a -> a -> a
224
225 -- | Reduce a non-empty list with @\<\>@
226 --
227 -- The default definition should be sufficient, but this can be
228 -- overridden for efficiency.
229 --
230 sconcat :: NonEmpty a -> a
231 sconcat (a :| as) = go a as where
232 go b (c:cs) = b <> go c cs
233 go b [] = b
234
235 -- | Repeat a value @n@ times.
236 --
237 -- Given that this works on a 'Semigroup' it is allowed to fail if
238 -- you request 0 or fewer repetitions, and the default definition
239 -- will do so.
240 --
241 -- By making this a member of the class, idempotent semigroups
242 -- and monoids can upgrade this to execute in /O(1)/ by
243 -- picking @stimes = 'stimesIdempotent'@ or @stimes =
244 -- 'stimesIdempotentMonoid'@ respectively.
245 stimes :: Integral b => b -> a -> a
246 stimes = stimesDefault
247
248
249 -- | The class of monoids (types with an associative binary operation that
250 -- has an identity). Instances should satisfy the following laws:
251 --
252 -- * @x '<>' 'mempty' = x@
253 --
254 -- * @'mempty' '<>' x = x@
255 --
256 -- * @x '<>' (y '<>' z) = (x '<>' y) '<>' z@ ('Semigroup' law)
257 --
258 -- * @'mconcat' = 'foldr' '(<>)' 'mempty'@
259 --
260 -- The method names refer to the monoid of lists under concatenation,
261 -- but there are many other instances.
262 --
263 -- Some types can be viewed as a monoid in more than one way,
264 -- e.g. both addition and multiplication on numbers.
265 -- In such cases we often define @newtype@s and make those instances
266 -- of 'Monoid', e.g. 'Sum' and 'Product'.
267 --
268 -- __NOTE__: 'Semigroup' is a superclass of 'Monoid' since /base-4.11.0.0/.
269 class Semigroup a => Monoid a where
270 -- | Identity of 'mappend'
271 mempty :: a
272
273 -- | An associative operation
274 --
275 -- __NOTE__: This method is redundant and has the default
276 -- implementation @'mappend' = '(<>)'@ since /base-4.11.0.0/.
277 mappend :: a -> a -> a
278 mappend = (<>)
279 {-# INLINE mappend #-}
280
281 -- | Fold a list using the monoid.
282 --
283 -- For most types, the default definition for 'mconcat' will be
284 -- used, but the function is included in the class definition so
285 -- that an optimized version can be provided for specific types.
286 mconcat :: [a] -> a
287 mconcat = foldr mappend mempty
288
289 -- | @since 4.9.0.0
290 instance Semigroup [a] where
291 (<>) = (++)
292 {-# INLINE (<>) #-}
293
294 stimes = stimesList
295
296 -- | @since 2.01
297 instance Monoid [a] where
298 {-# INLINE mempty #-}
299 mempty = []
300 {-# INLINE mconcat #-}
301 mconcat xss = [x | xs <- xss, x <- xs]
302 -- See Note: [List comprehensions and inlining]
303
304 {-
305 Note: [List comprehensions and inlining]
306 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
307 The list monad operations are traditionally described in terms of concatMap:
308
309 xs >>= f = concatMap f xs
310
311 Similarly, mconcat for lists is just concat. Here in Base, however, we don't
312 have concatMap, and we'll refrain from adding it here so it won't have to be
313 hidden in imports. Instead, we use GHC's list comprehension desugaring
314 mechanism to define mconcat and the Applicative and Monad instances for lists.
315 We mark them INLINE because the inliner is not generally too keen to inline
316 build forms such as the ones these desugar to without our insistence. Defining
317 these using list comprehensions instead of foldr has an additional potential
318 benefit, as described in compiler/deSugar/DsListComp.hs: if optimizations
319 needed to make foldr/build forms efficient are turned off, we'll get reasonably
320 efficient translations anyway.
321 -}
322
323 -- | @since 4.9.0.0
324 instance Semigroup (NonEmpty a) where
325 (a :| as) <> ~(b :| bs) = a :| (as ++ b : bs)
326
327 -- | @since 4.9.0.0
328 instance Semigroup b => Semigroup (a -> b) where
329 f <> g = \x -> f x <> g x
330 stimes n f e = stimes n (f e)
331
332 -- | @since 2.01
333 instance Monoid b => Monoid (a -> b) where
334 mempty _ = mempty
335
336 -- | @since 4.9.0.0
337 instance Semigroup () where
338 _ <> _ = ()
339 sconcat _ = ()
340 stimes _ _ = ()
341
342 -- | @since 2.01
343 instance Monoid () where
344 -- Should it be strict?
345 mempty = ()
346 mconcat _ = ()
347
348 -- | @since 4.9.0.0
349 instance (Semigroup a, Semigroup b) => Semigroup (a, b) where
350 (a,b) <> (a',b') = (a<>a',b<>b')
351 stimes n (a,b) = (stimes n a, stimes n b)
352
353 -- | @since 2.01
354 instance (Monoid a, Monoid b) => Monoid (a,b) where
355 mempty = (mempty, mempty)
356
357 -- | @since 4.9.0.0
358 instance (Semigroup a, Semigroup b, Semigroup c) => Semigroup (a, b, c) where
359 (a,b,c) <> (a',b',c') = (a<>a',b<>b',c<>c')
360 stimes n (a,b,c) = (stimes n a, stimes n b, stimes n c)
361
362 -- | @since 2.01
363 instance (Monoid a, Monoid b, Monoid c) => Monoid (a,b,c) where
364 mempty = (mempty, mempty, mempty)
365
366 -- | @since 4.9.0.0
367 instance (Semigroup a, Semigroup b, Semigroup c, Semigroup d)
368 => Semigroup (a, b, c, d) where
369 (a,b,c,d) <> (a',b',c',d') = (a<>a',b<>b',c<>c',d<>d')
370 stimes n (a,b,c,d) = (stimes n a, stimes n b, stimes n c, stimes n d)
371
372 -- | @since 2.01
373 instance (Monoid a, Monoid b, Monoid c, Monoid d) => Monoid (a,b,c,d) where
374 mempty = (mempty, mempty, mempty, mempty)
375
376 -- | @since 4.9.0.0
377 instance (Semigroup a, Semigroup b, Semigroup c, Semigroup d, Semigroup e)
378 => Semigroup (a, b, c, d, e) where
379 (a,b,c,d,e) <> (a',b',c',d',e') = (a<>a',b<>b',c<>c',d<>d',e<>e')
380 stimes n (a,b,c,d,e) =
381 (stimes n a, stimes n b, stimes n c, stimes n d, stimes n e)
382
383 -- | @since 2.01
384 instance (Monoid a, Monoid b, Monoid c, Monoid d, Monoid e) =>
385 Monoid (a,b,c,d,e) where
386 mempty = (mempty, mempty, mempty, mempty, mempty)
387
388
389 -- | @since 4.9.0.0
390 instance Semigroup Ordering where
391 LT <> _ = LT
392 EQ <> y = y
393 GT <> _ = GT
394
395 stimes = stimesIdempotentMonoid
396
397 -- lexicographical ordering
398 -- | @since 2.01
399 instance Monoid Ordering where
400 mempty = EQ
401
402 -- | @since 4.9.0.0
403 instance Semigroup a => Semigroup (Maybe a) where
404 Nothing <> b = b
405 a <> Nothing = a
406 Just a <> Just b = Just (a <> b)
407
408 stimes = stimesMaybe
409
410 -- | Lift a semigroup into 'Maybe' forming a 'Monoid' according to
411 -- <http://en.wikipedia.org/wiki/Monoid>: \"Any semigroup @S@ may be
412 -- turned into a monoid simply by adjoining an element @e@ not in @S@
413 -- and defining @e*e = e@ and @e*s = s = s*e@ for all @s ∈ S@.\"
414 --
415 -- /Since 4.11.0/: constraint on inner @a@ value generalised from
416 -- 'Monoid' to 'Semigroup'.
417 --
418 -- @since 2.01
419 instance Semigroup a => Monoid (Maybe a) where
420 mempty = Nothing
421
422 -- | For tuples, the 'Monoid' constraint on @a@ determines
423 -- how the first values merge.
424 -- For example, 'String's concatenate:
425 --
426 -- > ("hello ", (+15)) <*> ("world!", 2002)
427 -- > ("hello world!",2017)
428 --
429 -- @since 2.01
430 instance Monoid a => Applicative ((,) a) where
431 pure x = (mempty, x)
432 (u, f) <*> (v, x) = (u <> v, f x)
433 liftA2 f (u, x) (v, y) = (u <> v, f x y)
434
435 -- | @since 4.9.0.0
436 instance Monoid a => Monad ((,) a) where
437 (u, a) >>= k = case k a of (v, b) -> (u <> v, b)
438
439 -- | @since 4.10.0.0
440 instance Semigroup a => Semigroup (IO a) where
441 (<>) = liftA2 (<>)
442
443 -- | @since 4.9.0.0
444 instance Monoid a => Monoid (IO a) where
445 mempty = pure mempty
446
447 {- | The 'Functor' class is used for types that can be mapped over.
448 Instances of 'Functor' should satisfy the following laws:
449
450 > fmap id == id
451 > fmap (f . g) == fmap f . fmap g
452
453 The instances of 'Functor' for lists, 'Data.Maybe.Maybe' and 'System.IO.IO'
454 satisfy these laws.
455 -}
456
457 class Functor f where
458 fmap :: (a -> b) -> f a -> f b
459
460 -- | Replace all locations in the input with the same value.
461 -- The default definition is @'fmap' . 'const'@, but this may be
462 -- overridden with a more efficient version.
463 (<$) :: a -> f b -> f a
464 (<$) = fmap . const
465
466 -- | A functor with application, providing operations to
467 --
468 -- * embed pure expressions ('pure'), and
469 --
470 -- * sequence computations and combine their results ('<*>' and 'liftA2').
471 --
472 -- A minimal complete definition must include implementations of 'pure'
473 -- and of either '<*>' or 'liftA2'. If it defines both, then they must behave
474 -- the same as their default definitions:
475 --
476 -- @('<*>') = 'liftA2' 'id'@
477 --
478 -- @'liftA2' f x y = f '<$>' x '<*>' y@
479 --
480 -- Further, any definition must satisfy the following:
481 --
482 -- [/identity/]
483 --
484 -- @'pure' 'id' '<*>' v = v@
485 --
486 -- [/composition/]
487 --
488 -- @'pure' (.) '<*>' u '<*>' v '<*>' w = u '<*>' (v '<*>' w)@
489 --
490 -- [/homomorphism/]
491 --
492 -- @'pure' f '<*>' 'pure' x = 'pure' (f x)@
493 --
494 -- [/interchange/]
495 --
496 -- @u '<*>' 'pure' y = 'pure' ('$' y) '<*>' u@
497 --
498 --
499 -- The other methods have the following default definitions, which may
500 -- be overridden with equivalent specialized implementations:
501 --
502 -- * @u '*>' v = ('id' '<$' u) '<*>' v@
503 --
504 -- * @u '<*' v = 'liftA2' 'const' u v@
505 --
506 -- As a consequence of these laws, the 'Functor' instance for @f@ will satisfy
507 --
508 -- * @'fmap' f x = 'pure' f '<*>' x@
509 --
510 --
511 -- It may be useful to note that supposing
512 --
513 -- @forall x y. p (q x y) = f x . g y@
514 --
515 -- it follows from the above that
516 --
517 -- @'liftA2' p ('liftA2' q u v) = 'liftA2' f u . 'liftA2' g v@
518 --
519 --
520 -- If @f@ is also a 'Monad', it should satisfy
521 --
522 -- * @'pure' = 'return'@
523 --
524 -- * @('<*>') = 'ap'@
525 --
526 -- * @('*>') = ('>>')@
527 --
528 -- (which implies that 'pure' and '<*>' satisfy the applicative functor laws).
529
530 class Functor f => Applicative f where
531 {-# MINIMAL pure, ((<*>) | liftA2) #-}
532 -- | Lift a value.
533 pure :: a -> f a
534
535 -- | Sequential application.
536 --
537 -- A few functors support an implementation of '<*>' that is more
538 -- efficient than the default one.
539 (<*>) :: f (a -> b) -> f a -> f b
540 (<*>) = liftA2 id
541
542 -- | Lift a binary function to actions.
543 --
544 -- Some functors support an implementation of 'liftA2' that is more
545 -- efficient than the default one. In particular, if 'fmap' is an
546 -- expensive operation, it is likely better to use 'liftA2' than to
547 -- 'fmap' over the structure and then use '<*>'.
548 liftA2 :: (a -> b -> c) -> f a -> f b -> f c
549 liftA2 f x = (<*>) (fmap f x)
550
551 -- | Sequence actions, discarding the value of the first argument.
552 (*>) :: f a -> f b -> f b
553 a1 *> a2 = (id <$ a1) <*> a2
554 -- This is essentially the same as liftA2 (flip const), but if the
555 -- Functor instance has an optimized (<$), it may be better to use
556 -- that instead. Before liftA2 became a method, this definition
557 -- was strictly better, but now it depends on the functor. For a
558 -- functor supporting a sharing-enhancing (<$), this definition
559 -- may reduce allocation by preventing a1 from ever being fully
560 -- realized. In an implementation with a boring (<$) but an optimizing
561 -- liftA2, it would likely be better to define (*>) using liftA2.
562
563 -- | Sequence actions, discarding the value of the second argument.
564 (<*) :: f a -> f b -> f a
565 (<*) = liftA2 const
566
567 -- | A variant of '<*>' with the arguments reversed.
568 (<**>) :: Applicative f => f a -> f (a -> b) -> f b
569 (<**>) = liftA2 (\a f -> f a)
570 -- Don't use $ here, see the note at the top of the page
571
572 -- | Lift a function to actions.
573 -- This function may be used as a value for `fmap` in a `Functor` instance.
574 liftA :: Applicative f => (a -> b) -> f a -> f b
575 liftA f a = pure f <*> a
576 -- Caution: since this may be used for `fmap`, we can't use the obvious
577 -- definition of liftA = fmap.
578
579 -- | Lift a ternary function to actions.
580 liftA3 :: Applicative f => (a -> b -> c -> d) -> f a -> f b -> f c -> f d
581 liftA3 f a b c = liftA2 f a b <*> c
582
583
584 {-# INLINABLE liftA #-}
585 {-# SPECIALISE liftA :: (a1->r) -> IO a1 -> IO r #-}
586 {-# SPECIALISE liftA :: (a1->r) -> Maybe a1 -> Maybe r #-}
587 {-# INLINABLE liftA3 #-}
588 {-# SPECIALISE liftA3 :: (a1->a2->a3->r) -> IO a1 -> IO a2 -> IO a3 -> IO r #-}
589 {-# SPECIALISE liftA3 :: (a1->a2->a3->r) ->
590 Maybe a1 -> Maybe a2 -> Maybe a3 -> Maybe r #-}
591
592 -- | The 'join' function is the conventional monad join operator. It
593 -- is used to remove one level of monadic structure, projecting its
594 -- bound argument into the outer level.
595 --
596 -- ==== __Examples__
597 --
598 -- A common use of 'join' is to run an 'IO' computation returned from
599 -- an 'GHC.Conc.STM' transaction, since 'GHC.Conc.STM' transactions
600 -- can't perform 'IO' directly. Recall that
601 --
602 -- @
603 -- 'GHC.Conc.atomically' :: STM a -> IO a
604 -- @
605 --
606 -- is used to run 'GHC.Conc.STM' transactions atomically. So, by
607 -- specializing the types of 'GHC.Conc.atomically' and 'join' to
608 --
609 -- @
610 -- 'GHC.Conc.atomically' :: STM (IO b) -> IO (IO b)
611 -- 'join' :: IO (IO b) -> IO b
612 -- @
613 --
614 -- we can compose them as
615 --
616 -- @
617 -- 'join' . 'GHC.Conc.atomically' :: STM (IO b) -> IO b
618 -- @
619 --
620 -- to run an 'GHC.Conc.STM' transaction and the 'IO' action it
621 -- returns.
622 join :: (Monad m) => m (m a) -> m a
623 join x = x >>= id
624
625 {- | The 'Monad' class defines the basic operations over a /monad/,
626 a concept from a branch of mathematics known as /category theory/.
627 From the perspective of a Haskell programmer, however, it is best to
628 think of a monad as an /abstract datatype/ of actions.
629 Haskell's @do@ expressions provide a convenient syntax for writing
630 monadic expressions.
631
632 Instances of 'Monad' should satisfy the following laws:
633
634 * @'return' a '>>=' k = k a@
635 * @m '>>=' 'return' = m@
636 * @m '>>=' (\\x -> k x '>>=' h) = (m '>>=' k) '>>=' h@
637
638 Furthermore, the 'Monad' and 'Applicative' operations should relate as follows:
639
640 * @'pure' = 'return'@
641 * @('<*>') = 'ap'@
642
643 The above laws imply:
644
645 * @'fmap' f xs = xs '>>=' 'return' . f@
646 * @('>>') = ('*>')@
647
648 and that 'pure' and ('<*>') satisfy the applicative functor laws.
649
650 The instances of 'Monad' for lists, 'Data.Maybe.Maybe' and 'System.IO.IO'
651 defined in the "Prelude" satisfy these laws.
652 -}
653 class Applicative m => Monad m where
654 -- | Sequentially compose two actions, passing any value produced
655 -- by the first as an argument to the second.
656 (>>=) :: forall a b. m a -> (a -> m b) -> m b
657
658 -- | Sequentially compose two actions, discarding any value produced
659 -- by the first, like sequencing operators (such as the semicolon)
660 -- in imperative languages.
661 (>>) :: forall a b. m a -> m b -> m b
662 m >> k = m >>= \_ -> k -- See Note [Recursive bindings for Applicative/Monad]
663 {-# INLINE (>>) #-}
664
665 -- | Inject a value into the monadic type.
666 return :: a -> m a
667 return = pure
668
669 -- | Fail with a message. This operation is not part of the
670 -- mathematical definition of a monad, but is invoked on pattern-match
671 -- failure in a @do@ expression.
672 --
673 -- As part of the MonadFail proposal (MFP), this function is moved
674 -- to its own class 'MonadFail' (see "Control.Monad.Fail" for more
675 -- details). The definition here will be removed in a future
676 -- release.
677 fail :: String -> m a
678 fail s = errorWithoutStackTrace s
679
680 {- Note [Recursive bindings for Applicative/Monad]
681 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
682
683 The original Applicative/Monad proposal stated that after
684 implementation, the designated implementation of (>>) would become
685
686 (>>) :: forall a b. m a -> m b -> m b
687 (>>) = (*>)
688
689 by default. You might be inclined to change this to reflect the stated
690 proposal, but you really shouldn't! Why? Because people tend to define
691 such instances the /other/ way around: in particular, it is perfectly
692 legitimate to define an instance of Applicative (*>) in terms of (>>),
693 which would lead to an infinite loop for the default implementation of
694 Monad! And people do this in the wild.
695
696 This turned into a nasty bug that was tricky to track down, and rather
697 than eliminate it everywhere upstream, it's easier to just retain the
698 original default.
699
700 -}
701
702 -- | Same as '>>=', but with the arguments interchanged.
703 {-# SPECIALISE (=<<) :: (a -> [b]) -> [a] -> [b] #-}
704 (=<<) :: Monad m => (a -> m b) -> m a -> m b
705 f =<< x = x >>= f
706
707 -- | Conditional execution of 'Applicative' expressions. For example,
708 --
709 -- > when debug (putStrLn "Debugging")
710 --
711 -- will output the string @Debugging@ if the Boolean value @debug@
712 -- is 'True', and otherwise do nothing.
713 when :: (Applicative f) => Bool -> f () -> f ()
714 {-# INLINABLE when #-}
715 {-# SPECIALISE when :: Bool -> IO () -> IO () #-}
716 {-# SPECIALISE when :: Bool -> Maybe () -> Maybe () #-}
717 when p s = if p then s else pure ()
718
719 -- | Evaluate each action in the sequence from left to right,
720 -- and collect the results.
721 sequence :: Monad m => [m a] -> m [a]
722 {-# INLINE sequence #-}
723 sequence = mapM id
724 -- Note: [sequence and mapM]
725
726 -- | @'mapM' f@ is equivalent to @'sequence' . 'map' f@.
727 mapM :: Monad m => (a -> m b) -> [a] -> m [b]
728 {-# INLINE mapM #-}
729 mapM f as = foldr k (return []) as
730 where
731 k a r = do { x <- f a; xs <- r; return (x:xs) }
732
733 {-
734 Note: [sequence and mapM]
735 ~~~~~~~~~~~~~~~~~~~~~~~~~
736 Originally, we defined
737
738 mapM f = sequence . map f
739
740 This relied on list fusion to produce efficient code for mapM, and led to
741 excessive allocation in cryptarithm2. Defining
742
743 sequence = mapM id
744
745 relies only on inlining a tiny function (id) and beta reduction, which tends to
746 be a more reliable aspect of simplification. Indeed, this does not lead to
747 similar problems in nofib.
748 -}
749
750 -- | Promote a function to a monad.
751 liftM :: (Monad m) => (a1 -> r) -> m a1 -> m r
752 liftM f m1 = do { x1 <- m1; return (f x1) }
753
754 -- | Promote a function to a monad, scanning the monadic arguments from
755 -- left to right. For example,
756 --
757 -- > liftM2 (+) [0,1] [0,2] = [0,2,1,3]
758 -- > liftM2 (+) (Just 1) Nothing = Nothing
759 --
760 liftM2 :: (Monad m) => (a1 -> a2 -> r) -> m a1 -> m a2 -> m r
761 liftM2 f m1 m2 = do { x1 <- m1; x2 <- m2; return (f x1 x2) }
762 -- Caution: since this may be used for `liftA2`, we can't use the obvious
763 -- definition of liftM2 = liftA2.
764
765 -- | Promote a function to a monad, scanning the monadic arguments from
766 -- left to right (cf. 'liftM2').
767 liftM3 :: (Monad m) => (a1 -> a2 -> a3 -> r) -> m a1 -> m a2 -> m a3 -> m r
768 liftM3 f m1 m2 m3 = do { x1 <- m1; x2 <- m2; x3 <- m3; return (f x1 x2 x3) }
769
770 -- | Promote a function to a monad, scanning the monadic arguments from
771 -- left to right (cf. 'liftM2').
772 liftM4 :: (Monad m) => (a1 -> a2 -> a3 -> a4 -> r) -> m a1 -> m a2 -> m a3 -> m a4 -> m r
773 liftM4 f m1 m2 m3 m4 = do { x1 <- m1; x2 <- m2; x3 <- m3; x4 <- m4; return (f x1 x2 x3 x4) }
774
775 -- | Promote a function to a monad, scanning the monadic arguments from
776 -- left to right (cf. 'liftM2').
777 liftM5 :: (Monad m) => (a1 -> a2 -> a3 -> a4 -> a5 -> r) -> m a1 -> m a2 -> m a3 -> m a4 -> m a5 -> m r
778 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) }
779
780 {-# INLINABLE liftM #-}
781 {-# SPECIALISE liftM :: (a1->r) -> IO a1 -> IO r #-}
782 {-# SPECIALISE liftM :: (a1->r) -> Maybe a1 -> Maybe r #-}
783 {-# INLINABLE liftM2 #-}
784 {-# SPECIALISE liftM2 :: (a1->a2->r) -> IO a1 -> IO a2 -> IO r #-}
785 {-# SPECIALISE liftM2 :: (a1->a2->r) -> Maybe a1 -> Maybe a2 -> Maybe r #-}
786 {-# INLINABLE liftM3 #-}
787 {-# SPECIALISE liftM3 :: (a1->a2->a3->r) -> IO a1 -> IO a2 -> IO a3 -> IO r #-}
788 {-# SPECIALISE liftM3 :: (a1->a2->a3->r) -> Maybe a1 -> Maybe a2 -> Maybe a3 -> Maybe r #-}
789 {-# INLINABLE liftM4 #-}
790 {-# SPECIALISE liftM4 :: (a1->a2->a3->a4->r) -> IO a1 -> IO a2 -> IO a3 -> IO a4 -> IO r #-}
791 {-# SPECIALISE liftM4 :: (a1->a2->a3->a4->r) -> Maybe a1 -> Maybe a2 -> Maybe a3 -> Maybe a4 -> Maybe r #-}
792 {-# INLINABLE liftM5 #-}
793 {-# SPECIALISE liftM5 :: (a1->a2->a3->a4->a5->r) -> IO a1 -> IO a2 -> IO a3 -> IO a4 -> IO a5 -> IO r #-}
794 {-# SPECIALISE liftM5 :: (a1->a2->a3->a4->a5->r) -> Maybe a1 -> Maybe a2 -> Maybe a3 -> Maybe a4 -> Maybe a5 -> Maybe r #-}
795
796 {- | In many situations, the 'liftM' operations can be replaced by uses of
797 'ap', which promotes function application.
798
799 > return f `ap` x1 `ap` ... `ap` xn
800
801 is equivalent to
802
803 > liftMn f x1 x2 ... xn
804
805 -}
806
807 ap :: (Monad m) => m (a -> b) -> m a -> m b
808 ap m1 m2 = do { x1 <- m1; x2 <- m2; return (x1 x2) }
809 -- Since many Applicative instances define (<*>) = ap, we
810 -- cannot define ap = (<*>)
811 {-# INLINABLE ap #-}
812 {-# SPECIALISE ap :: IO (a -> b) -> IO a -> IO b #-}
813 {-# SPECIALISE ap :: Maybe (a -> b) -> Maybe a -> Maybe b #-}
814
815 -- instances for Prelude types
816
817 -- | @since 2.01
818 instance Functor ((->) r) where
819 fmap = (.)
820
821 -- | @since 2.01
822 instance Applicative ((->) a) where
823 pure = const
824 (<*>) f g x = f x (g x)
825 liftA2 q f g x = q (f x) (g x)
826
827 -- | @since 2.01
828 instance Monad ((->) r) where
829 f >>= k = \ r -> k (f r) r
830
831 -- | @since 2.01
832 instance Functor ((,) a) where
833 fmap f (x,y) = (x, f y)
834
835 -- | @since 2.01
836 instance Functor Maybe where
837 fmap _ Nothing = Nothing
838 fmap f (Just a) = Just (f a)
839
840 -- | @since 2.01
841 instance Applicative Maybe where
842 pure = Just
843
844 Just f <*> m = fmap f m
845 Nothing <*> _m = Nothing
846
847 liftA2 f (Just x) (Just y) = Just (f x y)
848 liftA2 _ _ _ = Nothing
849
850 Just _m1 *> m2 = m2
851 Nothing *> _m2 = Nothing
852
853 -- | @since 2.01
854 instance Monad Maybe where
855 (Just x) >>= k = k x
856 Nothing >>= _ = Nothing
857
858 (>>) = (*>)
859
860 fail _ = Nothing
861
862 -- -----------------------------------------------------------------------------
863 -- The Alternative class definition
864
865 infixl 3 <|>
866
867 -- | A monoid on applicative functors.
868 --
869 -- If defined, 'some' and 'many' should be the least solutions
870 -- of the equations:
871 --
872 -- * @'some' v = (:) '<$>' v '<*>' 'many' v@
873 --
874 -- * @'many' v = 'some' v '<|>' 'pure' []@
875 class Applicative f => Alternative f where
876 -- | The identity of '<|>'
877 empty :: f a
878 -- | An associative binary operation
879 (<|>) :: f a -> f a -> f a
880
881 -- | One or more.
882 some :: f a -> f [a]
883 some v = some_v
884 where
885 many_v = some_v <|> pure []
886 some_v = liftA2 (:) v many_v
887
888 -- | Zero or more.
889 many :: f a -> f [a]
890 many v = many_v
891 where
892 many_v = some_v <|> pure []
893 some_v = liftA2 (:) v many_v
894
895
896 -- | @since 2.01
897 instance Alternative Maybe where
898 empty = Nothing
899 Nothing <|> r = r
900 l <|> _ = l
901
902 -- -----------------------------------------------------------------------------
903 -- The MonadPlus class definition
904
905 -- | Monads that also support choice and failure.
906 class (Alternative m, Monad m) => MonadPlus m where
907 -- | The identity of 'mplus'. It should also satisfy the equations
908 --
909 -- > mzero >>= f = mzero
910 -- > v >> mzero = mzero
911 --
912 -- The default definition is
913 --
914 -- @
915 -- mzero = 'empty'
916 -- @
917 mzero :: m a
918 mzero = empty
919
920 -- | An associative operation. The default definition is
921 --
922 -- @
923 -- mplus = ('<|>')
924 -- @
925 mplus :: m a -> m a -> m a
926 mplus = (<|>)
927
928 -- | @since 2.01
929 instance MonadPlus Maybe
930
931 ---------------------------------------------
932 -- The non-empty list type
933
934 infixr 5 :|
935
936 -- | Non-empty (and non-strict) list type.
937 --
938 -- @since 4.9.0.0
939 data NonEmpty a = a :| [a]
940 deriving ( Eq -- ^ @since 4.9.0.0
941 , Ord -- ^ @since 4.9.0.0
942 )
943
944 -- | @since 4.9.0.0
945 instance Functor NonEmpty where
946 fmap f ~(a :| as) = f a :| fmap f as
947 b <$ ~(_ :| as) = b :| (b <$ as)
948
949 -- | @since 4.9.0.0
950 instance Applicative NonEmpty where
951 pure a = a :| []
952 (<*>) = ap
953 liftA2 = liftM2
954
955 -- | @since 4.9.0.0
956 instance Monad NonEmpty where
957 ~(a :| as) >>= f = b :| (bs ++ bs')
958 where b :| bs = f a
959 bs' = as >>= toList . f
960 toList ~(c :| cs) = c : cs
961
962 ----------------------------------------------
963 -- The list type
964
965 -- | @since 2.01
966 instance Functor [] where
967 {-# INLINE fmap #-}
968 fmap = map
969
970 -- See Note: [List comprehensions and inlining]
971 -- | @since 2.01
972 instance Applicative [] where
973 {-# INLINE pure #-}
974 pure x = [x]
975 {-# INLINE (<*>) #-}
976 fs <*> xs = [f x | f <- fs, x <- xs]
977 {-# INLINE liftA2 #-}
978 liftA2 f xs ys = [f x y | x <- xs, y <- ys]
979 {-# INLINE (*>) #-}
980 xs *> ys = [y | _ <- xs, y <- ys]
981
982 -- See Note: [List comprehensions and inlining]
983 -- | @since 2.01
984 instance Monad [] where
985 {-# INLINE (>>=) #-}
986 xs >>= f = [y | x <- xs, y <- f x]
987 {-# INLINE (>>) #-}
988 (>>) = (*>)
989 {-# INLINE fail #-}
990 fail _ = []
991
992 -- | @since 2.01
993 instance Alternative [] where
994 empty = []
995 (<|>) = (++)
996
997 -- | @since 2.01
998 instance MonadPlus []
999
1000 {-
1001 A few list functions that appear here because they are used here.
1002 The rest of the prelude list functions are in GHC.List.
1003 -}
1004
1005 ----------------------------------------------
1006 -- foldr/build/augment
1007 ----------------------------------------------
1008
1009 -- | 'foldr', applied to a binary operator, a starting value (typically
1010 -- the right-identity of the operator), and a list, reduces the list
1011 -- using the binary operator, from right to left:
1012 --
1013 -- > foldr f z [x1, x2, ..., xn] == x1 `f` (x2 `f` ... (xn `f` z)...)
1014
1015 foldr :: (a -> b -> b) -> b -> [a] -> b
1016 -- foldr _ z [] = z
1017 -- foldr f z (x:xs) = f x (foldr f z xs)
1018 {-# INLINE [0] foldr #-}
1019 -- Inline only in the final stage, after the foldr/cons rule has had a chance
1020 -- Also note that we inline it when it has *two* parameters, which are the
1021 -- ones we are keen about specialising!
1022 foldr k z = go
1023 where
1024 go [] = z
1025 go (y:ys) = y `k` go ys
1026
1027 -- | A list producer that can be fused with 'foldr'.
1028 -- This function is merely
1029 --
1030 -- > build g = g (:) []
1031 --
1032 -- but GHC's simplifier will transform an expression of the form
1033 -- @'foldr' k z ('build' g)@, which may arise after inlining, to @g k z@,
1034 -- which avoids producing an intermediate list.
1035
1036 build :: forall a. (forall b. (a -> b -> b) -> b -> b) -> [a]
1037 {-# INLINE [1] build #-}
1038 -- The INLINE is important, even though build is tiny,
1039 -- because it prevents [] getting inlined in the version that
1040 -- appears in the interface file. If [] *is* inlined, it
1041 -- won't match with [] appearing in rules in an importing module.
1042 --
1043 -- The "1" says to inline in phase 1
1044
1045 build g = g (:) []
1046
1047 -- | A list producer that can be fused with 'foldr'.
1048 -- This function is merely
1049 --
1050 -- > augment g xs = g (:) xs
1051 --
1052 -- but GHC's simplifier will transform an expression of the form
1053 -- @'foldr' k z ('augment' g xs)@, which may arise after inlining, to
1054 -- @g k ('foldr' k z xs)@, which avoids producing an intermediate list.
1055
1056 augment :: forall a. (forall b. (a->b->b) -> b -> b) -> [a] -> [a]
1057 {-# INLINE [1] augment #-}
1058 augment g xs = g (:) xs
1059
1060 {-# RULES
1061 "fold/build" forall k z (g::forall b. (a->b->b) -> b -> b) .
1062 foldr k z (build g) = g k z
1063
1064 "foldr/augment" forall k z xs (g::forall b. (a->b->b) -> b -> b) .
1065 foldr k z (augment g xs) = g k (foldr k z xs)
1066
1067 "foldr/id" foldr (:) [] = \x -> x
1068 "foldr/app" [1] forall ys. foldr (:) ys = \xs -> xs ++ ys
1069 -- Only activate this from phase 1, because that's
1070 -- when we disable the rule that expands (++) into foldr
1071
1072 -- The foldr/cons rule looks nice, but it can give disastrously
1073 -- bloated code when commpiling
1074 -- array (a,b) [(1,2), (2,2), (3,2), ...very long list... ]
1075 -- i.e. when there are very very long literal lists
1076 -- So I've disabled it for now. We could have special cases
1077 -- for short lists, I suppose.
1078 -- "foldr/cons" forall k z x xs. foldr k z (x:xs) = k x (foldr k z xs)
1079
1080 "foldr/single" forall k z x. foldr k z [x] = k x z
1081 "foldr/nil" forall k z. foldr k z [] = z
1082
1083 "foldr/cons/build" forall k z x (g::forall b. (a->b->b) -> b -> b) .
1084 foldr k z (x:build g) = k x (g k z)
1085
1086 "augment/build" forall (g::forall b. (a->b->b) -> b -> b)
1087 (h::forall b. (a->b->b) -> b -> b) .
1088 augment g (build h) = build (\c n -> g c (h c n))
1089 "augment/nil" forall (g::forall b. (a->b->b) -> b -> b) .
1090 augment g [] = build g
1091 #-}
1092
1093 -- This rule is true, but not (I think) useful:
1094 -- augment g (augment h t) = augment (\cn -> g c (h c n)) t
1095
1096 ----------------------------------------------
1097 -- map
1098 ----------------------------------------------
1099
1100 -- | 'map' @f xs@ is the list obtained by applying @f@ to each element
1101 -- of @xs@, i.e.,
1102 --
1103 -- > map f [x1, x2, ..., xn] == [f x1, f x2, ..., f xn]
1104 -- > map f [x1, x2, ...] == [f x1, f x2, ...]
1105
1106 map :: (a -> b) -> [a] -> [b]
1107 {-# NOINLINE [0] map #-}
1108 -- We want the RULEs "map" and "map/coerce" to fire first.
1109 -- map is recursive, so won't inline anyway,
1110 -- but saying so is more explicit, and silences warnings
1111 map _ [] = []
1112 map f (x:xs) = f x : map f xs
1113
1114 -- Note eta expanded
1115 mapFB :: (elt -> lst -> lst) -> (a -> elt) -> a -> lst -> lst
1116 {-# INLINE [0] mapFB #-} -- See Note [Inline FB functions] in GHC.List
1117 mapFB c f = \x ys -> c (f x) ys
1118
1119 {- Note [The rules for map]
1120 ~~~~~~~~~~~~~~~~~~~~~~~~~~~
1121 The rules for map work like this.
1122
1123 * Up to (but not including) phase 1, we use the "map" rule to
1124 rewrite all saturated applications of map with its build/fold
1125 form, hoping for fusion to happen.
1126
1127 In phase 1 and 0, we switch off that rule, inline build, and
1128 switch on the "mapList" rule, which rewrites the foldr/mapFB
1129 thing back into plain map.
1130
1131 It's important that these two rules aren't both active at once
1132 (along with build's unfolding) else we'd get an infinite loop
1133 in the rules. Hence the activation control below.
1134
1135 * This same pattern is followed by many other functions:
1136 e.g. append, filter, iterate, repeat, etc. in GHC.List
1137
1138 See also Note [Inline FB functions] in GHC.List
1139
1140 * The "mapFB" rule optimises compositions of map
1141
1142 * The "mapFB/id" rule gets rid of 'map id' calls.
1143 You might think that (mapFB c id) will turn into c simply
1144 when mapFB is inlined; but before that happens the "mapList"
1145 rule turns
1146 (foldr (mapFB (:) id) [] a
1147 back into
1148 map id
1149 Which is not very clever.
1150
1151 * Any similarity to the Functor laws for [] is expected.
1152 -}
1153
1154 {-# RULES
1155 "map" [~1] forall f xs. map f xs = build (\c n -> foldr (mapFB c f) n xs)
1156 "mapList" [1] forall f. foldr (mapFB (:) f) [] = map f
1157 "mapFB" forall c f g. mapFB (mapFB c f) g = mapFB c (f.g)
1158 "mapFB/id" forall c. mapFB c (\x -> x) = c
1159 #-}
1160
1161 -- See Breitner, Eisenberg, Peyton Jones, and Weirich, "Safe Zero-cost
1162 -- Coercions for Haskell", section 6.5:
1163 -- http://research.microsoft.com/en-us/um/people/simonpj/papers/ext-f/coercible.pdf
1164
1165 {-# RULES "map/coerce" [1] map coerce = coerce #-}
1166
1167
1168 ----------------------------------------------
1169 -- append
1170 ----------------------------------------------
1171
1172 -- | Append two lists, i.e.,
1173 --
1174 -- > [x1, ..., xm] ++ [y1, ..., yn] == [x1, ..., xm, y1, ..., yn]
1175 -- > [x1, ..., xm] ++ [y1, ...] == [x1, ..., xm, y1, ...]
1176 --
1177 -- If the first list is not finite, the result is the first list.
1178
1179 (++) :: [a] -> [a] -> [a]
1180 {-# NOINLINE [1] (++) #-} -- We want the RULE to fire first.
1181 -- It's recursive, so won't inline anyway,
1182 -- but saying so is more explicit
1183 (++) [] ys = ys
1184 (++) (x:xs) ys = x : xs ++ ys
1185
1186 {-# RULES
1187 "++" [~1] forall xs ys. xs ++ ys = augment (\c n -> foldr c n xs) ys
1188 #-}
1189
1190
1191 -- |'otherwise' is defined as the value 'True'. It helps to make
1192 -- guards more readable. eg.
1193 --
1194 -- > f x | x < 0 = ...
1195 -- > | otherwise = ...
1196 otherwise :: Bool
1197 otherwise = True
1198
1199 ----------------------------------------------
1200 -- Type Char and String
1201 ----------------------------------------------
1202
1203 -- | A 'String' is a list of characters. String constants in Haskell are values
1204 -- of type 'String'.
1205 --
1206 type String = [Char]
1207
1208 unsafeChr :: Int -> Char
1209 unsafeChr (I# i#) = C# (chr# i#)
1210
1211 -- | The 'Prelude.fromEnum' method restricted to the type 'Data.Char.Char'.
1212 ord :: Char -> Int
1213 ord (C# c#) = I# (ord# c#)
1214
1215 -- | This 'String' equality predicate is used when desugaring
1216 -- pattern-matches against strings.
1217 eqString :: String -> String -> Bool
1218 eqString [] [] = True
1219 eqString (c1:cs1) (c2:cs2) = c1 == c2 && cs1 `eqString` cs2
1220 eqString _ _ = False
1221
1222 {-# RULES "eqString" (==) = eqString #-}
1223 -- eqString also has a BuiltInRule in PrelRules.hs:
1224 -- eqString (unpackCString# (Lit s1)) (unpackCString# (Lit s2)) = s1==s2
1225
1226
1227 ----------------------------------------------
1228 -- 'Int' related definitions
1229 ----------------------------------------------
1230
1231 maxInt, minInt :: Int
1232
1233 {- Seems clumsy. Should perhaps put minInt and MaxInt directly into MachDeps.h -}
1234 #if WORD_SIZE_IN_BITS == 31
1235 minInt = I# (-0x40000000#)
1236 maxInt = I# 0x3FFFFFFF#
1237 #elif WORD_SIZE_IN_BITS == 32
1238 minInt = I# (-0x80000000#)
1239 maxInt = I# 0x7FFFFFFF#
1240 #else
1241 minInt = I# (-0x8000000000000000#)
1242 maxInt = I# 0x7FFFFFFFFFFFFFFF#
1243 #endif
1244
1245 ----------------------------------------------
1246 -- The function type
1247 ----------------------------------------------
1248
1249 -- | Identity function.
1250 --
1251 -- > id x = x
1252 id :: a -> a
1253 id x = x
1254
1255 -- Assertion function. This simply ignores its boolean argument.
1256 -- The compiler may rewrite it to @('assertError' line)@.
1257
1258 -- | If the first argument evaluates to 'True', then the result is the
1259 -- second argument. Otherwise an 'AssertionFailed' exception is raised,
1260 -- containing a 'String' with the source file and line number of the
1261 -- call to 'assert'.
1262 --
1263 -- Assertions can normally be turned on or off with a compiler flag
1264 -- (for GHC, assertions are normally on unless optimisation is turned on
1265 -- with @-O@ or the @-fignore-asserts@
1266 -- option is given). When assertions are turned off, the first
1267 -- argument to 'assert' is ignored, and the second argument is
1268 -- returned as the result.
1269
1270 -- SLPJ: in 5.04 etc 'assert' is in GHC.Prim,
1271 -- but from Template Haskell onwards it's simply
1272 -- defined here in Base.hs
1273 assert :: Bool -> a -> a
1274 assert _pred r = r
1275
1276 breakpoint :: a -> a
1277 breakpoint r = r
1278
1279 breakpointCond :: Bool -> a -> a
1280 breakpointCond _ r = r
1281
1282 data Opaque = forall a. O a
1283 -- | @const x@ is a unary function which evaluates to @x@ for all inputs.
1284 --
1285 -- >>> const 42 "hello"
1286 -- 42
1287 --
1288 -- >>> map (const 42) [0..3]
1289 -- [42,42,42,42]
1290 const :: a -> b -> a
1291 const x _ = x
1292
1293 -- | Function composition.
1294 {-# INLINE (.) #-}
1295 -- Make sure it has TWO args only on the left, so that it inlines
1296 -- when applied to two functions, even if there is no final argument
1297 (.) :: (b -> c) -> (a -> b) -> a -> c
1298 (.) f g = \x -> f (g x)
1299
1300 -- | @'flip' f@ takes its (first) two arguments in the reverse order of @f@.
1301 --
1302 -- >>> flip (++) "hello" "world"
1303 -- "worldhello"
1304 flip :: (a -> b -> c) -> b -> a -> c
1305 flip f x y = f y x
1306
1307 -- | Application operator. This operator is redundant, since ordinary
1308 -- application @(f x)@ means the same as @(f '$' x)@. However, '$' has
1309 -- low, right-associative binding precedence, so it sometimes allows
1310 -- parentheses to be omitted; for example:
1311 --
1312 -- > f $ g $ h x = f (g (h x))
1313 --
1314 -- It is also useful in higher-order situations, such as @'map' ('$' 0) xs@,
1315 -- or @'Data.List.zipWith' ('$') fs xs@.
1316 --
1317 -- Note that @($)@ is levity-polymorphic in its result type, so that
1318 -- foo $ True where foo :: Bool -> Int#
1319 -- is well-typed
1320 {-# INLINE ($) #-}
1321 ($) :: forall r a (b :: TYPE r). (a -> b) -> a -> b
1322 f $ x = f x
1323
1324 -- | Strict (call-by-value) application operator. It takes a function and an
1325 -- argument, evaluates the argument to weak head normal form (WHNF), then calls
1326 -- the function with that value.
1327
1328 ($!) :: forall r a (b :: TYPE r). (a -> b) -> a -> b
1329 f $! x = let !vx = x in f vx -- see #2273
1330
1331 -- | @'until' p f@ yields the result of applying @f@ until @p@ holds.
1332 until :: (a -> Bool) -> (a -> a) -> a -> a
1333 until p f = go
1334 where
1335 go x | p x = x
1336 | otherwise = go (f x)
1337
1338 -- | 'asTypeOf' is a type-restricted version of 'const'. It is usually
1339 -- used as an infix operator, and its typing forces its first argument
1340 -- (which is usually overloaded) to have the same type as the second.
1341 asTypeOf :: a -> a -> a
1342 asTypeOf = const
1343
1344 ----------------------------------------------
1345 -- Functor/Applicative/Monad instances for IO
1346 ----------------------------------------------
1347
1348 -- | @since 2.01
1349 instance Functor IO where
1350 fmap f x = x >>= (pure . f)
1351
1352 -- | @since 2.01
1353 instance Applicative IO where
1354 {-# INLINE pure #-}
1355 {-# INLINE (*>) #-}
1356 {-# INLINE liftA2 #-}
1357 pure = returnIO
1358 (*>) = thenIO
1359 (<*>) = ap
1360 liftA2 = liftM2
1361
1362 -- | @since 2.01
1363 instance Monad IO where
1364 {-# INLINE (>>) #-}
1365 {-# INLINE (>>=) #-}
1366 (>>) = (*>)
1367 (>>=) = bindIO
1368 fail s = failIO s
1369
1370 -- | @since 4.9.0.0
1371 instance Alternative IO where
1372 empty = failIO "mzero"
1373 (<|>) = mplusIO
1374
1375 -- | @since 4.9.0.0
1376 instance MonadPlus IO
1377
1378 returnIO :: a -> IO a
1379 returnIO x = IO (\ s -> (# s, x #))
1380
1381 bindIO :: IO a -> (a -> IO b) -> IO b
1382 bindIO (IO m) k = IO (\ s -> case m s of (# new_s, a #) -> unIO (k a) new_s)
1383
1384 thenIO :: IO a -> IO b -> IO b
1385 thenIO (IO m) k = IO (\ s -> case m s of (# new_s, _ #) -> unIO k new_s)
1386
1387 unIO :: IO a -> (State# RealWorld -> (# State# RealWorld, a #))
1388 unIO (IO a) = a
1389
1390 {- |
1391 Returns the 'tag' of a constructor application; this function is used
1392 by the deriving code for Eq, Ord and Enum.
1393
1394 The primitive dataToTag# requires an evaluated constructor application
1395 as its argument, so we provide getTag as a wrapper that performs the
1396 evaluation before calling dataToTag#. We could have dataToTag#
1397 evaluate its argument, but we prefer to do it this way because (a)
1398 dataToTag# can be an inline primop if it doesn't need to do any
1399 evaluation, and (b) we want to expose the evaluation to the
1400 simplifier, because it might be possible to eliminate the evaluation
1401 in the case when the argument is already known to be evaluated.
1402 -}
1403 {-# INLINE getTag #-}
1404 getTag :: a -> Int#
1405 getTag !x = dataToTag# x
1406
1407 ----------------------------------------------
1408 -- Numeric primops
1409 ----------------------------------------------
1410
1411 -- Definitions of the boxed PrimOps; these will be
1412 -- used in the case of partial applications, etc.
1413
1414 {-# INLINE quotInt #-}
1415 {-# INLINE remInt #-}
1416
1417 quotInt, remInt, divInt, modInt :: Int -> Int -> Int
1418 (I# x) `quotInt` (I# y) = I# (x `quotInt#` y)
1419 (I# x) `remInt` (I# y) = I# (x `remInt#` y)
1420 (I# x) `divInt` (I# y) = I# (x `divInt#` y)
1421 (I# x) `modInt` (I# y) = I# (x `modInt#` y)
1422
1423 quotRemInt :: Int -> Int -> (Int, Int)
1424 (I# x) `quotRemInt` (I# y) = case x `quotRemInt#` y of
1425 (# q, r #) ->
1426 (I# q, I# r)
1427
1428 divModInt :: Int -> Int -> (Int, Int)
1429 (I# x) `divModInt` (I# y) = case x `divModInt#` y of
1430 (# q, r #) -> (I# q, I# r)
1431
1432 divModInt# :: Int# -> Int# -> (# Int#, Int# #)
1433 x# `divModInt#` y#
1434 | isTrue# (x# ># 0#) && isTrue# (y# <# 0#) =
1435 case (x# -# 1#) `quotRemInt#` y# of
1436 (# q, r #) -> (# q -# 1#, r +# y# +# 1# #)
1437 | isTrue# (x# <# 0#) && isTrue# (y# ># 0#) =
1438 case (x# +# 1#) `quotRemInt#` y# of
1439 (# q, r #) -> (# q -# 1#, r +# y# -# 1# #)
1440 | otherwise =
1441 x# `quotRemInt#` y#
1442
1443 -- Wrappers for the shift operations. The uncheckedShift# family are
1444 -- undefined when the amount being shifted by is greater than the size
1445 -- in bits of Int#, so these wrappers perform a check and return
1446 -- either zero or -1 appropriately.
1447 --
1448 -- Note that these wrappers still produce undefined results when the
1449 -- second argument (the shift amount) is negative.
1450
1451 -- | Shift the argument left by the specified number of bits
1452 -- (which must be non-negative).
1453 shiftL# :: Word# -> Int# -> Word#
1454 a `shiftL#` b | isTrue# (b >=# WORD_SIZE_IN_BITS#) = 0##
1455 | otherwise = a `uncheckedShiftL#` b
1456
1457 -- | Shift the argument right by the specified number of bits
1458 -- (which must be non-negative).
1459 -- The "RL" means "right, logical" (as opposed to RA for arithmetic)
1460 -- (although an arithmetic right shift wouldn't make sense for Word#)
1461 shiftRL# :: Word# -> Int# -> Word#
1462 a `shiftRL#` b | isTrue# (b >=# WORD_SIZE_IN_BITS#) = 0##
1463 | otherwise = a `uncheckedShiftRL#` b
1464
1465 -- | Shift the argument left by the specified number of bits
1466 -- (which must be non-negative).
1467 iShiftL# :: Int# -> Int# -> Int#
1468 a `iShiftL#` b | isTrue# (b >=# WORD_SIZE_IN_BITS#) = 0#
1469 | otherwise = a `uncheckedIShiftL#` b
1470
1471 -- | Shift the argument right (signed) by the specified number of bits
1472 -- (which must be non-negative).
1473 -- The "RA" means "right, arithmetic" (as opposed to RL for logical)
1474 iShiftRA# :: Int# -> Int# -> Int#
1475 a `iShiftRA#` b | isTrue# (b >=# WORD_SIZE_IN_BITS#) = if isTrue# (a <# 0#)
1476 then (-1#)
1477 else 0#
1478 | otherwise = a `uncheckedIShiftRA#` b
1479
1480 -- | Shift the argument right (unsigned) by the specified number of bits
1481 -- (which must be non-negative).
1482 -- The "RL" means "right, logical" (as opposed to RA for arithmetic)
1483 iShiftRL# :: Int# -> Int# -> Int#
1484 a `iShiftRL#` b | isTrue# (b >=# WORD_SIZE_IN_BITS#) = 0#
1485 | otherwise = a `uncheckedIShiftRL#` b
1486
1487 -- Rules for C strings (the functions themselves are now in GHC.CString)
1488 {-# RULES
1489 "unpack" [~1] forall a . unpackCString# a = build (unpackFoldrCString# a)
1490 "unpack-list" [1] forall a . unpackFoldrCString# a (:) [] = unpackCString# a
1491 "unpack-append" forall a n . unpackFoldrCString# a (:) n = unpackAppendCString# a n
1492
1493 -- There's a built-in rule (in PrelRules.hs) for
1494 -- unpackFoldr "foo" c (unpackFoldr "baz" c n) = unpackFoldr "foobaz" c n
1495
1496 #-}