Base.hs 47.5 KB
Newer Older
1
{-
2 3 4 5 6 7 8 9 10 11 12 13 14

NOTA BENE: Do NOT use ($) anywhere in this module! The type of ($) is
slightly magical (it can return unlifted types), and it is wired in.
But, it is also *defined* in this module, with a non-magical type.
GHC gets terribly confused (and *hangs*) if you try to use ($) in this
module, because it has different types in different scenarios.

This is not a problem in general, because the type ($), being wired in, is not
written out to the interface file, so importing files don't get confused.
The problem is only if ($) is used here. So don't!

---------------------------------------------

15 16 17
The overall structure of the GHC Prelude is a bit tricky.

  a) We want to avoid "orphan modules", i.e. ones with instance
Don Stewart's avatar
Don Stewart committed
18 19
        decls that don't belong either to a tycon or a class
        defined in the same module
20 21 22 23 24 25

  b) We want to avoid giant modules

So the rough structure is as follows, in (linearised) dependency order


26
GHC.Prim        Has no implementation.  It defines built-in things, and
Don Stewart's avatar
Don Stewart committed
27 28 29
                by importing it you bring them into scope.
                The source file is GHC.Prim.hi-boot, which is just
                copied to make GHC.Prim.hi
30

Don Stewart's avatar
Don Stewart committed
31 32
GHC.Base        Classes: Eq, Ord, Functor, Monad
                Types:   list, (), Int, Bool, Ordering, Char, String
33

Don Stewart's avatar
Don Stewart committed
34
Data.Tuple      Types: tuples, plus instances for GHC.Base classes
35

Don Stewart's avatar
Don Stewart committed
36
GHC.Show        Class: Show, plus instances for GHC.Base/GHC.Tup types
37

Don Stewart's avatar
Don Stewart committed
38
GHC.Enum        Class: Enum,  plus instances for GHC.Base/GHC.Tup types
39

Don Stewart's avatar
Don Stewart committed
40
Data.Maybe      Type: Maybe, plus instances for GHC.Base classes
41

Don Stewart's avatar
Don Stewart committed
42
GHC.List        List functions
43

Don Stewart's avatar
Don Stewart committed
44 45
GHC.Num         Class: Num, plus instances for Int
                Type:  Integer, plus instances for all classes so far (Eq, Ord, Num, Show)
46

Don Stewart's avatar
Don Stewart committed
47 48
                Integer is needed here because it is mentioned in the signature
                of 'fromInteger' in class Num
49

Don Stewart's avatar
Don Stewart committed
50 51 52
GHC.Real        Classes: Real, Integral, Fractional, RealFrac
                         plus instances for Int, Integer
                Types:  Ratio, Rational
53
                        plus instances for classes so far
54

Don Stewart's avatar
Don Stewart committed
55 56
                Rational is needed here because it is mentioned in the signature
                of 'toRational' in class Real
57

Don Stewart's avatar
Don Stewart committed
58
GHC.ST  The ST monad, instances and a few helper functions
59

Don Stewart's avatar
Don Stewart committed
60
Ix              Classes: Ix, plus instances for Int, Bool, Char, Integer, Ordering, tuples
61

Don Stewart's avatar
Don Stewart committed
62
GHC.Arr         Types: Array, MutableArray, MutableVar
63

Don Stewart's avatar
Don Stewart committed
64
                Arrays are used by a function in GHC.Float
65

Don Stewart's avatar
Don Stewart committed
66 67
GHC.Float       Classes: Floating, RealFloat
                Types:   Float, Double, plus instances of all classes so far
68

Don Stewart's avatar
Don Stewart committed
69 70 71
                This module contains everything to do with floating point.
                It is a big module (900 lines)
                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 79 80 81 82 83 84
{-# LANGUAGE CPP
           , NoImplicitPrelude
           , BangPatterns
           , ExplicitForAll
           , MagicHash
           , UnboxedTuples
           , ExistentialQuantification
85
           , RankNTypes
86
  #-}
87
-- -Wno-orphans is needed for things like:
88
-- Orphan rule: "x# -# x#" ALWAYS forall x# :: Int# -# x# x# = 0
89
{-# OPTIONS_GHC -Wno-orphans #-}
90
{-# OPTIONS_HADDOCK hide #-}
91

92 93 94 95 96
-----------------------------------------------------------------------------
-- |
-- Module      :  GHC.Base
-- Copyright   :  (c) The University of Glasgow, 1992-2002
-- License     :  see libraries/base/LICENSE
97
--
98 99 100 101 102
-- Maintainer  :  cvs-ghc@haskell.org
-- Stability   :  internal
-- Portability :  non-portable (GHC extensions)
--
-- Basic data types and classes.
103
--
104
-----------------------------------------------------------------------------
105 106 107 108

#include "MachDeps.h"

module GHC.Base
109 110 111 112 113 114 115 116 117 118 119
        (
        module GHC.Base,
        module GHC.Classes,
        module GHC.CString,
        module GHC.Magic,
        module GHC.Types,
        module GHC.Prim,        -- Re-export GHC.Prim and [boot] GHC.Err,
                                -- to avoid lots of people having to
        module GHC.Err          -- import it explicitly
  )
        where
120

121
import GHC.Types
122
import GHC.Classes
123
import GHC.CString
124
import GHC.Magic
125
import GHC.Prim
Simon Peyton Jones's avatar
Simon Peyton Jones committed
126
import GHC.Err
127
import {-# SOURCE #-} GHC.IO (failIO,mplusIO)
128

129 130
import GHC.Tuple ()     -- Note [Depend on GHC.Tuple]
import GHC.Integer ()   -- Note [Depend on GHC.Integer]
131

132 133 134 135 136 137 138 139
-- for 'class Semigroup'
import {-# SOURCE #-} GHC.Real (Integral)
import {-# SOURCE #-} Data.Semigroup.Internal ( stimesDefault
                                              , stimesMaybe
                                              , stimesList
                                              , stimesIdempotentMonoid
                                              )

140
infixr 9  .
141
infixr 5  ++
142
infixl 4  <$
143
infixl 1  >>, >>=
144
infixr 1  =<<
145
infixr 0  $, $!
146

147 148
infixl 4 <*>, <*, *>, <**>

Don Stewart's avatar
Don Stewart committed
149
default ()              -- Double isn't available yet
150

151
{-
152 153 154 155 156 157
Note [Depend on GHC.Integer]
~~~~~~~~~~~~~~~~~~~~~~~~~~~~
The Integer type is special because TidyPgm uses
GHC.Integer.Type.mkInteger to construct Integer literal values
Currently it reads the interface file whether or not the current
module *has* any Integer literals, so it's important that
Javran Cheng's avatar
Javran Cheng committed
158
GHC.Integer.Type (in package integer-gmp or integer-simple) is
159 160 161 162 163 164 165 166
compiled before any other module.  (There's a hack in GHC to disable
this for packages ghc-prim, integer-gmp, integer-simple, which aren't
allowed to contain any Integer literals.)

Likewise we implicitly need Integer when deriving things like Eq
instances.

The danger is that if the build system doesn't know about the dependency
167
on Integer, it'll compile some base module before GHC.Integer.Type,
168 169 170 171 172 173
resulting in:
  Failed to load interface for ‘GHC.Integer.Type’
    There are files missing in the ‘integer-gmp’ package,

Bottom line: we make GHC.Base depend on GHC.Integer; and everything
else either depends on GHC.Base, or does not have NoImplicitPrelude
Gabor Greif's avatar
Gabor Greif committed
174
(and hence depends on Prelude).
175 176 177 178

Note [Depend on GHC.Tuple]
~~~~~~~~~~~~~~~~~~~~~~~~~~
Similarly, tuple syntax (or ()) creates an implicit dependency on
Gabor Greif's avatar
Gabor Greif committed
179
GHC.Tuple, so we use the same rule as for Integer --- see Note [Depend on
180 181
GHC.Integer] --- to explain this to the build system.  We make GHC.Base
depend on GHC.Tuple, and everything else depends on GHC.Base or Prelude.
182
-}
183

184 185
#if 0
-- for use when compiling GHC.Base itself doesn't work
186
data  Bool  =  False | True
187
data Ordering = LT | EQ | GT
188 189 190 191 192 193 194 195 196 197
data Char = C# Char#
type  String = [Char]
data Int = I# Int#
data  ()  =  ()
data [] a = MkNil

not True = False
(&&) True True = True
otherwise = True

Eric Seidel's avatar
Eric Seidel committed
198 199
build = errorWithoutStackTrace "urk"
foldr = errorWithoutStackTrace "urk"
200
#endif
201 202 203 204 205 206 207 208 209 210 211 212 213 214

-- | The 'Maybe' type encapsulates an optional value.  A value of type
-- @'Maybe' a@ either contains a value of type @a@ (represented as @'Just' a@),
-- or it is empty (represented as 'Nothing').  Using 'Maybe' is a good way to
-- deal with errors or exceptional cases without resorting to drastic
-- measures such as 'error'.
--
-- The 'Maybe' type is also a monad.  It is a simple kind of error
-- monad, where all errors are represented by 'Nothing'.  A richer
-- error monad can be built using the 'Data.Either.Either' type.
--
data  Maybe a  =  Nothing | Just a
  deriving (Eq, Ord)

215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251
infixr 6 <>

-- | The class of semigroups (types with an associative binary operation).
--
-- Instances should satisfy the associativity law:
--
--  * @x '<>' (y '<>' z) = (x '<>' y) '<>' z@
--
-- @since 4.9.0.0
class Semigroup a where
        -- | An associative operation.
        (<>) :: a -> a -> a

        -- | Reduce a non-empty list with @\<\>@
        --
        -- The default definition should be sufficient, but this can be
        -- overridden for efficiency.
        --
        sconcat :: NonEmpty a -> a
        sconcat (a :| as) = go a as where
          go b (c:cs) = b <> go c cs
          go b []     = b

        -- | Repeat a value @n@ times.
        --
        -- Given that this works on a 'Semigroup' it is allowed to fail if
        -- you request 0 or fewer repetitions, and the default definition
        -- will do so.
        --
        -- By making this a member of the class, idempotent semigroups
        -- and monoids can upgrade this to execute in /O(1)/ by
        -- picking @stimes = 'stimesIdempotent'@ or @stimes =
        -- 'stimesIdempotentMonoid'@ respectively.
        stimes :: Integral b => b -> a -> a
        stimes = stimesDefault


252 253 254
-- | The class of monoids (types with an associative binary operation that
-- has an identity).  Instances should satisfy the following laws:
--
255
--  * @x '<>' 'mempty' = x@
256
--
257
--  * @'mempty' '<>' x = x@
258
--
259
--  * @x '<>' (y '<>' z) = (x '<>' y) '<>' z@ ('Semigroup' law)
260
--
261
--  * @'mconcat' = 'foldr' '(<>)' 'mempty'@
262 263 264 265 266 267 268 269
--
-- The method names refer to the monoid of lists under concatenation,
-- but there are many other instances.
--
-- Some types can be viewed as a monoid in more than one way,
-- e.g. both addition and multiplication on numbers.
-- In such cases we often define @newtype@s and make those instances
-- of 'Monoid', e.g. 'Sum' and 'Product'.
270 271 272 273
--
-- __NOTE__: 'Semigroup' is a superclass of 'Monoid' since /base-4.11.0.0/.
class Semigroup a => Monoid a where
        -- | Identity of 'mappend'
274
        mempty  :: a
275 276 277 278 279

        -- | An associative operation
        --
        -- __NOTE__: This method is redundant and has the default
        -- implementation @'mappend' = '(<>)'@ since /base-4.11.0.0/.
280
        mappend :: a -> a -> a
281 282
        mappend = (<>)
        {-# INLINE mappend #-}
283

284 285
        -- | Fold a list using the monoid.
        --
286 287 288
        -- For most types, the default definition for 'mconcat' will be
        -- used, but the function is included in the class definition so
        -- that an optimized version can be provided for specific types.
289
        mconcat :: [a] -> a
290 291
        mconcat = foldr mappend mempty

292 293 294 295 296 297 298
-- | @since 4.9.0.0
instance Semigroup [a] where
        (<>) = (++)
        {-# INLINE (<>) #-}

        stimes = stimesList

299
-- | @since 2.01
300
instance Monoid [a] where
301
        {-# INLINE mempty #-}
302
        mempty  = []
303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320
        {-# INLINE mconcat #-}
        mconcat xss = [x | xs <- xss, x <- xs]
-- See Note: [List comprehensions and inlining]

{-
Note: [List comprehensions and inlining]
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
The list monad operations are traditionally described in terms of concatMap:

xs >>= f = concatMap f xs

Similarly, mconcat for lists is just concat. Here in Base, however, we don't
have concatMap, and we'll refrain from adding it here so it won't have to be
hidden in imports. Instead, we use GHC's list comprehension desugaring
mechanism to define mconcat and the Applicative and Monad instances for lists.
We mark them INLINE because the inliner is not generally too keen to inline
build forms such as the ones these desugar to without our insistence.  Defining
these using list comprehensions instead of foldr has an additional potential
321
benefit, as described in compiler/deSugar/DsListComp.hs: if optimizations
322 323 324
needed to make foldr/build forms efficient are turned off, we'll get reasonably
efficient translations anyway.
-}
325

326 327 328 329 330 331 332 333 334
-- | @since 4.9.0.0
instance Semigroup (NonEmpty a) where
        (a :| as) <> ~(b :| bs) = a :| (as ++ b : bs)

-- | @since 4.9.0.0
instance Semigroup b => Semigroup (a -> b) where
        f <> g = \x -> f x <> g x
        stimes n f e = stimes n (f e)

335
-- | @since 2.01
336 337
instance Monoid b => Monoid (a -> b) where
        mempty _ = mempty
338 339 340 341 342 343

-- | @since 4.9.0.0
instance Semigroup () where
        _ <> _      = ()
        sconcat _   = ()
        stimes  _ _ = ()
344

345
-- | @since 2.01
346 347 348 349 350
instance Monoid () where
        -- Should it be strict?
        mempty        = ()
        mconcat _     = ()

351 352 353 354 355
-- | @since 4.9.0.0
instance (Semigroup a, Semigroup b) => Semigroup (a, b) where
        (a,b) <> (a',b') = (a<>a',b<>b')
        stimes n (a,b) = (stimes n a, stimes n b)

356
-- | @since 2.01
357 358
instance (Monoid a, Monoid b) => Monoid (a,b) where
        mempty = (mempty, mempty)
359 360 361 362 363

-- | @since 4.9.0.0
instance (Semigroup a, Semigroup b, Semigroup c) => Semigroup (a, b, c) where
        (a,b,c) <> (a',b',c') = (a<>a',b<>b',c<>c')
        stimes n (a,b,c) = (stimes n a, stimes n b, stimes n c)
364

365
-- | @since 2.01
366 367
instance (Monoid a, Monoid b, Monoid c) => Monoid (a,b,c) where
        mempty = (mempty, mempty, mempty)
368 369 370 371 372 373

-- | @since 4.9.0.0
instance (Semigroup a, Semigroup b, Semigroup c, Semigroup d)
         => Semigroup (a, b, c, d) where
        (a,b,c,d) <> (a',b',c',d') = (a<>a',b<>b',c<>c',d<>d')
        stimes n (a,b,c,d) = (stimes n a, stimes n b, stimes n c, stimes n d)
374

375
-- | @since 2.01
376 377
instance (Monoid a, Monoid b, Monoid c, Monoid d) => Monoid (a,b,c,d) where
        mempty = (mempty, mempty, mempty, mempty)
378 379 380 381 382 383 384

-- | @since 4.9.0.0
instance (Semigroup a, Semigroup b, Semigroup c, Semigroup d, Semigroup e)
         => Semigroup (a, b, c, d, e) where
        (a,b,c,d,e) <> (a',b',c',d',e') = (a<>a',b<>b',c<>c',d<>d',e<>e')
        stimes n (a,b,c,d,e) =
            (stimes n a, stimes n b, stimes n c, stimes n d, stimes n e)
385

386
-- | @since 2.01
387 388 389
instance (Monoid a, Monoid b, Monoid c, Monoid d, Monoid e) =>
                Monoid (a,b,c,d,e) where
        mempty = (mempty, mempty, mempty, mempty, mempty)
390 391 392 393 394 395 396 397 398


-- | @since 4.9.0.0
instance Semigroup Ordering where
    LT <> _ = LT
    EQ <> y = y
    GT <> _ = GT

    stimes = stimesIdempotentMonoid
399 400

-- lexicographical ordering
401
-- | @since 2.01
402
instance Monoid Ordering where
403 404 405 406 407 408 409 410 411
    mempty             = EQ

-- | @since 4.9.0.0
instance Semigroup a => Semigroup (Maybe a) where
    Nothing <> b       = b
    a       <> Nothing = a
    Just a  <> Just b  = Just (a <> b)

    stimes = stimesMaybe
412

413 414 415 416
-- | Lift a semigroup into 'Maybe' forming a 'Monoid' according to
-- <http://en.wikipedia.org/wiki/Monoid>: \"Any semigroup @S@ may be
-- turned into a monoid simply by adjoining an element @e@ not in @S@
-- and defining @e*e = e@ and @e*s = s = s*e@ for all @s ∈ S@.\" Since
417 418
-- there used to be no \"Semigroup\" typeclass providing just 'mappend',
-- we use 'Monoid' instead.
419 420
--
-- @since 2.01
421
instance Monoid a => Monoid (Maybe a) where
422
    mempty = Nothing
423

424 425 426 427 428 429 430 431
-- | For tuples, the 'Monoid' constraint on @a@ determines
-- how the first values merge.
-- For example, 'String's concatenate:
--
-- > ("hello ", (+15)) <*> ("world!", 2002)
-- > ("hello world!",2017)
--
-- @since 2.01
432 433
instance Monoid a => Applicative ((,) a) where
    pure x = (mempty, x)
434 435
    (u, f) <*> (v, x) = (u <> v, f x)
    liftA2 f (u, x) (v, y) = (u <> v, f x y)
436

437
-- | @since 4.9.0.0
438
instance Monoid a => Monad ((,) a) where
439 440 441 442 443
    (u, a) >>= k = case k a of (v, b) -> (u <> v, b)

-- | @since 4.10.0.0
instance Semigroup a => Semigroup (IO a) where
    (<>) = liftA2 (<>)
444

445
-- | @since 4.9.0.0
Gabriel439's avatar
Gabriel439 committed
446 447 448
instance Monoid a => Monoid (IO a) where
    mempty = pure mempty

449 450 451 452 453 454
{- | The 'Functor' class is used for types that can be mapped over.
Instances of 'Functor' should satisfy the following laws:

> fmap id  ==  id
> fmap (f . g)  ==  fmap f . fmap g

455
The instances of 'Functor' for lists, 'Data.Maybe.Maybe' and 'System.IO.IO'
456
satisfy these laws.
457 458
-}

459 460 461
class  Functor f  where
    fmap        :: (a -> b) -> f a -> f b

462 463 464 465 466 467
    -- | Replace all locations in the input with the same value.
    -- The default definition is @'fmap' . 'const'@, but this may be
    -- overridden with a more efficient version.
    (<$)        :: a -> f b -> f a
    (<$)        =  fmap . const

468 469 470 471
-- | A functor with application, providing operations to
--
-- * embed pure expressions ('pure'), and
--
472
-- * sequence computations and combine their results ('<*>' and 'liftA2').
473
--
474 475 476 477 478
-- A minimal complete definition must include implementations of 'pure'
-- and of either '<*>' or 'liftA2'. If it defines both, then they must behave
-- the same as their default definitions:
--
--      @('<*>') = 'liftA2' 'id'@
479
--
480 481 482
--      @'liftA2' f x y = f '<$>' x '<*>' y@
--
-- Further, any definition must satisfy the following:
483 484 485 486 487 488 489 490 491 492 493 494 495 496 497 498 499
--
-- [/identity/]
--
--      @'pure' 'id' '<*>' v = v@
--
-- [/composition/]
--
--      @'pure' (.) '<*>' u '<*>' v '<*>' w = u '<*>' (v '<*>' w)@
--
-- [/homomorphism/]
--
--      @'pure' f '<*>' 'pure' x = 'pure' (f x)@
--
-- [/interchange/]
--
--      @u '<*>' 'pure' y = 'pure' ('$' y) '<*>' u@
--
500
--
501 502 503
-- The other methods have the following default definitions, which may
-- be overridden with equivalent specialized implementations:
--
504
--   * @u '*>' v = ('id' '<$' u) '<*>' v@
505
--
506
--   * @u '<*' v = 'liftA2' 'const' u v@
507 508 509 510 511
--
-- As a consequence of these laws, the 'Functor' instance for @f@ will satisfy
--
--   * @'fmap' f x = 'pure' f '<*>' x@
--
512 513 514 515 516 517 518 519 520 521
--
-- It may be useful to note that supposing
--
--      @forall x y. p (q x y) = f x . g y@
--
-- it follows from the above that
--
--      @'liftA2' p ('liftA2' q u v) = 'liftA2' f u . 'liftA2' g v@
--
--
522 523 524 525 526 527
-- If @f@ is also a 'Monad', it should satisfy
--
--   * @'pure' = 'return'@
--
--   * @('<*>') = 'ap'@
--
quchen's avatar
quchen committed
528 529
--   * @('*>') = ('>>')@
--
530 531 532
-- (which implies that 'pure' and '<*>' satisfy the applicative functor laws).

class Functor f => Applicative f where
533
    {-# MINIMAL pure, ((<*>) | liftA2) #-}
534 535 536 537
    -- | Lift a value.
    pure :: a -> f a

    -- | Sequential application.
538 539 540
    --
    -- A few functors support an implementation of '<*>' that is more
    -- efficient than the default one.
541
    (<*>) :: f (a -> b) -> f a -> f b
542 543 544 545 546 547 548 549 550 551
    (<*>) = liftA2 id

    -- | Lift a binary function to actions.
    --
    -- Some functors support an implementation of 'liftA2' that is more
    -- efficient than the default one. In particular, if 'fmap' is an
    -- expensive operation, it is likely better to use 'liftA2' than to
    -- 'fmap' over the structure and then use '<*>'.
    liftA2 :: (a -> b -> c) -> f a -> f b -> f c
    liftA2 f x = (<*>) (fmap f x)
552 553 554

    -- | Sequence actions, discarding the value of the first argument.
    (*>) :: f a -> f b -> f b
555
    a1 *> a2 = (id <$ a1) <*> a2
556 557 558 559 560 561 562 563
    -- This is essentially the same as liftA2 (flip const), but if the
    -- Functor instance has an optimized (<$), it may be better to use
    -- that instead. Before liftA2 became a method, this definition
    -- was strictly better, but now it depends on the functor. For a
    -- functor supporting a sharing-enhancing (<$), this definition
    -- may reduce allocation by preventing a1 from ever being fully
    -- realized. In an implementation with a boring (<$) but an optimizing
    -- liftA2, it would likely be better to define (*>) using liftA2.
564 565 566 567 568 569 570

    -- | Sequence actions, discarding the value of the second argument.
    (<*) :: f a -> f b -> f a
    (<*) = liftA2 const

-- | A variant of '<*>' with the arguments reversed.
(<**>) :: Applicative f => f a -> f (a -> b) -> f b
571 572
(<**>) = liftA2 (\a f -> f a)
-- Don't use $ here, see the note at the top of the page
573 574 575 576 577

-- | Lift a function to actions.
-- This function may be used as a value for `fmap` in a `Functor` instance.
liftA :: Applicative f => (a -> b) -> f a -> f b
liftA f a = pure f <*> a
578 579
-- Caution: since this may be used for `fmap`, we can't use the obvious
-- definition of liftA = fmap.
580 581 582

-- | Lift a ternary function to actions.
liftA3 :: Applicative f => (a -> b -> c -> d) -> f a -> f b -> f c -> f d
583
liftA3 f a b c = liftA2 f a b <*> c
584 585


586
{-# INLINABLE liftA #-}
587 588
{-# SPECIALISE liftA :: (a1->r) -> IO a1 -> IO r #-}
{-# SPECIALISE liftA :: (a1->r) -> Maybe a1 -> Maybe r #-}
589
{-# INLINABLE liftA3 #-}
590 591 592
{-# SPECIALISE liftA3 :: (a1->a2->a3->r) -> IO a1 -> IO a2 -> IO a3 -> IO r #-}
{-# SPECIALISE liftA3 :: (a1->a2->a3->r) ->
                                Maybe a1 -> Maybe a2 -> Maybe a3 -> Maybe r #-}
593

594 595 596 597 598 599
-- | The 'join' function is the conventional monad join operator. It
-- is used to remove one level of monadic structure, projecting its
-- bound argument into the outer level.
join              :: (Monad m) => m (m a) -> m a
join x            =  x >>= id

600 601 602 603 604 605 606
{- | The 'Monad' class defines the basic operations over a /monad/,
a concept from a branch of mathematics known as /category theory/.
From the perspective of a Haskell programmer, however, it is best to
think of a monad as an /abstract datatype/ of actions.
Haskell's @do@ expressions provide a convenient syntax for writing
monadic expressions.

607 608
Instances of 'Monad' should satisfy the following laws:

609 610
* @'return' a '>>=' k  =  k a@
* @m '>>=' 'return'  =  m@
Vaibhav Sagar's avatar
Vaibhav Sagar committed
611
* @m '>>=' (\\x -> k x '>>=' h)  =  (m '>>=' k) '>>=' h@
612 613 614 615 616 617

Furthermore, the 'Monad' and 'Applicative' operations should relate as follows:

* @'pure' = 'return'@
* @('<*>') = 'ap'@

618
The above laws imply:
619

620 621
* @'fmap' f xs  =  xs '>>=' 'return' . f@
* @('>>') = ('*>')@
622

623
and that 'pure' and ('<*>') satisfy the applicative functor laws.
624

625 626
The instances of 'Monad' for lists, 'Data.Maybe.Maybe' and 'System.IO.IO'
defined in the "Prelude" satisfy these laws.
627
-}
628
class Applicative m => Monad m where
629 630
    -- | Sequentially compose two actions, passing any value produced
    -- by the first as an argument to the second.
631
    (>>=)       :: forall a b. m a -> (a -> m b) -> m b
632

633 634 635
    -- | Sequentially compose two actions, discarding any value produced
    -- by the first, like sequencing operators (such as the semicolon)
    -- in imperative languages.
636
    (>>)        :: forall a b. m a -> m b -> m b
637
    m >> k = m >>= \_ -> k -- See Note [Recursive bindings for Applicative/Monad]
638
    {-# INLINE (>>) #-}
639 640

    -- | Inject a value into the monadic type.
641
    return      :: a -> m a
642
    return      = pure
643

644 645 646
    -- | Fail with a message.  This operation is not part of the
    -- mathematical definition of a monad, but is invoked on pattern-match
    -- failure in a @do@ expression.
647 648 649 650 651
    --
    -- As part of the MonadFail proposal (MFP), this function is moved
    -- to its own class 'MonadFail' (see "Control.Monad.Fail" for more
    -- details). The definition here will be removed in a future
    -- release.
Don Stewart's avatar
Don Stewart committed
652
    fail        :: String -> m a
Eric Seidel's avatar
Eric Seidel committed
653
    fail s      = errorWithoutStackTrace s
654

655 656 657 658 659 660 661 662 663 664 665 666 667 668 669 670 671 672 673 674 675 676
{- Note [Recursive bindings for Applicative/Monad]
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

The original Applicative/Monad proposal stated that after
implementation, the designated implementation of (>>) would become

  (>>) :: forall a b. m a -> m b -> m b
  (>>) = (*>)

by default. You might be inclined to change this to reflect the stated
proposal, but you really shouldn't! Why? Because people tend to define
such instances the /other/ way around: in particular, it is perfectly
legitimate to define an instance of Applicative (*>) in terms of (>>),
which would lead to an infinite loop for the default implementation of
Monad! And people do this in the wild.

This turned into a nasty bug that was tricky to track down, and rather
than eliminate it everywhere upstream, it's easier to just retain the
original default.

-}

677 678 679 680 681
-- | Same as '>>=', but with the arguments interchanged.
{-# SPECIALISE (=<<) :: (a -> [b]) -> [a] -> [b] #-}
(=<<)           :: Monad m => (a -> m b) -> m a -> m b
f =<< x         = x >>= f

682
-- | Conditional execution of 'Applicative' expressions. For example,
683 684 685 686 687
--
-- > when debug (putStrLn "Debugging")
--
-- will output the string @Debugging@ if the Boolean value @debug@
-- is 'True', and otherwise do nothing.
688
when      :: (Applicative f) => Bool -> f () -> f ()
689
{-# INLINABLE when #-}
690 691
{-# SPECIALISE when :: Bool -> IO () -> IO () #-}
{-# SPECIALISE when :: Bool -> Maybe () -> Maybe () #-}
692
when p s  = if p then s else pure ()
693

694 695 696 697
-- | Evaluate each action in the sequence from left to right,
-- and collect the results.
sequence :: Monad m => [m a] -> m [a]
{-# INLINE sequence #-}
698 699
sequence = mapM id
-- Note: [sequence and mapM]
700 701 702 703

-- | @'mapM' f@ is equivalent to @'sequence' . 'map' f@.
mapM :: Monad m => (a -> m b) -> [a] -> m [b]
{-# INLINE mapM #-}
704 705 706
mapM f as = foldr k (return []) as
            where
              k a r = do { x <- f a; xs <- r; return (x:xs) }
707

708 709 710 711 712 713 714 715 716 717 718 719 720 721 722 723 724
{-
Note: [sequence and mapM]
~~~~~~~~~~~~~~~~~~~~~~~~~
Originally, we defined

mapM f = sequence . map f

This relied on list fusion to produce efficient code for mapM, and led to
excessive allocation in cryptarithm2. Defining

sequence = mapM id

relies only on inlining a tiny function (id) and beta reduction, which tends to
be a more reliable aspect of simplification. Indeed, this does not lead to
similar problems in nofib.
-}

725 726 727 728 729 730 731
-- | Promote a function to a monad.
liftM   :: (Monad m) => (a1 -> r) -> m a1 -> m r
liftM f m1              = do { x1 <- m1; return (f x1) }

-- | Promote a function to a monad, scanning the monadic arguments from
-- left to right.  For example,
--
quchen's avatar
quchen committed
732 733
-- > liftM2 (+) [0,1] [0,2] = [0,2,1,3]
-- > liftM2 (+) (Just 1) Nothing = Nothing
734 735 736
--
liftM2  :: (Monad m) => (a1 -> a2 -> r) -> m a1 -> m a2 -> m r
liftM2 f m1 m2          = do { x1 <- m1; x2 <- m2; return (f x1 x2) }
737 738
-- Caution: since this may be used for `liftA2`, we can't use the obvious
-- definition of liftM2 = liftA2.
739 740 741 742 743 744 745 746 747 748 749 750 751 752 753 754

-- | Promote a function to a monad, scanning the monadic arguments from
-- left to right (cf. 'liftM2').
liftM3  :: (Monad m) => (a1 -> a2 -> a3 -> r) -> m a1 -> m a2 -> m a3 -> m r
liftM3 f m1 m2 m3       = do { x1 <- m1; x2 <- m2; x3 <- m3; return (f x1 x2 x3) }

-- | Promote a function to a monad, scanning the monadic arguments from
-- left to right (cf. 'liftM2').
liftM4  :: (Monad m) => (a1 -> a2 -> a3 -> a4 -> r) -> m a1 -> m a2 -> m a3 -> m a4 -> m r
liftM4 f m1 m2 m3 m4    = do { x1 <- m1; x2 <- m2; x3 <- m3; x4 <- m4; return (f x1 x2 x3 x4) }

-- | Promote a function to a monad, scanning the monadic arguments from
-- left to right (cf. 'liftM2').
liftM5  :: (Monad m) => (a1 -> a2 -> a3 -> a4 -> a5 -> r) -> m a1 -> m a2 -> m a3 -> m a4 -> m a5 -> m r
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) }

755
{-# INLINABLE liftM #-}
756
{-# SPECIALISE liftM :: (a1->r) -> IO a1 -> IO r #-}
757
{-# SPECIALISE liftM :: (a1->r) -> Maybe a1 -> Maybe r #-}
758
{-# INLINABLE liftM2 #-}
759
{-# SPECIALISE liftM2 :: (a1->a2->r) -> IO a1 -> IO a2 -> IO r #-}
760
{-# SPECIALISE liftM2 :: (a1->a2->r) -> Maybe a1 -> Maybe a2 -> Maybe r #-}
761
{-# INLINABLE liftM3 #-}
762
{-# SPECIALISE liftM3 :: (a1->a2->a3->r) -> IO a1 -> IO a2 -> IO a3 -> IO r #-}
763
{-# SPECIALISE liftM3 :: (a1->a2->a3->r) -> Maybe a1 -> Maybe a2 -> Maybe a3 -> Maybe r #-}
764
{-# INLINABLE liftM4 #-}
765
{-# SPECIALISE liftM4 :: (a1->a2->a3->a4->r) -> IO a1 -> IO a2 -> IO a3 -> IO a4 -> IO r #-}
766
{-# SPECIALISE liftM4 :: (a1->a2->a3->a4->r) -> Maybe a1 -> Maybe a2 -> Maybe a3 -> Maybe a4 -> Maybe r #-}
767
{-# INLINABLE liftM5 #-}
768
{-# SPECIALISE liftM5 :: (a1->a2->a3->a4->a5->r) -> IO a1 -> IO a2 -> IO a3 -> IO a4 -> IO a5 -> IO r #-}
769
{-# SPECIALISE liftM5 :: (a1->a2->a3->a4->a5->r) -> Maybe a1 -> Maybe a2 -> Maybe a3 -> Maybe a4 -> Maybe a5 -> Maybe r #-}
770 771

{- | In many situations, the 'liftM' operations can be replaced by uses of
772
'ap', which promotes function application.
773

quchen's avatar
quchen committed
774
> return f `ap` x1 `ap` ... `ap` xn
775

776
is equivalent to
777

quchen's avatar
quchen committed
778
> liftMn f x1 x2 ... xn
779 780 781 782

-}

ap                :: (Monad m) => m (a -> b) -> m a -> m b
783 784 785
ap m1 m2          = do { x1 <- m1; x2 <- m2; return (x1 x2) }
-- Since many Applicative instances define (<*>) = ap, we
-- cannot define ap = (<*>)
786
{-# INLINABLE ap #-}
787 788
{-# SPECIALISE ap :: IO (a -> b) -> IO a -> IO b #-}
{-# SPECIALISE ap :: Maybe (a -> b) -> Maybe a -> Maybe b #-}
789 790 791

-- instances for Prelude types

792
-- | @since 2.01
793 794 795
instance Functor ((->) r) where
    fmap = (.)

796
-- | @since 2.01
797 798 799
instance Applicative ((->) a) where
    pure = const
    (<*>) f g x = f x (g x)
800
    liftA2 q f g x = q (f x) (g x)
801

802
-- | @since 2.01
803 804 805
instance Monad ((->) r) where
    f >>= k = \ r -> k (f r) r

806
-- | @since 2.01
807 808
instance Functor ((,) a) where
    fmap f (x,y) = (x, f y)
809

810
-- | @since 2.01
811 812 813 814
instance  Functor Maybe  where
    fmap _ Nothing       = Nothing
    fmap f (Just a)      = Just (f a)

815
-- | @since 2.01
816
instance Applicative Maybe where
817 818 819 820 821
    pure = Just

    Just f  <*> m       = fmap f m
    Nothing <*> _m      = Nothing

822 823 824
    liftA2 f (Just x) (Just y) = Just (f x y)
    liftA2 _ _ _ = Nothing

825 826
    Just _m1 *> m2      = m2
    Nothing  *> _m2     = Nothing
827

828
-- | @since 2.01
829 830 831 832
instance  Monad Maybe  where
    (Just x) >>= k      = k x
    Nothing  >>= _      = Nothing

833
    (>>) = (*>)
834 835 836

    fail _              = Nothing

837 838 839 840 841 842 843 844 845 846
-- -----------------------------------------------------------------------------
-- The Alternative class definition

infixl 3 <|>

-- | A monoid on applicative functors.
--
-- If defined, 'some' and 'many' should be the least solutions
-- of the equations:
--
quchen's avatar
quchen committed
847
-- * @'some' v = (:) '<$>' v '<*>' 'many' v@
848
--
quchen's avatar
quchen committed
849
-- * @'many' v = 'some' v '<|>' 'pure' []@
850 851 852 853 854 855 856 857 858 859 860
class Applicative f => Alternative f where
    -- | The identity of '<|>'
    empty :: f a
    -- | An associative binary operation
    (<|>) :: f a -> f a -> f a

    -- | One or more.
    some :: f a -> f [a]
    some v = some_v
      where
        many_v = some_v <|> pure []
861
        some_v = liftA2 (:) v many_v
862 863 864 865 866 867

    -- | Zero or more.
    many :: f a -> f [a]
    many v = many_v
      where
        many_v = some_v <|> pure []
868
        some_v = liftA2 (:) v many_v
869 870


871
-- | @since 2.01
872 873 874 875 876 877 878 879 880 881 882 883 884 885 886 887 888 889 890 891 892 893
instance Alternative Maybe where
    empty = Nothing
    Nothing <|> r = r
    l       <|> _ = l

-- -----------------------------------------------------------------------------
-- The MonadPlus class definition

-- | Monads that also support choice and failure.
class (Alternative m, Monad m) => MonadPlus m where
   -- | the identity of 'mplus'.  It should also satisfy the equations
   --
   -- > mzero >>= f  =  mzero
   -- > v >> mzero   =  mzero
   --
   mzero :: m a
   mzero = empty

   -- | an associative operation
   mplus :: m a -> m a -> m a
   mplus = (<|>)

894
-- | @since 2.01
895
instance MonadPlus Maybe
896

897 898 899 900 901 902 903 904 905 906 907 908 909 910 911 912 913 914 915 916 917 918 919 920 921 922 923 924 925
---------------------------------------------
-- The non-empty list type

infixr 5 :|

-- | Non-empty (and non-strict) list type.
--
-- @since 4.9.0.0
data NonEmpty a = a :| [a]
  deriving (Eq, Ord)

-- | @since 4.9.0.0
instance Functor NonEmpty where
  fmap f ~(a :| as) = f a :| fmap f as
  b <$ ~(_ :| as)   = b   :| (b <$ as)

-- | @since 4.9.0.0
instance Applicative NonEmpty where
  pure a = a :| []
  (<*>) = ap
  liftA2 = liftM2

-- | @since 4.9.0.0
instance Monad NonEmpty where
  ~(a :| as) >>= f = b :| (bs ++ bs')
    where b :| bs = f a
          bs' = as >>= toList . f
          toList ~(c :| cs) = c : cs

926 927
----------------------------------------------
-- The list type
928

929
-- | @since 2.01
930
instance Functor [] where
931
    {-# INLINE fmap #-}
932 933
    fmap = map

934
-- See Note: [List comprehensions and inlining]
935
-- | @since 2.01
936
instance Applicative [] where
937 938 939 940
    {-# INLINE pure #-}
    pure x    = [x]
    {-# INLINE (<*>) #-}
    fs <*> xs = [f x | f <- fs, x <- xs]
941 942
    {-# INLINE liftA2 #-}
    liftA2 f xs ys = [f x y | x <- xs, y <- ys]
943 944 945 946
    {-# INLINE (*>) #-}
    xs *> ys  = [y | _ <- xs, y <- ys]

-- See Note: [List comprehensions and inlining]
947
-- | @since 2.01
948 949 950 951 952 953
instance Monad []  where
    {-# INLINE (>>=) #-}
    xs >>= f             = [y | x <- xs, y <- f x]
    {-# INLINE (>>) #-}
    (>>) = (*>)
    {-# INLINE fail #-}
Don Stewart's avatar
Don Stewart committed
954
    fail _              = []
955

956
-- | @since 2.01
957 958 959 960
instance Alternative [] where
    empty = []
    (<|>) = (++)

961
-- | @since 2.01
962
instance MonadPlus []
963

964
{-
965 966
A few list functions that appear here because they are used here.
The rest of the prelude list functions are in GHC.List.
967
-}
968 969

----------------------------------------------
Don Stewart's avatar
Don Stewart committed
970
--      foldr/build/augment
971
----------------------------------------------
972

973 974 975 976 977 978
-- | 'foldr', applied to a binary operator, a starting value (typically
-- the right-identity of the operator), and a list, reduces the list
-- using the binary operator, from right to left:
--
-- > foldr f z [x1, x2, ..., xn] == x1 `f` (x2 `f` ... (xn `f` z)...)

979 980 981
foldr            :: (a -> b -> b) -> b -> [a] -> b
-- foldr _ z []     =  z
-- foldr f z (x:xs) =  f x (foldr f z xs)
Simon Marlow's avatar
Simon Marlow committed
982 983
{-# INLINE [0] foldr #-}
-- Inline only in the final stage, after the foldr/cons rule has had a chance
984
-- Also note that we inline it when it has *two* parameters, which are the
985 986 987 988 989
-- ones we are keen about specialising!
foldr k z = go
          where
            go []     = z
            go (y:ys) = y `k` go ys
990

991 992 993
-- | A list producer that can be fused with 'foldr'.
-- This function is merely
--
Don Stewart's avatar
Don Stewart committed
994
-- >    build g = g (:) []
995 996 997 998 999
--
-- but GHC's simplifier will transform an expression of the form
-- @'foldr' k z ('build' g)@, which may arise after inlining, to @g k z@,
-- which avoids producing an intermediate list.

Don Stewart's avatar
Don Stewart committed
1000
build   :: forall a. (forall b. (a -> b -> b) -> b -> b) -> [a]
1001
{-# INLINE [1] build #-}
Don Stewart's avatar
Don Stewart committed
1002 1003 1004 1005 1006 1007
        -- The INLINE is important, even though build is tiny,
        -- because it prevents [] getting inlined in the version that
        -- appears in the interface file.  If [] *is* inlined, it
        -- won't match with [] appearing in rules in an importing module.
        --
        -- The "1" says to inline in phase 1
1008 1009 1010

build g = g (:) []

1011 1012 1013
-- | A list producer that can be fused with 'foldr'.
-- This function is merely
--
Don Stewart's avatar
Don Stewart committed
1014
-- >    augment g xs = g (:) xs
1015 1016 1017 1018 1019
--
-- but GHC's simplifier will transform an expression of the form
-- @'foldr' k z ('augment' g xs)@, which may arise after inlining, to
-- @g k ('foldr' k z xs)@, which avoids producing an intermediate list.

1020
augment :: forall a. (forall b. (a->b->b) -> b -> b) -> [a] -> [a]
1021
{-# INLINE [1] augment #-}
1022 1023 1024
augment g xs = g (:) xs

{-# RULES
1025
"fold/build"    forall k z (g::forall b. (a->b->b) -> b -> b) .
Don Stewart's avatar
Don Stewart committed
1026
                foldr k z (build g) = g k z
1027

1028
"foldr/augment" forall k z xs (g::forall b. (a->b->b) -> b -> b) .
Don Stewart's avatar
Don Stewart committed
1029
                foldr k z (augment g xs) = g k (foldr k z xs)
1030

Don Stewart's avatar
Don Stewart committed
1031 1032 1033 1034
"foldr/id"                        foldr (:) [] = \x  -> x
"foldr/app"     [1] forall ys. foldr (:) ys = \xs -> xs ++ ys
        -- Only activate this from phase 1, because that's
        -- when we disable the rule that expands (++) into foldr
1035

1036 1037
-- The foldr/cons rule looks nice, but it can give disastrously
-- bloated code when commpiling
Don Stewart's avatar
Don Stewart committed
1038
--      array (a,b) [(1,2), (2,2), (3,2), ...very long list... ]
1039 1040 1041
-- i.e. when there are very very long literal lists
-- So I've disabled it for now. We could have special cases
-- for short lists, I suppose.
Don Stewart's avatar
Don Stewart committed
1042
-- "foldr/cons" forall k z x xs. foldr k z (x:xs) = k x (foldr k z xs)
1043

Don Stewart's avatar
Don Stewart committed
1044
"foldr/single"  forall k z x. foldr k z [x] = k x z
1045
"foldr/nil"     forall k z.   foldr k z []  = z
1046

1047 1048 1049
"foldr/cons/build" forall k z x (g::forall b. (a->b->b) -> b -> b) .
                           foldr k z (x:build g) = k x (g k z)

1050
"augment/build" forall (g::forall b. (a->b->b) -> b -> b)
Don Stewart's avatar
Don Stewart committed
1051 1052
                       (h::forall b. (a->b->b) -> b -> b) .
                       augment g (build h) = build (\c n -> g c (h c n))
1053
"augment/nil"   forall (g::forall b. (a->b->b) -> b -> b) .
Don Stewart's avatar
Don Stewart committed
1054
                        augment g [] = build g
1055 1056 1057
 #-}

-- This rule is true, but not (I think) useful:
Don Stewart's avatar
Don Stewart committed
1058
--      augment g (augment h t) = augment (\cn -> g c (h c n)) t
1059 1060

----------------------------------------------
1061
--              map
1062 1063
----------------------------------------------

1064 1065 1066 1067 1068 1069
-- | 'map' @f xs@ is the list obtained by applying @f@ to each element
-- of @xs@, i.e.,
--
-- > map f [x1, x2, ..., xn] == [f x1, f x2, ..., f xn]
-- > map f [x1, x2, ...] == [f x1, f x2, ...]

1070
map :: (a -> b) -> [a] -> [b]
1071 1072 1073 1074
{-# NOINLINE [0] map #-}
  -- We want the RULEs "map" and "map/coerce" to fire first.
  -- map is recursive, so won't inline anyway,
  -- but saying so is more explicit, and silences warnings
1075 1076
map _ []     = []
map f (x:xs) = f x : map f xs
1077 1078 1079

-- Note eta expanded
mapFB ::  (elt -> lst -> lst) -> (a -> elt) -> a -> lst -> lst
1080
{-# INLINE [0] mapFB #-} -- See Note [Inline FB functions] in GHC.List
1081
mapFB c f = \x ys -> c (f x) ys
1082

Simon Peyton Jones's avatar
Simon Peyton Jones committed
1083 1084 1085 1086 1087 1088 1089 1090 1091 1092 1093 1094 1095 1096 1097 1098 1099 1100 1101 1102 1103 1104 1105
{- Note [The rules for map]
~~~~~~~~~~~~~~~~~~~~~~~~~~~
The rules for map work like this.

* Up to (but not including) phase 1, we use the "map" rule to
  rewrite all saturated applications of map with its build/fold
  form, hoping for fusion to happen.

  In phase 1 and 0, we switch off that rule, inline build, and
  switch on the "mapList" rule, which rewrites the foldr/mapFB
  thing back into plain map.

  It's important that these two rules aren't both active at once
  (along with build's unfolding) else we'd get an infinite loop
  in the rules.  Hence the activation control below.

* This same pattern is followed by many other functions:
  e.g. append, filter, iterate, repeat, etc. in GHC.List

  See also Note [Inline FB functions] in GHC.List

* The "mapFB" rule optimises compositions of map

Gabor Greif's avatar
Gabor Greif committed
1106
* The "mapFB/id" rule gets rid of 'map id' calls.
Simon Peyton Jones's avatar
Simon Peyton Jones committed
1107 1108 1109 1110 1111 1112
  You might think that (mapFB c id) will turn into c simply
  when mapFB is inlined; but before that happens the "mapList"
  rule turns
     (foldr (mapFB (:) id) [] a
  back into
     map id
Gabor Greif's avatar
Gabor Greif committed
1113
  Which is not very clever.
Simon Peyton Jones's avatar
Simon Peyton Jones committed
1114 1115 1116

* Any similarity to the Functor laws for [] is expected.
-}
1117 1118

{-# RULES
Don Stewart's avatar
Don Stewart committed
1119 1120
"map"       [~1] forall f xs.   map f xs                = build (\c n -> foldr (mapFB c f) n xs)
"mapList"   [1]  forall f.      foldr (mapFB (:) f) []  = map f
1121
"mapFB"     forall c f g.       mapFB (mapFB c f) g     = mapFB c (f.g)
1122
"mapFB/id"  forall c.           mapFB c (\x -> x)       = c
1123
  #-}
1124

David Feuer's avatar
David Feuer committed
1125 1126
-- See Breitner, Eisenberg, Peyton Jones, and Weirich, "Safe Zero-cost
-- Coercions for Haskell", section 6.5:
1127 1128
--   http://research.microsoft.com/en-us/um/people/simonpj/papers/ext-f/coercible.pdf

1129
{-# RULES "map/coerce" [1] map coerce = coerce #-}
1130

1131 1132

----------------------------------------------
1133
--              append
1134
----------------------------------------------
1135

1136 1137 1138 1139 1140 1141 1142
-- | Append two lists, i.e.,
--
-- > [x1, ..., xm] ++ [y1, ..., yn] == [x1, ..., xm, y1, ..., yn]
-- > [x1, ..., xm] ++ [y1, ...] == [x1, ..., xm, y1, ...]
--
-- If the first list is not finite, the result is the first list.

1143
(++) :: [a] -> [a] -> [a]
1144 1145
{-# NOINLINE [1] (++) #-}    -- We want the RULE to fire first.
                             -- It's recursive, so won't inline anyway,
Simon Peyton Jones's avatar
Simon Peyton Jones committed
1146
                             -- but saying so is more explicit
1147 1148
(++) []     ys = ys
(++) (x:xs) ys = x : xs ++ ys
1149 1150

{-# RULES
Don Stewart's avatar
Don Stewart committed
1151
"++"    [~1] forall xs ys. xs ++ ys = augment (\c n -> foldr c n xs) ys
1152 1153 1154
  #-}


1155
-- |'otherwise' is defined as the value 'True'.  It helps to make
1156 1157
-- guards more readable.  eg.
--
1158
-- >  f x | x < 0     = ...
1159
-- >      | otherwise = ...
Don Stewart's avatar
Don Stewart committed
1160 1161
otherwise               :: Bool
otherwise               =  True
1162

1163 1164 1165
----------------------------------------------
-- Type Char and String
----------------------------------------------
1166

1167 1168 1169
-- | A 'String' is a list of characters.  String constants in Haskell are values
-- of type 'String'.
--
1170 1171 1172 1173 1174
type String = [Char]

unsafeChr :: Int -> Char
unsafeChr (I# i#) = C# (chr# i#)

1175
-- | The 'Prelude.fromEnum' method restricted to the type 'Data.Char.Char'.
1176 1177 1178
ord :: Char -> Int
ord (C# c#) = I# (ord# c#)

1179 1180
-- | This 'String' equality predicate is used when desugaring
-- pattern-matches against strings.
1181
eqString :: String -> String -> Bool
Don Stewart's avatar
Don Stewart committed
1182
eqString []       []       = True
1183
eqString (c1:cs1) (c2:cs2) = c1 == c2 && cs1 `eqString` cs2
Ian Lynagh's avatar
Ian Lynagh committed
1184
eqString _        _        = False
1185 1186

{-# RULES "eqString" (==) = eqString #-}
1187
-- eqString also has a BuiltInRule in PrelRules.hs:
1188
--      eqString (unpackCString# (Lit s1)) (unpackCString# (Lit s2)) = s1==s2
1189

1190

1191 1192 1193
----------------------------------------------
-- 'Int' related definitions
----------------------------------------------
1194

1195
maxInt, minInt :: Int
1196 1197 1198 1199 1200 1201

{- Seems clumsy. Should perhaps put minInt and MaxInt directly into MachDeps.h -}
#if WORD_SIZE_IN_BITS == 31
minInt  = I# (-0x40000000#)
maxInt  = I# 0x3FFFFFFF#
#elif WORD_SIZE_IN_BITS == 32
1202 1203
minInt  = I# (-0x80000000#)
maxInt  = I# 0x7FFFFFFF#
1204
#else
1205 1206 1207 1208
minInt  = I# (-0x8000000000000000#)
maxInt  = I# 0x7FFFFFFFFFFFFFFF#
#endif

1209 1210 1211
----------------------------------------------
-- The function type
----------------------------------------------
1212

1213
-- | Identity function.
quchen's avatar
quchen committed
1214 1215
--
-- > id x = x
Don Stewart's avatar
Don Stewart committed
1216 1217
id                      :: a -> a
id x                    =  x
1218

ross's avatar