Base.hs 41.7 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
infixr 9  .
133
infixr 5  ++
134
infixl 4  <$
135
infixl 1  >>, >>=
136
infixr 1  =<<
137
infixr 0  $, $!
138

139 140
infixl 4 <*>, <*, *>, <**>

Don Stewart's avatar
Don Stewart committed
141
default ()              -- Double isn't available yet
142

143
{-
144 145 146 147 148 149
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
150
GHC.Integer.Type (in package integer-gmp or integer-simple) is
151 152 153 154 155 156 157 158
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
159
on Integer, it'll compile some base module before GHC.Integer.Type,
160 161 162 163 164 165
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
166
(and hence depends on Prelude).
167 168 169 170

Note [Depend on GHC.Tuple]
~~~~~~~~~~~~~~~~~~~~~~~~~~
Similarly, tuple syntax (or ()) creates an implicit dependency on
Gabor Greif's avatar
Gabor Greif committed
171
GHC.Tuple, so we use the same rule as for Integer --- see Note [Depend on
172 173
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.
174
-}
175

176 177
#if 0
-- for use when compiling GHC.Base itself doesn't work
178
data  Bool  =  False | True
179
data Ordering = LT | EQ | GT
180 181 182 183 184 185 186 187 188 189
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
190 191
build = errorWithoutStackTrace "urk"
foldr = errorWithoutStackTrace "urk"
192
#endif
193 194 195 196 197 198 199 200 201 202 203 204 205 206

-- | 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)

207 208 209 210 211 212 213 214 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
-- | The class of monoids (types with an associative binary operation that
-- has an identity).  Instances should satisfy the following laws:
--
--  * @mappend mempty x = x@
--
--  * @mappend x mempty = x@
--
--  * @mappend x (mappend y z) = mappend (mappend x y) z@
--
--  * @mconcat = 'foldr' mappend mempty@
--
-- 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'.

class Monoid a where
        mempty  :: a
        -- ^ Identity of 'mappend'
        mappend :: a -> a -> a
        -- ^ An associative operation
        mconcat :: [a] -> a

        -- ^ Fold a list using the monoid.
        -- 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.

        mconcat = foldr mappend mempty

240
-- | @since 2.01
241
instance Monoid [a] where
242
        {-# INLINE mempty #-}
243
        mempty  = []
244
        {-# INLINE mappend #-}
245
        mappend = (++)
246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267
        {-# 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
benefit, as described in compiler/deSugar/DsListComp.lhs: if optimizations
needed to make foldr/build forms efficient are turned off, we'll get reasonably
efficient translations anyway.
-}
268

269
-- | @since 2.01
270 271 272 273
instance Monoid b => Monoid (a -> b) where
        mempty _ = mempty
        mappend f g x = f x `mappend` g x

274
-- | @since 2.01
275 276 277 278 279 280
instance Monoid () where
        -- Should it be strict?
        mempty        = ()
        _ `mappend` _ = ()
        mconcat _     = ()

281
-- | @since 2.01
282 283 284 285 286
instance (Monoid a, Monoid b) => Monoid (a,b) where
        mempty = (mempty, mempty)
        (a1,b1) `mappend` (a2,b2) =
                (a1 `mappend` a2, b1 `mappend` b2)

287
-- | @since 2.01
288 289 290 291 292
instance (Monoid a, Monoid b, Monoid c) => Monoid (a,b,c) where
        mempty = (mempty, mempty, mempty)
        (a1,b1,c1) `mappend` (a2,b2,c2) =
                (a1 `mappend` a2, b1 `mappend` b2, c1 `mappend` c2)

293
-- | @since 2.01
294 295 296 297 298 299
instance (Monoid a, Monoid b, Monoid c, Monoid d) => Monoid (a,b,c,d) where
        mempty = (mempty, mempty, mempty, mempty)
        (a1,b1,c1,d1) `mappend` (a2,b2,c2,d2) =
                (a1 `mappend` a2, b1 `mappend` b2,
                 c1 `mappend` c2, d1 `mappend` d2)

300
-- | @since 2.01
301 302 303 304 305 306 307 308
instance (Monoid a, Monoid b, Monoid c, Monoid d, Monoid e) =>
                Monoid (a,b,c,d,e) where
        mempty = (mempty, mempty, mempty, mempty, mempty)
        (a1,b1,c1,d1,e1) `mappend` (a2,b2,c2,d2,e2) =
                (a1 `mappend` a2, b1 `mappend` b2, c1 `mappend` c2,
                 d1 `mappend` d2, e1 `mappend` e2)

-- lexicographical ordering
309
-- | @since 2.01
310 311 312 313 314 315
instance Monoid Ordering where
        mempty         = EQ
        LT `mappend` _ = LT
        EQ `mappend` y = y
        GT `mappend` _ = GT

316 317 318 319 320 321
-- | 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
-- there is no \"Semigroup\" typeclass providing just 'mappend', we
-- use 'Monoid' instead.
322 323
--
-- @since 2.01
324 325 326 327 328 329
instance Monoid a => Monoid (Maybe a) where
  mempty = Nothing
  Nothing `mappend` m = m
  m `mappend` Nothing = m
  Just m1 `mappend` Just m2 = Just (m1 `mappend` m2)

330
-- | @since 2.01
331 332 333 334
instance Monoid a => Applicative ((,) a) where
    pure x = (mempty, x)
    (u, f) <*> (v, x) = (u `mappend` v, f x)

335
-- | @since 4.9.0.0
336 337
instance Monoid a => Monad ((,) a) where
    (u, a) >>= k = case k a of (v, b) -> (u `mappend` v, b)
338

339
-- | @since 4.9.0.0
Gabriel439's avatar
Gabriel439 committed
340 341 342 343
instance Monoid a => Monoid (IO a) where
    mempty = pure mempty
    mappend = liftA2 mappend

ross's avatar
ross committed
344 345 346 347 348 349
{- | 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

ross's avatar
ross committed
350
The instances of 'Functor' for lists, 'Data.Maybe.Maybe' and 'System.IO.IO'
351
satisfy these laws.
ross's avatar
ross committed
352 353
-}

354 355 356
class  Functor f  where
    fmap        :: (a -> b) -> f a -> f b

357 358 359 360 361 362
    -- | 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

363 364 365 366 367 368 369 370 371 372 373 374 375 376 377 378 379 380 381 382 383 384 385 386 387 388 389 390 391 392 393 394 395 396 397 398 399 400 401 402 403 404 405 406 407 408 409 410 411 412 413 414 415
-- | A functor with application, providing operations to
--
-- * embed pure expressions ('pure'), and
--
-- * sequence computations and combine their results ('<*>').
--
-- A minimal complete definition must include implementations of these
-- functions satisfying the following laws:
--
-- [/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@
--
-- The other methods have the following default definitions, which may
-- be overridden with equivalent specialized implementations:
--
--   * @u '*>' v = 'pure' ('const' 'id') '<*>' u '<*>' v@
--
--   * @u '<*' v = 'pure' 'const' '<*>' u '<*>' v@
--
-- As a consequence of these laws, the 'Functor' instance for @f@ will satisfy
--
--   * @'fmap' f x = 'pure' f '<*>' x@
--
-- If @f@ is also a 'Monad', it should satisfy
--
--   * @'pure' = 'return'@
--
--   * @('<*>') = 'ap'@
--
-- (which implies that 'pure' and '<*>' satisfy the applicative functor laws).

class Functor f => Applicative f where
    -- | Lift a value.
    pure :: a -> f a

    -- | Sequential application.
    (<*>) :: f (a -> b) -> f a -> f b

    -- | Sequence actions, discarding the value of the first argument.
    (*>) :: f a -> f b -> f b
David Feuer's avatar
David Feuer committed
416 417 418
    a1 *> a2 = (id <$ a1) <*> a2
    -- This is essentially the same as liftA2 (const id), but if the
    -- Functor instance has an optimized (<$), we want to use that instead.
419 420 421 422 423 424 425 426 427 428 429 430 431

    -- | 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
(<**>) = liftA2 (flip ($))

-- | 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
David Feuer's avatar
David Feuer committed
432 433
-- Caution: since this may be used for `fmap`, we can't use the obvious
-- definition of liftA = fmap.
434 435 436

-- | Lift a binary function to actions.
liftA2 :: Applicative f => (a -> b -> c) -> f a -> f b -> f c
David Feuer's avatar
David Feuer committed
437
liftA2 f a b = fmap f a <*> b
438 439 440

-- | Lift a ternary function to actions.
liftA3 :: Applicative f => (a -> b -> c -> d) -> f a -> f b -> f c -> f d
David Feuer's avatar
David Feuer committed
441 442 443
liftA3 f a b c = fmap f a <*> b <*> c


444
{-# INLINABLE liftA #-}
David Feuer's avatar
David Feuer committed
445 446
{-# SPECIALISE liftA :: (a1->r) -> IO a1 -> IO r #-}
{-# SPECIALISE liftA :: (a1->r) -> Maybe a1 -> Maybe r #-}
447
{-# INLINABLE liftA2 #-}
David Feuer's avatar
David Feuer committed
448 449
{-# SPECIALISE liftA2 :: (a1->a2->r) -> IO a1 -> IO a2 -> IO r #-}
{-# SPECIALISE liftA2 :: (a1->a2->r) -> Maybe a1 -> Maybe a2 -> Maybe r #-}
450
{-# INLINABLE liftA3 #-}
David Feuer's avatar
David Feuer committed
451 452 453
{-# 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 #-}
454

455 456 457 458 459 460
-- | 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

ross's avatar
ross committed
461 462 463 464 465 466 467
{- | 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.

ross's avatar
ross committed
468 469
Instances of 'Monad' should satisfy the following laws:

David Feuer's avatar
David Feuer committed
470 471 472 473 474 475 476 477 478
* @'return' a '>>=' k  =  k a@
* @m '>>=' 'return'  =  m@
* @m '>>=' (\x -> k x '>>=' h)  =  (m '>>=' k) '>>=' h@

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

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

479
The above laws imply:
ross's avatar
ross committed
480

481 482
* @'fmap' f xs  =  xs '>>=' 'return' . f@
* @('>>') = ('*>')@
ross's avatar
ross committed
483

David Feuer's avatar
David Feuer committed
484
and that 'pure' and ('<*>') satisfy the applicative functor laws.
ross's avatar
ross committed
485

ross's avatar
ross committed
486 487
The instances of 'Monad' for lists, 'Data.Maybe.Maybe' and 'System.IO.IO'
defined in the "Prelude" satisfy these laws.
ross's avatar
ross committed
488
-}
489
class Applicative m => Monad m where
ross's avatar
ross committed
490 491
    -- | Sequentially compose two actions, passing any value produced
    -- by the first as an argument to the second.
492
    (>>=)       :: forall a b. m a -> (a -> m b) -> m b
493

ross's avatar
ross committed
494 495 496
    -- | Sequentially compose two actions, discarding any value produced
    -- by the first, like sequencing operators (such as the semicolon)
    -- in imperative languages.
497
    (>>)        :: forall a b. m a -> m b -> m b
498
    m >> k = m >>= \_ -> k -- See Note [Recursive bindings for Applicative/Monad]
499
    {-# INLINE (>>) #-}
ross's avatar
ross committed
500 501

    -- | Inject a value into the monadic type.
502
    return      :: a -> m a
503
    return      = pure
504

ross's avatar
ross committed
505 506 507
    -- | 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.
508 509 510 511 512
    --
    -- 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
513
    fail        :: String -> m a
Eric Seidel's avatar
Eric Seidel committed
514
    fail s      = errorWithoutStackTrace s
515

516 517 518 519 520 521 522 523 524 525 526 527 528 529 530 531 532 533 534 535 536 537
{- 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.

-}

538 539 540 541 542
-- | 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

543
-- | Conditional execution of 'Applicative' expressions. For example,
544 545 546 547 548
--
-- > when debug (putStrLn "Debugging")
--
-- will output the string @Debugging@ if the Boolean value @debug@
-- is 'True', and otherwise do nothing.
549
when      :: (Applicative f) => Bool -> f () -> f ()
550
{-# INLINABLE when #-}
551 552
{-# SPECIALISE when :: Bool -> IO () -> IO () #-}
{-# SPECIALISE when :: Bool -> Maybe () -> Maybe () #-}
553
when p s  = if p then s else pure ()
554

555 556 557 558
-- | Evaluate each action in the sequence from left to right,
-- and collect the results.
sequence :: Monad m => [m a] -> m [a]
{-# INLINE sequence #-}
559 560
sequence = mapM id
-- Note: [sequence and mapM]
561 562 563 564

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

569 570 571 572 573 574 575 576 577 578 579 580 581 582 583 584 585
{-
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.
-}

586 587 588 589 590 591 592 593 594 595 596 597 598 599 600 601 602 603 604 605 606 607 608 609 610 611 612 613
-- | 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,
--
-- >    liftM2 (+) [0,1] [0,2] = [0,2,1,3]
-- >    liftM2 (+) (Just 1) Nothing = Nothing
--
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) }

-- | 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) }

614
{-# INLINABLE liftM #-}
615
{-# SPECIALISE liftM :: (a1->r) -> IO a1 -> IO r #-}
616
{-# SPECIALISE liftM :: (a1->r) -> Maybe a1 -> Maybe r #-}
617
{-# INLINABLE liftM2 #-}
618
{-# SPECIALISE liftM2 :: (a1->a2->r) -> IO a1 -> IO a2 -> IO r #-}
619
{-# SPECIALISE liftM2 :: (a1->a2->r) -> Maybe a1 -> Maybe a2 -> Maybe r #-}
620
{-# INLINABLE liftM3 #-}
621
{-# SPECIALISE liftM3 :: (a1->a2->a3->r) -> IO a1 -> IO a2 -> IO a3 -> IO r #-}
622
{-# SPECIALISE liftM3 :: (a1->a2->a3->r) -> Maybe a1 -> Maybe a2 -> Maybe a3 -> Maybe r #-}
623
{-# INLINABLE liftM4 #-}
624
{-# SPECIALISE liftM4 :: (a1->a2->a3->a4->r) -> IO a1 -> IO a2 -> IO a3 -> IO a4 -> IO r #-}
625
{-# SPECIALISE liftM4 :: (a1->a2->a3->a4->r) -> Maybe a1 -> Maybe a2 -> Maybe a3 -> Maybe a4 -> Maybe r #-}
626
{-# INLINABLE liftM5 #-}
627
{-# SPECIALISE liftM5 :: (a1->a2->a3->a4->a5->r) -> IO a1 -> IO a2 -> IO a3 -> IO a4 -> IO a5 -> IO r #-}
628
{-# SPECIALISE liftM5 :: (a1->a2->a3->a4->a5->r) -> Maybe a1 -> Maybe a2 -> Maybe a3 -> Maybe a4 -> Maybe a5 -> Maybe r #-}
629 630

{- | In many situations, the 'liftM' operations can be replaced by uses of
631
'ap', which promotes function application.
632 633 634

>       return f `ap` x1 `ap` ... `ap` xn

635
is equivalent to
636 637 638 639 640 641

>       liftMn f x1 x2 ... xn

-}

ap                :: (Monad m) => m (a -> b) -> m a -> m b
David Feuer's avatar
David Feuer committed
642 643 644
ap m1 m2          = do { x1 <- m1; x2 <- m2; return (x1 x2) }
-- Since many Applicative instances define (<*>) = ap, we
-- cannot define ap = (<*>)
645
{-# INLINABLE ap #-}
David Feuer's avatar
David Feuer committed
646 647
{-# SPECIALISE ap :: IO (a -> b) -> IO a -> IO b #-}
{-# SPECIALISE ap :: Maybe (a -> b) -> Maybe a -> Maybe b #-}
648 649 650

-- instances for Prelude types

651
-- | @since 2.01
652 653 654
instance Functor ((->) r) where
    fmap = (.)

655
-- | @since 2.01
656 657 658 659
instance Applicative ((->) a) where
    pure = const
    (<*>) f g x = f x (g x)

660
-- | @since 2.01
661 662 663
instance Monad ((->) r) where
    f >>= k = \ r -> k (f r) r

664
-- | @since 2.01
665 666
instance Functor ((,) a) where
    fmap f (x,y) = (x, f y)
667

668
-- | @since 2.01
669 670 671 672
instance  Functor Maybe  where
    fmap _ Nothing       = Nothing
    fmap f (Just a)      = Just (f a)

673
-- | @since 2.01
674
instance Applicative Maybe where
David Feuer's avatar
David Feuer committed
675 676 677 678 679 680 681
    pure = Just

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

    Just _m1 *> m2      = m2
    Nothing  *> _m2     = Nothing
682

683
-- | @since 2.01
684 685 686 687
instance  Monad Maybe  where
    (Just x) >>= k      = k x
    Nothing  >>= _      = Nothing

David Feuer's avatar
David Feuer committed
688
    (>>) = (*>)
689 690 691

    fail _              = Nothing

692 693 694 695 696 697 698 699 700 701 702 703 704 705 706 707 708 709 710 711 712 713 714 715 716 717 718 719 720 721 722 723 724 725
-- -----------------------------------------------------------------------------
-- The Alternative class definition

infixl 3 <|>

-- | A monoid on applicative functors.
--
-- If defined, 'some' and 'many' should be the least solutions
-- of the equations:
--
-- * @some v = (:) '<$>' v '<*>' many v@
--
-- * @many v = some v '<|>' 'pure' []@
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 []
        some_v = (fmap (:) v) <*> many_v

    -- | Zero or more.
    many :: f a -> f [a]
    many v = many_v
      where
        many_v = some_v <|> pure []
        some_v = (fmap (:) v) <*> many_v


726
-- | @since 2.01
727 728 729 730 731 732 733 734 735 736 737 738 739 740 741 742 743 744 745 746 747 748
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 = (<|>)

749
-- | @since 2.01
David Feuer's avatar
David Feuer committed
750
instance MonadPlus Maybe
751

752 753
----------------------------------------------
-- The list type
754

755
-- | @since 2.01
756
instance Functor [] where
757
    {-# INLINE fmap #-}
758 759
    fmap = map

760
-- See Note: [List comprehensions and inlining]
761
-- | @since 2.01
762
instance Applicative [] where
763 764 765 766 767 768 769 770
    {-# INLINE pure #-}
    pure x    = [x]
    {-# INLINE (<*>) #-}
    fs <*> xs = [f x | f <- fs, x <- xs]
    {-# INLINE (*>) #-}
    xs *> ys  = [y | _ <- xs, y <- ys]

-- See Note: [List comprehensions and inlining]
771
-- | @since 2.01
772 773 774 775 776 777
instance Monad []  where
    {-# INLINE (>>=) #-}
    xs >>= f             = [y | x <- xs, y <- f x]
    {-# INLINE (>>) #-}
    (>>) = (*>)
    {-# INLINE fail #-}
Don Stewart's avatar
Don Stewart committed
778
    fail _              = []
779

780
-- | @since 2.01
781 782 783 784
instance Alternative [] where
    empty = []
    (<|>) = (++)

785
-- | @since 2.01
David Feuer's avatar
David Feuer committed
786
instance MonadPlus []
787

788
{-
789 790
A few list functions that appear here because they are used here.
The rest of the prelude list functions are in GHC.List.
791
-}
792 793

----------------------------------------------
Don Stewart's avatar
Don Stewart committed
794
--      foldr/build/augment
795
----------------------------------------------
796

ross's avatar
ross committed
797 798 799 800 801 802
-- | '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)...)

803 804 805
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
806 807
{-# INLINE [0] foldr #-}
-- Inline only in the final stage, after the foldr/cons rule has had a chance
808
-- Also note that we inline it when it has *two* parameters, which are the
809 810 811 812 813
-- ones we are keen about specialising!
foldr k z = go
          where
            go []     = z
            go (y:ys) = y `k` go ys
814

ross's avatar
ross committed
815 816 817
-- | A list producer that can be fused with 'foldr'.
-- This function is merely
--
Don Stewart's avatar
Don Stewart committed
818
-- >    build g = g (:) []
ross's avatar
ross committed
819 820 821 822 823
--
-- 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
824
build   :: forall a. (forall b. (a -> b -> b) -> b -> b) -> [a]
825
{-# INLINE [1] build #-}
Don Stewart's avatar
Don Stewart committed
826 827 828 829 830 831
        -- 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
832 833 834

build g = g (:) []

ross's avatar
ross committed
835 836 837
-- | A list producer that can be fused with 'foldr'.
-- This function is merely
--
Don Stewart's avatar
Don Stewart committed
838
-- >    augment g xs = g (:) xs
ross's avatar
ross committed
839 840 841 842 843
--
-- 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.

844
augment :: forall a. (forall b. (a->b->b) -> b -> b) -> [a] -> [a]
845
{-# INLINE [1] augment #-}
846 847 848
augment g xs = g (:) xs

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

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

Don Stewart's avatar
Don Stewart committed
855 856 857 858
"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
859

860 861
-- The foldr/cons rule looks nice, but it can give disastrously
-- bloated code when commpiling
Don Stewart's avatar
Don Stewart committed
862
--      array (a,b) [(1,2), (2,2), (3,2), ...very long list... ]
863 864 865
-- 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
866
-- "foldr/cons" forall k z x xs. foldr k z (x:xs) = k x (foldr k z xs)
867

Don Stewart's avatar
Don Stewart committed
868
"foldr/single"  forall k z x. foldr k z [x] = k x z
869
"foldr/nil"     forall k z.   foldr k z []  = z
870

871 872 873
"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)

874
"augment/build" forall (g::forall b. (a->b->b) -> b -> b)
Don Stewart's avatar
Don Stewart committed
875 876
                       (h::forall b. (a->b->b) -> b -> b) .
                       augment g (build h) = build (\c n -> g c (h c n))
877
"augment/nil"   forall (g::forall b. (a->b->b) -> b -> b) .
Don Stewart's avatar
Don Stewart committed
878
                        augment g [] = build g
879 880 881
 #-}

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

----------------------------------------------
885
--              map
886 887
----------------------------------------------

ross's avatar
ross committed
888 889 890 891 892 893
-- | '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, ...]

894
map :: (a -> b) -> [a] -> [b]
895 896 897 898
{-# 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
899 900
map _ []     = []
map f (x:xs) = f x : map f xs
901 902 903

-- Note eta expanded
mapFB ::  (elt -> lst -> lst) -> (a -> elt) -> a -> lst -> lst
904
{-# INLINE [0] mapFB #-}
905
mapFB c f = \x ys -> c (f x) ys
906

907
-- The rules for map work like this.
908
--
909
-- Up to (but not including) phase 1, we use the "map" rule to
910
-- rewrite all saturated applications of map with its build/fold
911 912 913
-- 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
914
-- thing back into plain map.
915
--
916 917
-- 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
918 919 920 921
-- in the rules.  Hence the activation control below.
--
-- The "mapFB" rule optimises compositions of map.
--
922
-- This same pattern is followed by many other functions:
923
-- e.g. append, filter, iterate, repeat, etc.
924 925

{-# RULES
Don Stewart's avatar
Don Stewart committed
926 927
"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
928
"mapFB"     forall c f g.       mapFB (mapFB c f) g     = mapFB c (f.g)
929
  #-}
930

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

935
{-# RULES "map/coerce" [1] map coerce = coerce #-}
936

937 938

----------------------------------------------
939
--              append
940
----------------------------------------------
941

ross's avatar
ross committed
942 943 944 945 946 947 948
-- | 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.

949
(++) :: [a] -> [a] -> [a]
950 951
{-# 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
952
                             -- but saying so is more explicit
953 954
(++) []     ys = ys
(++) (x:xs) ys = x : xs ++ ys
955 956

{-# RULES
Don Stewart's avatar
Don Stewart committed
957
"++"    [~1] forall xs ys. xs ++ ys = augment (\c n -> foldr c n xs) ys
958 959 960
  #-}


961
-- |'otherwise' is defined as the value 'True'.  It helps to make
962 963
-- guards more readable.  eg.
--
964
-- >  f x | x < 0     = ...
965
-- >      | otherwise = ...
Don Stewart's avatar
Don Stewart committed
966 967
otherwise               :: Bool
otherwise               =  True
968

969 970 971
----------------------------------------------
-- Type Char and String
----------------------------------------------
972

973 974 975
-- | A 'String' is a list of characters.  String constants in Haskell are values
-- of type 'String'.
--
976 977 978 979 980
type String = [Char]

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

ross's avatar
ross committed
981
-- | The 'Prelude.fromEnum' method restricted to the type 'Data.Char.Char'.
982 983 984
ord :: Char -> Int
ord (C# c#) = I# (ord# c#)

985 986
-- | This 'String' equality predicate is used when desugaring
-- pattern-matches against strings.
987
eqString :: String -> String -> Bool
Don Stewart's avatar
Don Stewart committed
988
eqString []       []       = True
989
eqString (c1:cs1) (c2:cs2) = c1 == c2 && cs1 `eqString` cs2
Ian Lynagh's avatar
Ian Lynagh committed
990
eqString _        _        = False
991 992

{-# RULES "eqString" (==) = eqString #-}
993
-- eqString also has a BuiltInRule in PrelRules.lhs:
994
--      eqString (unpackCString# (Lit s1)) (unpackCString# (Lit s2)) = s1==s2
995

996

997 998 999
----------------------------------------------
-- 'Int' related definitions
----------------------------------------------
1000

1001
maxInt, minInt :: Int
1002 1003 1004 1005 1006 1007

{- 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
1008 1009
minInt  = I# (-0x80000000#)
maxInt  = I# 0x7FFFFFFF#