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