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