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