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