base: Remove `Monad(fail)` method and reexport `MonadFail(fail)` instead
[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 {- Note [Recursive bindings for Applicative/Monad]
668 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
669
670 The original Applicative/Monad proposal stated that after
671 implementation, the designated implementation of (>>) would become
672
673 (>>) :: forall a b. m a -> m b -> m b
674 (>>) = (*>)
675
676 by default. You might be inclined to change this to reflect the stated
677 proposal, but you really shouldn't! Why? Because people tend to define
678 such instances the /other/ way around: in particular, it is perfectly
679 legitimate to define an instance of Applicative (*>) in terms of (>>),
680 which would lead to an infinite loop for the default implementation of
681 Monad! And people do this in the wild.
682
683 This turned into a nasty bug that was tricky to track down, and rather
684 than eliminate it everywhere upstream, it's easier to just retain the
685 original default.
686
687 -}
688
689 -- | Same as '>>=', but with the arguments interchanged.
690 {-# SPECIALISE (=<<) :: (a -> [b]) -> [a] -> [b] #-}
691 (=<<) :: Monad m => (a -> m b) -> m a -> m b
692 f =<< x = x >>= f
693
694 -- | Conditional execution of 'Applicative' expressions. For example,
695 --
696 -- > when debug (putStrLn "Debugging")
697 --
698 -- will output the string @Debugging@ if the Boolean value @debug@
699 -- is 'True', and otherwise do nothing.
700 when :: (Applicative f) => Bool -> f () -> f ()
701 {-# INLINABLE when #-}
702 {-# SPECIALISE when :: Bool -> IO () -> IO () #-}
703 {-# SPECIALISE when :: Bool -> Maybe () -> Maybe () #-}
704 when p s = if p then s else pure ()
705
706 -- | Evaluate each action in the sequence from left to right,
707 -- and collect the results.
708 sequence :: Monad m => [m a] -> m [a]
709 {-# INLINE sequence #-}
710 sequence = mapM id
711 -- Note: [sequence and mapM]
712
713 -- | @'mapM' f@ is equivalent to @'sequence' . 'map' f@.
714 mapM :: Monad m => (a -> m b) -> [a] -> m [b]
715 {-# INLINE mapM #-}
716 mapM f as = foldr k (return []) as
717 where
718 k a r = do { x <- f a; xs <- r; return (x:xs) }
719
720 {-
721 Note: [sequence and mapM]
722 ~~~~~~~~~~~~~~~~~~~~~~~~~
723 Originally, we defined
724
725 mapM f = sequence . map f
726
727 This relied on list fusion to produce efficient code for mapM, and led to
728 excessive allocation in cryptarithm2. Defining
729
730 sequence = mapM id
731
732 relies only on inlining a tiny function (id) and beta reduction, which tends to
733 be a more reliable aspect of simplification. Indeed, this does not lead to
734 similar problems in nofib.
735 -}
736
737 -- | Promote a function to a monad.
738 liftM :: (Monad m) => (a1 -> r) -> m a1 -> m r
739 liftM f m1 = do { x1 <- m1; return (f x1) }
740
741 -- | Promote a function to a monad, scanning the monadic arguments from
742 -- left to right. For example,
743 --
744 -- > liftM2 (+) [0,1] [0,2] = [0,2,1,3]
745 -- > liftM2 (+) (Just 1) Nothing = Nothing
746 --
747 liftM2 :: (Monad m) => (a1 -> a2 -> r) -> m a1 -> m a2 -> m r
748 liftM2 f m1 m2 = do { x1 <- m1; x2 <- m2; return (f x1 x2) }
749 -- Caution: since this may be used for `liftA2`, we can't use the obvious
750 -- definition of liftM2 = liftA2.
751
752 -- | Promote a function to a monad, scanning the monadic arguments from
753 -- left to right (cf. 'liftM2').
754 liftM3 :: (Monad m) => (a1 -> a2 -> a3 -> r) -> m a1 -> m a2 -> m a3 -> m r
755 liftM3 f m1 m2 m3 = do { x1 <- m1; x2 <- m2; x3 <- m3; return (f x1 x2 x3) }
756
757 -- | Promote a function to a monad, scanning the monadic arguments from
758 -- left to right (cf. 'liftM2').
759 liftM4 :: (Monad m) => (a1 -> a2 -> a3 -> a4 -> r) -> m a1 -> m a2 -> m a3 -> m a4 -> m r
760 liftM4 f m1 m2 m3 m4 = do { x1 <- m1; x2 <- m2; x3 <- m3; x4 <- m4; return (f x1 x2 x3 x4) }
761
762 -- | Promote a function to a monad, scanning the monadic arguments from
763 -- left to right (cf. 'liftM2').
764 liftM5 :: (Monad m) => (a1 -> a2 -> a3 -> a4 -> a5 -> r) -> m a1 -> m a2 -> m a3 -> m a4 -> m a5 -> m r
765 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) }
766
767 {-# INLINABLE liftM #-}
768 {-# SPECIALISE liftM :: (a1->r) -> IO a1 -> IO r #-}
769 {-# SPECIALISE liftM :: (a1->r) -> Maybe a1 -> Maybe r #-}
770 {-# INLINABLE liftM2 #-}
771 {-# SPECIALISE liftM2 :: (a1->a2->r) -> IO a1 -> IO a2 -> IO r #-}
772 {-# SPECIALISE liftM2 :: (a1->a2->r) -> Maybe a1 -> Maybe a2 -> Maybe r #-}
773 {-# INLINABLE liftM3 #-}
774 {-# SPECIALISE liftM3 :: (a1->a2->a3->r) -> IO a1 -> IO a2 -> IO a3 -> IO r #-}
775 {-# SPECIALISE liftM3 :: (a1->a2->a3->r) -> Maybe a1 -> Maybe a2 -> Maybe a3 -> Maybe r #-}
776 {-# INLINABLE liftM4 #-}
777 {-# SPECIALISE liftM4 :: (a1->a2->a3->a4->r) -> IO a1 -> IO a2 -> IO a3 -> IO a4 -> IO r #-}
778 {-# SPECIALISE liftM4 :: (a1->a2->a3->a4->r) -> Maybe a1 -> Maybe a2 -> Maybe a3 -> Maybe a4 -> Maybe r #-}
779 {-# INLINABLE liftM5 #-}
780 {-# SPECIALISE liftM5 :: (a1->a2->a3->a4->a5->r) -> IO a1 -> IO a2 -> IO a3 -> IO a4 -> IO a5 -> IO r #-}
781 {-# SPECIALISE liftM5 :: (a1->a2->a3->a4->a5->r) -> Maybe a1 -> Maybe a2 -> Maybe a3 -> Maybe a4 -> Maybe a5 -> Maybe r #-}
782
783 {- | In many situations, the 'liftM' operations can be replaced by uses of
784 'ap', which promotes function application.
785
786 > return f `ap` x1 `ap` ... `ap` xn
787
788 is equivalent to
789
790 > liftMn f x1 x2 ... xn
791
792 -}
793
794 ap :: (Monad m) => m (a -> b) -> m a -> m b
795 ap m1 m2 = do { x1 <- m1; x2 <- m2; return (x1 x2) }
796 -- Since many Applicative instances define (<*>) = ap, we
797 -- cannot define ap = (<*>)
798 {-# INLINABLE ap #-}
799 {-# SPECIALISE ap :: IO (a -> b) -> IO a -> IO b #-}
800 {-# SPECIALISE ap :: Maybe (a -> b) -> Maybe a -> Maybe b #-}
801
802 -- instances for Prelude types
803
804 -- | @since 2.01
805 instance Functor ((->) r) where
806 fmap = (.)
807
808 -- | @since 2.01
809 instance Applicative ((->) a) where
810 pure = const
811 (<*>) f g x = f x (g x)
812 liftA2 q f g x = q (f x) (g x)
813
814 -- | @since 2.01
815 instance Monad ((->) r) where
816 f >>= k = \ r -> k (f r) r
817
818 -- | @since 2.01
819 instance Functor ((,) a) where
820 fmap f (x,y) = (x, f y)
821
822 -- | @since 2.01
823 instance Functor Maybe where
824 fmap _ Nothing = Nothing
825 fmap f (Just a) = Just (f a)
826
827 -- | @since 2.01
828 instance Applicative Maybe where
829 pure = Just
830
831 Just f <*> m = fmap f m
832 Nothing <*> _m = Nothing
833
834 liftA2 f (Just x) (Just y) = Just (f x y)
835 liftA2 _ _ _ = Nothing
836
837 Just _m1 *> m2 = m2
838 Nothing *> _m2 = Nothing
839
840 -- | @since 2.01
841 instance Monad Maybe where
842 (Just x) >>= k = k x
843 Nothing >>= _ = Nothing
844
845 (>>) = (*>)
846
847 -- -----------------------------------------------------------------------------
848 -- The Alternative class definition
849
850 infixl 3 <|>
851
852 -- | A monoid on applicative functors.
853 --
854 -- If defined, 'some' and 'many' should be the least solutions
855 -- of the equations:
856 --
857 -- * @'some' v = (:) 'Prelude.<$>' v '<*>' 'many' v@
858 --
859 -- * @'many' v = 'some' v '<|>' 'pure' []@
860 class Applicative f => Alternative f where
861 -- | The identity of '<|>'
862 empty :: f a
863 -- | An associative binary operation
864 (<|>) :: f a -> f a -> f a
865
866 -- | One or more.
867 some :: f a -> f [a]
868 some v = some_v
869 where
870 many_v = some_v <|> pure []
871 some_v = liftA2 (:) v many_v
872
873 -- | Zero or more.
874 many :: f a -> f [a]
875 many v = many_v
876 where
877 many_v = some_v <|> pure []
878 some_v = liftA2 (:) v many_v
879
880
881 -- | @since 2.01
882 instance Alternative Maybe where
883 empty = Nothing
884 Nothing <|> r = r
885 l <|> _ = l
886
887 -- -----------------------------------------------------------------------------
888 -- The MonadPlus class definition
889
890 -- | Monads that also support choice and failure.
891 class (Alternative m, Monad m) => MonadPlus m where
892 -- | The identity of 'mplus'. It should also satisfy the equations
893 --
894 -- > mzero >>= f = mzero
895 -- > v >> mzero = mzero
896 --
897 -- The default definition is
898 --
899 -- @
900 -- mzero = 'empty'
901 -- @
902 mzero :: m a
903 mzero = empty
904
905 -- | An associative operation. The default definition is
906 --
907 -- @
908 -- mplus = ('<|>')
909 -- @
910 mplus :: m a -> m a -> m a
911 mplus = (<|>)
912
913 -- | @since 2.01
914 instance MonadPlus Maybe
915
916 ---------------------------------------------
917 -- The non-empty list type
918
919 infixr 5 :|
920
921 -- | Non-empty (and non-strict) list type.
922 --
923 -- @since 4.9.0.0
924 data NonEmpty a = a :| [a]
925 deriving ( Eq -- ^ @since 4.9.0.0
926 , Ord -- ^ @since 4.9.0.0
927 )
928
929 -- | @since 4.9.0.0
930 instance Functor NonEmpty where
931 fmap f ~(a :| as) = f a :| fmap f as
932 b <$ ~(_ :| as) = b :| (b <$ as)
933
934 -- | @since 4.9.0.0
935 instance Applicative NonEmpty where
936 pure a = a :| []
937 (<*>) = ap
938 liftA2 = liftM2
939
940 -- | @since 4.9.0.0
941 instance Monad NonEmpty where
942 ~(a :| as) >>= f = b :| (bs ++ bs')
943 where b :| bs = f a
944 bs' = as >>= toList . f
945 toList ~(c :| cs) = c : cs
946
947 ----------------------------------------------
948 -- The list type
949
950 -- | @since 2.01
951 instance Functor [] where
952 {-# INLINE fmap #-}
953 fmap = map
954
955 -- See Note: [List comprehensions and inlining]
956 -- | @since 2.01
957 instance Applicative [] where
958 {-# INLINE pure #-}
959 pure x = [x]
960 {-# INLINE (<*>) #-}
961 fs <*> xs = [f x | f <- fs, x <- xs]
962 {-# INLINE liftA2 #-}
963 liftA2 f xs ys = [f x y | x <- xs, y <- ys]
964 {-# INLINE (*>) #-}
965 xs *> ys = [y | _ <- xs, y <- ys]
966
967 -- See Note: [List comprehensions and inlining]
968 -- | @since 2.01
969 instance Monad [] where
970 {-# INLINE (>>=) #-}
971 xs >>= f = [y | x <- xs, y <- f x]
972 {-# INLINE (>>) #-}
973 (>>) = (*>)
974
975 -- | @since 2.01
976 instance Alternative [] where
977 empty = []
978 (<|>) = (++)
979
980 -- | @since 2.01
981 instance MonadPlus []
982
983 {-
984 A few list functions that appear here because they are used here.
985 The rest of the prelude list functions are in GHC.List.
986 -}
987
988 ----------------------------------------------
989 -- foldr/build/augment
990 ----------------------------------------------
991
992 -- | 'foldr', applied to a binary operator, a starting value (typically
993 -- the right-identity of the operator), and a list, reduces the list
994 -- using the binary operator, from right to left:
995 --
996 -- > foldr f z [x1, x2, ..., xn] == x1 `f` (x2 `f` ... (xn `f` z)...)
997
998 foldr :: (a -> b -> b) -> b -> [a] -> b
999 -- foldr _ z [] = z
1000 -- foldr f z (x:xs) = f x (foldr f z xs)
1001 {-# INLINE [0] foldr #-}
1002 -- Inline only in the final stage, after the foldr/cons rule has had a chance
1003 -- Also note that we inline it when it has *two* parameters, which are the
1004 -- ones we are keen about specialising!
1005 foldr k z = go
1006 where
1007 go [] = z
1008 go (y:ys) = y `k` go ys
1009
1010 -- | A list producer that can be fused with 'foldr'.
1011 -- This function is merely
1012 --
1013 -- > build g = g (:) []
1014 --
1015 -- but GHC's simplifier will transform an expression of the form
1016 -- @'foldr' k z ('build' g)@, which may arise after inlining, to @g k z@,
1017 -- which avoids producing an intermediate list.
1018
1019 build :: forall a. (forall b. (a -> b -> b) -> b -> b) -> [a]
1020 {-# INLINE [1] build #-}
1021 -- The INLINE is important, even though build is tiny,
1022 -- because it prevents [] getting inlined in the version that
1023 -- appears in the interface file. If [] *is* inlined, it
1024 -- won't match with [] appearing in rules in an importing module.
1025 --
1026 -- The "1" says to inline in phase 1
1027
1028 build g = g (:) []
1029
1030 -- | A list producer that can be fused with 'foldr'.
1031 -- This function is merely
1032 --
1033 -- > augment g xs = g (:) xs
1034 --
1035 -- but GHC's simplifier will transform an expression of the form
1036 -- @'foldr' k z ('augment' g xs)@, which may arise after inlining, to
1037 -- @g k ('foldr' k z xs)@, which avoids producing an intermediate list.
1038
1039 augment :: forall a. (forall b. (a->b->b) -> b -> b) -> [a] -> [a]
1040 {-# INLINE [1] augment #-}
1041 augment g xs = g (:) xs
1042
1043 {-# RULES
1044 "fold/build" forall k z (g::forall b. (a->b->b) -> b -> b) .
1045 foldr k z (build g) = g k z
1046
1047 "foldr/augment" forall k z xs (g::forall b. (a->b->b) -> b -> b) .
1048 foldr k z (augment g xs) = g k (foldr k z xs)
1049
1050 "foldr/id" foldr (:) [] = \x -> x
1051 "foldr/app" [1] forall ys. foldr (:) ys = \xs -> xs ++ ys
1052 -- Only activate this from phase 1, because that's
1053 -- when we disable the rule that expands (++) into foldr
1054
1055 -- The foldr/cons rule looks nice, but it can give disastrously
1056 -- bloated code when commpiling
1057 -- array (a,b) [(1,2), (2,2), (3,2), ...very long list... ]
1058 -- i.e. when there are very very long literal lists
1059 -- So I've disabled it for now. We could have special cases
1060 -- for short lists, I suppose.
1061 -- "foldr/cons" forall k z x xs. foldr k z (x:xs) = k x (foldr k z xs)
1062
1063 "foldr/single" forall k z x. foldr k z [x] = k x z
1064 "foldr/nil" forall k z. foldr k z [] = z
1065
1066 "foldr/cons/build" forall k z x (g::forall b. (a->b->b) -> b -> b) .
1067 foldr k z (x:build g) = k x (g k z)
1068
1069 "augment/build" forall (g::forall b. (a->b->b) -> b -> b)
1070 (h::forall b. (a->b->b) -> b -> b) .
1071 augment g (build h) = build (\c n -> g c (h c n))
1072 "augment/nil" forall (g::forall b. (a->b->b) -> b -> b) .
1073 augment g [] = build g
1074 #-}
1075
1076 -- This rule is true, but not (I think) useful:
1077 -- augment g (augment h t) = augment (\cn -> g c (h c n)) t
1078
1079 ----------------------------------------------
1080 -- map
1081 ----------------------------------------------
1082
1083 -- | /O(n)/. 'map' @f xs@ is the list obtained by applying @f@ to each element
1084 -- of @xs@, i.e.,
1085 --
1086 -- > map f [x1, x2, ..., xn] == [f x1, f x2, ..., f xn]
1087 -- > map f [x1, x2, ...] == [f x1, f x2, ...]
1088 --
1089 -- >>> map (+1) [1, 2, 3]
1090 --- [2,3,4]
1091
1092 map :: (a -> b) -> [a] -> [b]
1093 {-# NOINLINE [0] map #-}
1094 -- We want the RULEs "map" and "map/coerce" to fire first.
1095 -- map is recursive, so won't inline anyway,
1096 -- but saying so is more explicit, and silences warnings
1097 map _ [] = []
1098 map f (x:xs) = f x : map f xs
1099
1100 -- Note eta expanded
1101 mapFB :: (elt -> lst -> lst) -> (a -> elt) -> a -> lst -> lst
1102 {-# INLINE [0] mapFB #-} -- See Note [Inline FB functions] in GHC.List
1103 mapFB c f = \x ys -> c (f x) ys
1104
1105 {- Note [The rules for map]
1106 ~~~~~~~~~~~~~~~~~~~~~~~~~~~
1107 The rules for map work like this.
1108
1109 * Up to (but not including) phase 1, we use the "map" rule to
1110 rewrite all saturated applications of map with its build/fold
1111 form, hoping for fusion to happen.
1112
1113 In phase 1 and 0, we switch off that rule, inline build, and
1114 switch on the "mapList" rule, which rewrites the foldr/mapFB
1115 thing back into plain map.
1116
1117 It's important that these two rules aren't both active at once
1118 (along with build's unfolding) else we'd get an infinite loop
1119 in the rules. Hence the activation control below.
1120
1121 * This same pattern is followed by many other functions:
1122 e.g. append, filter, iterate, repeat, etc. in GHC.List
1123
1124 See also Note [Inline FB functions] in GHC.List
1125
1126 * The "mapFB" rule optimises compositions of map
1127
1128 * The "mapFB/id" rule gets rid of 'map id' calls.
1129 You might think that (mapFB c id) will turn into c simply
1130 when mapFB is inlined; but before that happens the "mapList"
1131 rule turns
1132 (foldr (mapFB (:) id) [] a
1133 back into
1134 map id
1135 Which is not very clever.
1136
1137 * Any similarity to the Functor laws for [] is expected.
1138 -}
1139
1140 {-# RULES
1141 "map" [~1] forall f xs. map f xs = build (\c n -> foldr (mapFB c f) n xs)
1142 "mapList" [1] forall f. foldr (mapFB (:) f) [] = map f
1143 "mapFB" forall c f g. mapFB (mapFB c f) g = mapFB c (f.g)
1144 "mapFB/id" forall c. mapFB c (\x -> x) = c
1145 #-}
1146
1147 -- See Breitner, Eisenberg, Peyton Jones, and Weirich, "Safe Zero-cost
1148 -- Coercions for Haskell", section 6.5:
1149 -- http://research.microsoft.com/en-us/um/people/simonpj/papers/ext-f/coercible.pdf
1150
1151 {-# RULES "map/coerce" [1] map coerce = coerce #-}
1152
1153
1154 ----------------------------------------------
1155 -- append
1156 ----------------------------------------------
1157
1158 -- | Append two lists, i.e.,
1159 --
1160 -- > [x1, ..., xm] ++ [y1, ..., yn] == [x1, ..., xm, y1, ..., yn]
1161 -- > [x1, ..., xm] ++ [y1, ...] == [x1, ..., xm, y1, ...]
1162 --
1163 -- If the first list is not finite, the result is the first list.
1164
1165 (++) :: [a] -> [a] -> [a]
1166 {-# NOINLINE [1] (++) #-} -- We want the RULE to fire first.
1167 -- It's recursive, so won't inline anyway,
1168 -- but saying so is more explicit
1169 (++) [] ys = ys
1170 (++) (x:xs) ys = x : xs ++ ys
1171
1172 {-# RULES
1173 "++" [~1] forall xs ys. xs ++ ys = augment (\c n -> foldr c n xs) ys
1174 #-}
1175
1176
1177 -- |'otherwise' is defined as the value 'True'. It helps to make
1178 -- guards more readable. eg.
1179 --
1180 -- > f x | x < 0 = ...
1181 -- > | otherwise = ...
1182 otherwise :: Bool
1183 otherwise = True
1184
1185 ----------------------------------------------
1186 -- Type Char and String
1187 ----------------------------------------------
1188
1189 -- | A 'String' is a list of characters. String constants in Haskell are values
1190 -- of type 'String'.
1191 --
1192 type String = [Char]
1193
1194 unsafeChr :: Int -> Char
1195 unsafeChr (I# i#) = C# (chr# i#)
1196
1197 -- | The 'Prelude.fromEnum' method restricted to the type 'Data.Char.Char'.
1198 ord :: Char -> Int
1199 ord (C# c#) = I# (ord# c#)
1200
1201 -- | This 'String' equality predicate is used when desugaring
1202 -- pattern-matches against strings.
1203 eqString :: String -> String -> Bool
1204 eqString [] [] = True
1205 eqString (c1:cs1) (c2:cs2) = c1 == c2 && cs1 `eqString` cs2
1206 eqString _ _ = False
1207
1208 {-# RULES "eqString" (==) = eqString #-}
1209 -- eqString also has a BuiltInRule in PrelRules.hs:
1210 -- eqString (unpackCString# (Lit s1)) (unpackCString# (Lit s2)) = s1==s2
1211
1212
1213 ----------------------------------------------
1214 -- 'Int' related definitions
1215 ----------------------------------------------
1216
1217 maxInt, minInt :: Int
1218
1219 {- Seems clumsy. Should perhaps put minInt and MaxInt directly into MachDeps.h -}
1220 #if WORD_SIZE_IN_BITS == 31
1221 minInt = I# (-0x40000000#)
1222 maxInt = I# 0x3FFFFFFF#
1223 #elif WORD_SIZE_IN_BITS == 32
1224 minInt = I# (-0x80000000#)
1225 maxInt = I# 0x7FFFFFFF#
1226 #else
1227 minInt = I# (-0x8000000000000000#)
1228 maxInt = I# 0x7FFFFFFFFFFFFFFF#
1229 #endif
1230
1231 ----------------------------------------------
1232 -- The function type
1233 ----------------------------------------------
1234
1235 -- | Identity function.
1236 --
1237 -- > id x = x
1238 id :: a -> a
1239 id x = x
1240
1241 -- Assertion function. This simply ignores its boolean argument.
1242 -- The compiler may rewrite it to @('assertError' line)@.
1243
1244 -- | If the first argument evaluates to 'True', then the result is the
1245 -- second argument. Otherwise an 'Control.Exception.AssertionFailed' exception
1246 -- is raised, containing a 'String' with the source file and line number of the
1247 -- call to 'assert'.
1248 --
1249 -- Assertions can normally be turned on or off with a compiler flag
1250 -- (for GHC, assertions are normally on unless optimisation is turned on
1251 -- with @-O@ or the @-fignore-asserts@
1252 -- option is given). When assertions are turned off, the first
1253 -- argument to 'assert' is ignored, and the second argument is
1254 -- returned as the result.
1255
1256 -- SLPJ: in 5.04 etc 'assert' is in GHC.Prim,
1257 -- but from Template Haskell onwards it's simply
1258 -- defined here in Base.hs
1259 assert :: Bool -> a -> a
1260 assert _pred r = r
1261
1262 breakpoint :: a -> a
1263 breakpoint r = r
1264
1265 breakpointCond :: Bool -> a -> a
1266 breakpointCond _ r = r
1267
1268 data Opaque = forall a. O a
1269 -- | @const x@ is a unary function which evaluates to @x@ for all inputs.
1270 --
1271 -- >>> const 42 "hello"
1272 -- 42
1273 --
1274 -- >>> map (const 42) [0..3]
1275 -- [42,42,42,42]
1276 const :: a -> b -> a
1277 const x _ = x
1278
1279 -- | Function composition.
1280 {-# INLINE (.) #-}
1281 -- Make sure it has TWO args only on the left, so that it inlines
1282 -- when applied to two functions, even if there is no final argument
1283 (.) :: (b -> c) -> (a -> b) -> a -> c
1284 (.) f g = \x -> f (g x)
1285
1286 -- | @'flip' f@ takes its (first) two arguments in the reverse order of @f@.
1287 --
1288 -- >>> flip (++) "hello" "world"
1289 -- "worldhello"
1290 flip :: (a -> b -> c) -> b -> a -> c
1291 flip f x y = f y x
1292
1293 -- | Application operator. This operator is redundant, since ordinary
1294 -- application @(f x)@ means the same as @(f '$' x)@. However, '$' has
1295 -- low, right-associative binding precedence, so it sometimes allows
1296 -- parentheses to be omitted; for example:
1297 --
1298 -- > f $ g $ h x = f (g (h x))
1299 --
1300 -- It is also useful in higher-order situations, such as @'map' ('$' 0) xs@,
1301 -- or @'Data.List.zipWith' ('$') fs xs@.
1302 --
1303 -- Note that @('$')@ is levity-polymorphic in its result type, so that
1304 -- @foo '$' True@ where @foo :: Bool -> Int#@ is well-typed.
1305 {-# INLINE ($) #-}
1306 ($) :: forall r a (b :: TYPE r). (a -> b) -> a -> b
1307 f $ x = f x
1308
1309 -- | Strict (call-by-value) application operator. It takes a function and an
1310 -- argument, evaluates the argument to weak head normal form (WHNF), then calls
1311 -- the function with that value.
1312
1313 ($!) :: forall r a (b :: TYPE r). (a -> b) -> a -> b
1314 f $! x = let !vx = x in f vx -- see #2273
1315
1316 -- | @'until' p f@ yields the result of applying @f@ until @p@ holds.
1317 until :: (a -> Bool) -> (a -> a) -> a -> a
1318 until p f = go
1319 where
1320 go x | p x = x
1321 | otherwise = go (f x)
1322
1323 -- | 'asTypeOf' is a type-restricted version of 'const'. It is usually
1324 -- used as an infix operator, and its typing forces its first argument
1325 -- (which is usually overloaded) to have the same type as the second.
1326 asTypeOf :: a -> a -> a
1327 asTypeOf = const
1328
1329 ----------------------------------------------
1330 -- Functor/Applicative/Monad instances for IO
1331 ----------------------------------------------
1332
1333 -- | @since 2.01
1334 instance Functor IO where
1335 fmap f x = x >>= (pure . f)
1336
1337 -- | @since 2.01
1338 instance Applicative IO where
1339 {-# INLINE pure #-}
1340 {-# INLINE (*>) #-}
1341 {-# INLINE liftA2 #-}
1342 pure = returnIO
1343 (*>) = thenIO
1344 (<*>) = ap
1345 liftA2 = liftM2
1346
1347 -- | @since 2.01
1348 instance Monad IO where
1349 {-# INLINE (>>) #-}
1350 {-# INLINE (>>=) #-}
1351 (>>) = (*>)
1352 (>>=) = bindIO
1353
1354 -- | @since 4.9.0.0
1355 instance Alternative IO where
1356 empty = failIO "mzero"
1357 (<|>) = mplusIO
1358
1359 -- | @since 4.9.0.0
1360 instance MonadPlus IO
1361
1362 returnIO :: a -> IO a
1363 returnIO x = IO (\ s -> (# s, x #))
1364
1365 bindIO :: IO a -> (a -> IO b) -> IO b
1366 bindIO (IO m) k = IO (\ s -> case m s of (# new_s, a #) -> unIO (k a) new_s)
1367
1368 thenIO :: IO a -> IO b -> IO b
1369 thenIO (IO m) k = IO (\ s -> case m s of (# new_s, _ #) -> unIO k new_s)
1370
1371 unIO :: IO a -> (State# RealWorld -> (# State# RealWorld, a #))
1372 unIO (IO a) = a
1373
1374 {- |
1375 Returns the tag of a constructor application; this function is used
1376 by the deriving code for Eq, Ord and Enum.
1377 -}
1378 {-# INLINE getTag #-}
1379 getTag :: a -> Int#
1380 getTag x = dataToTag# x
1381
1382 ----------------------------------------------
1383 -- Numeric primops
1384 ----------------------------------------------
1385
1386 -- Definitions of the boxed PrimOps; these will be
1387 -- used in the case of partial applications, etc.
1388
1389 {-# INLINE quotInt #-}
1390 {-# INLINE remInt #-}
1391
1392 quotInt, remInt, divInt, modInt :: Int -> Int -> Int
1393 (I# x) `quotInt` (I# y) = I# (x `quotInt#` y)
1394 (I# x) `remInt` (I# y) = I# (x `remInt#` y)
1395 (I# x) `divInt` (I# y) = I# (x `divInt#` y)
1396 (I# x) `modInt` (I# y) = I# (x `modInt#` y)
1397
1398 quotRemInt :: Int -> Int -> (Int, Int)
1399 (I# x) `quotRemInt` (I# y) = case x `quotRemInt#` y of
1400 (# q, r #) ->
1401 (I# q, I# r)
1402
1403 divModInt :: Int -> Int -> (Int, Int)
1404 (I# x) `divModInt` (I# y) = case x `divModInt#` y of
1405 (# q, r #) -> (I# q, I# r)
1406
1407 divModInt# :: Int# -> Int# -> (# Int#, Int# #)
1408 x# `divModInt#` y#
1409 | isTrue# (x# ># 0#) && isTrue# (y# <# 0#) =
1410 case (x# -# 1#) `quotRemInt#` y# of
1411 (# q, r #) -> (# q -# 1#, r +# y# +# 1# #)
1412 | isTrue# (x# <# 0#) && isTrue# (y# ># 0#) =
1413 case (x# +# 1#) `quotRemInt#` y# of
1414 (# q, r #) -> (# q -# 1#, r +# y# -# 1# #)
1415 | otherwise =
1416 x# `quotRemInt#` y#
1417
1418 -- Wrappers for the shift operations. The uncheckedShift# family are
1419 -- undefined when the amount being shifted by is greater than the size
1420 -- in bits of Int#, so these wrappers perform a check and return
1421 -- either zero or -1 appropriately.
1422 --
1423 -- Note that these wrappers still produce undefined results when the
1424 -- second argument (the shift amount) is negative.
1425
1426 -- | Shift the argument left by the specified number of bits
1427 -- (which must be non-negative).
1428 shiftL# :: Word# -> Int# -> Word#
1429 a `shiftL#` b | isTrue# (b >=# WORD_SIZE_IN_BITS#) = 0##
1430 | otherwise = a `uncheckedShiftL#` b
1431
1432 -- | Shift the argument right by the specified number of bits
1433 -- (which must be non-negative).
1434 -- The "RL" means "right, logical" (as opposed to RA for arithmetic)
1435 -- (although an arithmetic right shift wouldn't make sense for Word#)
1436 shiftRL# :: Word# -> Int# -> Word#
1437 a `shiftRL#` b | isTrue# (b >=# WORD_SIZE_IN_BITS#) = 0##
1438 | otherwise = a `uncheckedShiftRL#` b
1439
1440 -- | Shift the argument left by the specified number of bits
1441 -- (which must be non-negative).
1442 iShiftL# :: Int# -> Int# -> Int#
1443 a `iShiftL#` b | isTrue# (b >=# WORD_SIZE_IN_BITS#) = 0#
1444 | otherwise = a `uncheckedIShiftL#` b
1445
1446 -- | Shift the argument right (signed) by the specified number of bits
1447 -- (which must be non-negative).
1448 -- The "RA" means "right, arithmetic" (as opposed to RL for logical)
1449 iShiftRA# :: Int# -> Int# -> Int#
1450 a `iShiftRA#` b | isTrue# (b >=# WORD_SIZE_IN_BITS#) = if isTrue# (a <# 0#)
1451 then (-1#)
1452 else 0#
1453 | otherwise = a `uncheckedIShiftRA#` b
1454
1455 -- | Shift the argument right (unsigned) by the specified number of bits
1456 -- (which must be non-negative).
1457 -- The "RL" means "right, logical" (as opposed to RA for arithmetic)
1458 iShiftRL# :: Int# -> Int# -> Int#
1459 a `iShiftRL#` b | isTrue# (b >=# WORD_SIZE_IN_BITS#) = 0#
1460 | otherwise = a `uncheckedIShiftRL#` b
1461
1462 -- Rules for C strings (the functions themselves are now in GHC.CString)
1463 {-# RULES
1464 "unpack" [~1] forall a . unpackCString# a = build (unpackFoldrCString# a)
1465 "unpack-list" [1] forall a . unpackFoldrCString# a (:) [] = unpackCString# a
1466 "unpack-append" forall a n . unpackFoldrCString# a (:) n = unpackAppendCString# a n
1467
1468 -- There's a built-in rule (in PrelRules.hs) for
1469 -- unpackFoldr "foo" c (unpackFoldr "baz" c n) = unpackFoldr "foobaz" c n
1470
1471 #-}