GHC/Base.lhs

   1 \section[GHC.Base]{Module @GHC.Base@}
   2
   3 The overall structure of the GHC Prelude is a bit tricky.
   4
   5   a) We want to avoid "orphan modules", i.e. ones with instance
   6         decls that don't belong either to a tycon or a class
   7         defined in the same module
   8
   9   b) We want to avoid giant modules
  10
  11 So the rough structure is as follows, in (linearised) dependency order
  12
  13
  14 GHC.Prim                Has no implementation.  It defines built-in things, and
  15                 by importing it you bring them into scope.
  16                 The source file is GHC.Prim.hi-boot, which is just
  17                 copied to make GHC.Prim.hi
  18
  19 GHC.Base        Classes: Eq, Ord, Functor, Monad
  20                 Types:   list, (), Int, Bool, Ordering, Char, String
  21
  22 Data.Tuple      Types: tuples, plus instances for GHC.Base classes
  23
  24 GHC.Show        Class: Show, plus instances for GHC.Base/GHC.Tup types
  25
  26 GHC.Enum        Class: Enum,  plus instances for GHC.Base/GHC.Tup types
  27
  28 Data.Maybe      Type: Maybe, plus instances for GHC.Base classes
  29
  30 GHC.List        List functions
  31
  32 GHC.Num         Class: Num, plus instances for Int
  33                 Type:  Integer, plus instances for all classes so far (Eq, Ord, Num, Show)
  34
  35                 Integer is needed here because it is mentioned in the signature
  36                 of 'fromInteger' in class Num
  37
  38 GHC.Real        Classes: Real, Integral, Fractional, RealFrac
  39                          plus instances for Int, Integer
  40                 Types:  Ratio, Rational
  41                         plus intances for classes so far
  42
  43                 Rational is needed here because it is mentioned in the signature
  44                 of 'toRational' in class Real
  45
  46 GHC.ST  The ST monad, instances and a few helper functions
  47
  48 Ix              Classes: Ix, plus instances for Int, Bool, Char, Integer, Ordering, tuples
  49
  50 GHC.Arr         Types: Array, MutableArray, MutableVar
  51
  52                 Arrays are used by a function in GHC.Float
  53
  54 GHC.Float       Classes: Floating, RealFloat
  55                 Types:   Float, Double, plus instances of all classes so far
  56
  57                 This module contains everything to do with floating point.
  58                 It is a big module (900 lines)
  59                 With a bit of luck, many modules can be compiled without ever reading GHC.Float.hi
  60
  61
  62 Other Prelude modules are much easier with fewer complex dependencies.
  63
  64 \begin{code}
  65 {-# OPTIONS_GHC -fno-implicit-prelude #-}
  66 {-# OPTIONS_HADDOCK hide #-}
  67 -----------------------------------------------------------------------------
  68 -- |
  69 -- Module      :  GHC.Base
  70 -- Copyright   :  (c) The University of Glasgow, 1992-2002
  71 -- License     :  see libraries/base/LICENSE
  72 --
  73 -- Maintainer  :  cvs-ghc@haskell.org
  74 -- Stability   :  internal
  75 -- Portability :  non-portable (GHC extensions)
  76 --
  77 -- Basic data types and classes.
  78 --
  79 -----------------------------------------------------------------------------
  80
  81 #include "MachDeps.h"
  82
  83 -- #hide
  84 module GHC.Base
  85         (
  86         module GHC.Base,
  87         module GHC.Bool,
  88         module GHC.Generics,
  89         module GHC.Prim,        -- Re-export GHC.Prim and GHC.Err, to avoid lots
  90         module GHC.Err          -- of people having to import it explicitly
  91   )
  92         where
  93
  94 import GHC.Bool
  95 import GHC.Generics
  96 import GHC.Prim
  97 import {-# SOURCE #-} GHC.Err
  98
  99 infixr 9  .
 100 infixr 5  ++, :
 101 infix  4  ==, /=, <, <=, >=, >
 102 infixr 3  &&
 103 infixr 2  ||
 104 infixl 1  >>, >>=
 105 infixr 0  $
 106
 107 default ()              -- Double isn't available yet
 108 \end{code}
 109
 110
 111 %*********************************************************
 112 %*                                                      *
 113 \subsection{DEBUGGING STUFF}
 114 %*  (for use when compiling GHC.Base itself doesn't work)
 115 %*                                                      *
 116 %*********************************************************
 117
 118 \begin{code}
 119 {-
 120 data  Bool  =  False | True
 121 data Ordering = LT | EQ | GT
 122 data Char = C# Char#
 123 type  String = [Char]
 124 data Int = I# Int#
 125 data  ()  =  ()
 126 data [] a = MkNil
 127
 128 not True = False
 129 (&&) True True = True
 130 otherwise = True
 131
 132 build = error "urk"
 133 foldr = error "urk"
 134
 135 unpackCString# :: Addr# -> [Char]
 136 unpackFoldrCString# :: Addr# -> (Char  -> a -> a) -> a -> a
 137 unpackAppendCString# :: Addr# -> [Char] -> [Char]
 138 unpackCStringUtf8# :: Addr# -> [Char]
 139 unpackCString# a = error "urk"
 140 unpackFoldrCString# a = error "urk"
 141 unpackAppendCString# a = error "urk"
 142 unpackCStringUtf8# a = error "urk"
 143 -}
 144 \end{code}
 145
 146
 147 %*********************************************************
 148 %*                                                      *
 149 \subsection{Standard classes @Eq@, @Ord@}
 150 %*                                                      *
 151 %*********************************************************
 152
 153 \begin{code}
 154
 155 -- | The 'Eq' class defines equality ('==') and inequality ('/=').
 156 -- All the basic datatypes exported by the "Prelude" are instances of 'Eq',
 157 -- and 'Eq' may be derived for any datatype whose constituents are also
 158 -- instances of 'Eq'.
 159 --
 160 -- Minimal complete definition: either '==' or '/='.
 161 --
 162 class  Eq a  where
 163     (==), (/=)           :: a -> a -> Bool
 164
 165     x /= y               = not (x == y)
 166     x == y               = not (x /= y)
 167
 168 -- | The 'Ord' class is used for totally ordered datatypes.
 169 --
 170 -- Instances of 'Ord' can be derived for any user-defined
 171 -- datatype whose constituent types are in 'Ord'.  The declared order
 172 -- of the constructors in the data declaration determines the ordering
 173 -- in derived 'Ord' instances.  The 'Ordering' datatype allows a single
 174 -- comparison to determine the precise ordering of two objects.
 175 --
 176 -- Minimal complete definition: either 'compare' or '<='.
 177 -- Using 'compare' can be more efficient for complex types.
 178 --
 179 class  (Eq a) => Ord a  where
 180     compare              :: a -> a -> Ordering
 181     (<), (<=), (>), (>=) :: a -> a -> Bool
 182     max, min             :: a -> a -> a
 183
 184     compare x y
 185         | x == y    = EQ
 186         | x <= y    = LT        -- NB: must be '<=' not '<' to validate the
 187                                 -- above claim about the minimal things that
 188                                 -- can be defined for an instance of Ord
 189         | otherwise = GT
 190
 191     x <  y = case compare x y of { LT -> True;  _other -> False }
 192     x <= y = case compare x y of { GT -> False; _other -> True }
 193     x >  y = case compare x y of { GT -> True;  _other -> False }
 194     x >= y = case compare x y of { LT -> False; _other -> True }
 195
 196         -- These two default methods use '<=' rather than 'compare'
 197         -- because the latter is often more expensive
 198     max x y = if x <= y then y else x
 199     min x y = if x <= y then x else y
 200 \end{code}
 201
 202 %*********************************************************
 203 %*                                                      *
 204 \subsection{Monadic classes @Functor@, @Monad@ }
 205 %*                                                      *
 206 %*********************************************************
 207
 208 \begin{code}
 209 {- | The 'Functor' class is used for types that can be mapped over.
 210 Instances of 'Functor' should satisfy the following laws:
 211
 212 > fmap id  ==  id
 213 > fmap (f . g)  ==  fmap f . fmap g
 214
 215 The instances of 'Functor' for lists, 'Data.Maybe.Maybe' and 'System.IO.IO'
 216 defined in the "Prelude" satisfy these laws.
 217 -}
 218
 219 class  Functor f  where
 220     fmap        :: (a -> b) -> f a -> f b
 221
 222 {- | The 'Monad' class defines the basic operations over a /monad/,
 223 a concept from a branch of mathematics known as /category theory/.
 224 From the perspective of a Haskell programmer, however, it is best to
 225 think of a monad as an /abstract datatype/ of actions.
 226 Haskell's @do@ expressions provide a convenient syntax for writing
 227 monadic expressions.
 228
 229 Minimal complete definition: '>>=' and 'return'.
 230
 231 Instances of 'Monad' should satisfy the following laws:
 232
 233 > return a >>= k  ==  k a
 234 > m >>= return  ==  m
 235 > m >>= (\x -> k x >>= h)  ==  (m >>= k) >>= h
 236
 237 Instances of both 'Monad' and 'Functor' should additionally satisfy the law:
 238
 239 > fmap f xs  ==  xs >>= return . f
 240
 241 The instances of 'Monad' for lists, 'Data.Maybe.Maybe' and 'System.IO.IO'
 242 defined in the "Prelude" satisfy these laws.
 243 -}
 244
 245 class  Monad m  where
 246     -- | Sequentially compose two actions, passing any value produced
 247     -- by the first as an argument to the second.
 248     (>>=)       :: forall a b. m a -> (a -> m b) -> m b
 249     -- | Sequentially compose two actions, discarding any value produced
 250     -- by the first, like sequencing operators (such as the semicolon)
 251     -- in imperative languages.
 252     (>>)        :: forall a b. m a -> m b -> m b
 253         -- Explicit for-alls so that we know what order to
 254         -- give type arguments when desugaring
 255
 256     -- | Inject a value into the monadic type.
 257     return      :: a -> m a
 258     -- | Fail with a message.  This operation is not part of the
 259     -- mathematical definition of a monad, but is invoked on pattern-match
 260     -- failure in a @do@ expression.
 261     fail        :: String -> m a
 262
 263     m >> k      = m >>= \_ -> k
 264     fail s      = error s
 265 \end{code}
 266
 267
 268 %*********************************************************
 269 %*                                                      *
 270 \subsection{The list type}
 271 %*                                                      *
 272 %*********************************************************
 273
 274 \begin{code}
 275 data [] a = [] | a : [a]  -- do explicitly: deriving (Eq, Ord)
 276                           -- to avoid weird names like con2tag_[]#
 277
 278
 279 instance (Eq a) => Eq [a] where
 280     {-# SPECIALISE instance Eq [Char] #-}
 281     []     == []     = True
 282     (x:xs) == (y:ys) = x == y && xs == ys
 283     _xs    == _ys    = False
 284
 285 instance (Ord a) => Ord [a] where
 286     {-# SPECIALISE instance Ord [Char] #-}
 287     compare []     []     = EQ
 288     compare []     (_:_)  = LT
 289     compare (_:_)  []     = GT
 290     compare (x:xs) (y:ys) = case compare x y of
 291                                 EQ    -> compare xs ys
 292                                 other -> other
 293
 294 instance Functor [] where
 295     fmap = map
 296
 297 instance  Monad []  where
 298     m >>= k             = foldr ((++) . k) [] m
 299     m >> k              = foldr ((++) . (\ _ -> k)) [] m
 300     return x            = [x]
 301     fail _              = []
 302 \end{code}
 303
 304 A few list functions that appear here because they are used here.
 305 The rest of the prelude list functions are in GHC.List.
 306
 307 ----------------------------------------------
 308 --      foldr/build/augment
 309 ----------------------------------------------
 310
 311 \begin{code}
 312 -- | 'foldr', applied to a binary operator, a starting value (typically
 313 -- the right-identity of the operator), and a list, reduces the list
 314 -- using the binary operator, from right to left:
 315 --
 316 -- > foldr f z [x1, x2, ..., xn] == x1 `f` (x2 `f` ... (xn `f` z)...)
 317
 318 foldr            :: (a -> b -> b) -> b -> [a] -> b
 319 -- foldr _ z []     =  z
 320 -- foldr f z (x:xs) =  f x (foldr f z xs)
 321 {-# INLINE [0] foldr #-}
 322 -- Inline only in the final stage, after the foldr/cons rule has had a chance
 323 foldr k z xs = go xs
 324              where
 325                go []     = z
 326                go (y:ys) = y `k` go ys
 327
 328 -- | A list producer that can be fused with 'foldr'.
 329 -- This function is merely
 330 --
 331 -- >    build g = g (:) []
 332 --
 333 -- but GHC's simplifier will transform an expression of the form
 334 -- @'foldr' k z ('build' g)@, which may arise after inlining, to @g k z@,
 335 -- which avoids producing an intermediate list.
 336
 337 build   :: forall a. (forall b. (a -> b -> b) -> b -> b) -> [a]
 338 {-# INLINE [1] build #-}
 339         -- The INLINE is important, even though build is tiny,
 340         -- because it prevents [] getting inlined in the version that
 341         -- appears in the interface file.  If [] *is* inlined, it
 342         -- won't match with [] appearing in rules in an importing module.
 343         --
 344         -- The "1" says to inline in phase 1
 345
 346 build g = g (:) []
 347
 348 -- | A list producer that can be fused with 'foldr'.
 349 -- This function is merely
 350 --
 351 -- >    augment g xs = g (:) xs
 352 --
 353 -- but GHC's simplifier will transform an expression of the form
 354 -- @'foldr' k z ('augment' g xs)@, which may arise after inlining, to
 355 -- @g k ('foldr' k z xs)@, which avoids producing an intermediate list.
 356
 357 augment :: forall a. (forall b. (a->b->b) -> b -> b) -> [a] -> [a]
 358 {-# INLINE [1] augment #-}
 359 augment g xs = g (:) xs
 360
 361 {-# RULES
 362 "fold/build"    forall k z (g::forall b. (a->b->b) -> b -> b) .
 363                 foldr k z (build g) = g k z
 364
 365 "foldr/augment" forall k z xs (g::forall b. (a->b->b) -> b -> b) .
 366                 foldr k z (augment g xs) = g k (foldr k z xs)
 367
 368 "foldr/id"                        foldr (:) [] = \x  -> x
 369 "foldr/app"     [1] forall ys. foldr (:) ys = \xs -> xs ++ ys
 370         -- Only activate this from phase 1, because that's
 371         -- when we disable the rule that expands (++) into foldr
 372
 373 -- The foldr/cons rule looks nice, but it can give disastrously
 374 -- bloated code when commpiling
 375 --      array (a,b) [(1,2), (2,2), (3,2), ...very long list... ]
 376 -- i.e. when there are very very long literal lists
 377 -- So I've disabled it for now. We could have special cases
 378 -- for short lists, I suppose.
 379 -- "foldr/cons" forall k z x xs. foldr k z (x:xs) = k x (foldr k z xs)
 380
 381 "foldr/single"  forall k z x. foldr k z [x] = k x z
 382 "foldr/nil"     forall k z.   foldr k z []  = z
 383
 384 "augment/build" forall (g::forall b. (a->b->b) -> b -> b)
 385                        (h::forall b. (a->b->b) -> b -> b) .
 386                        augment g (build h) = build (\c n -> g c (h c n))
 387 "augment/nil"   forall (g::forall b. (a->b->b) -> b -> b) .
 388                         augment g [] = build g
 389  #-}
 390
 391 -- This rule is true, but not (I think) useful:
 392 --      augment g (augment h t) = augment (\cn -> g c (h c n)) t
 393 \end{code}
 394
 395
 396 ----------------------------------------------
 397 --              map
 398 ----------------------------------------------
 399
 400 \begin{code}
 401 -- | 'map' @f xs@ is the list obtained by applying @f@ to each element
 402 -- of @xs@, i.e.,
 403 --
 404 -- > map f [x1, x2, ..., xn] == [f x1, f x2, ..., f xn]
 405 -- > map f [x1, x2, ...] == [f x1, f x2, ...]
 406
 407 map :: (a -> b) -> [a] -> [b]
 408 map _ []     = []
 409 map f (x:xs) = f x : map f xs
 410
 411 -- Note eta expanded
 412 mapFB ::  (elt -> lst -> lst) -> (a -> elt) -> a -> lst -> lst
 413 {-# INLINE [0] mapFB #-}
 414 mapFB c f x ys = c (f x) ys
 415
 416 -- The rules for map work like this.
 417 --
 418 -- Up to (but not including) phase 1, we use the "map" rule to
 419 -- rewrite all saturated applications of map with its build/fold
 420 -- form, hoping for fusion to happen.
 421 -- In phase 1 and 0, we switch off that rule, inline build, and
 422 -- switch on the "mapList" rule, which rewrites the foldr/mapFB
 423 -- thing back into plain map.
 424 --
 425 -- It's important that these two rules aren't both active at once
 426 -- (along with build's unfolding) else we'd get an infinite loop
 427 -- in the rules.  Hence the activation control below.
 428 --
 429 -- The "mapFB" rule optimises compositions of map.
 430 --
 431 -- This same pattern is followed by many other functions:
 432 -- e.g. append, filter, iterate, repeat, etc.
 433
 434 {-# RULES
 435 "map"       [~1] forall f xs.   map f xs                = build (\c n -> foldr (mapFB c f) n xs)
 436 "mapList"   [1]  forall f.      foldr (mapFB (:) f) []  = map f
 437 "mapFB"     forall c f g.       mapFB (mapFB c f) g     = mapFB c (f.g)
 438   #-}
 439 \end{code}
 440
 441
 442 ----------------------------------------------
 443 --              append
 444 ----------------------------------------------
 445 \begin{code}
 446 -- | Append two lists, i.e.,
 447 --
 448 -- > [x1, ..., xm] ++ [y1, ..., yn] == [x1, ..., xm, y1, ..., yn]
 449 -- > [x1, ..., xm] ++ [y1, ...] == [x1, ..., xm, y1, ...]
 450 --
 451 -- If the first list is not finite, the result is the first list.
 452
 453 (++) :: [a] -> [a] -> [a]
 454 (++) []     ys = ys
 455 (++) (x:xs) ys = x : xs ++ ys
 456
 457 {-# RULES
 458 "++"    [~1] forall xs ys. xs ++ ys = augment (\c n -> foldr c n xs) ys
 459   #-}
 460
 461 \end{code}
 462
 463
 464 %*********************************************************
 465 %*                                                      *
 466 \subsection{Type @Bool@}
 467 %*                                                      *
 468 %*********************************************************
 469
 470 \begin{code}
 471 -- |The 'Bool' type is an enumeration.  It is defined with 'False'
 472 -- first so that the corresponding 'Prelude.Enum' instance will give
 473 -- 'Prelude.fromEnum' 'False' the value zero, and
 474 -- 'Prelude.fromEnum' 'True' the value 1.
 475 -- The actual definition is in the ghc-prim package.
 476
 477 -- XXX These don't work:
 478 -- deriving instance Eq Bool
 479 -- deriving instance Ord Bool
 480 -- <wired into compiler>:
 481 --     Illegal binding of built-in syntax: con2tag_Bool#
 482
 483 instance Eq Bool where
 484     True  == True  = True
 485     False == False = True
 486     _     == _     = False
 487
 488 instance Ord Bool where
 489     compare False True  = LT
 490     compare True  False = GT
 491     compare _     _     = EQ
 492
 493 -- Read is in GHC.Read, Show in GHC.Show
 494
 495 -- Boolean functions
 496
 497 -- | Boolean \"and\"
 498 (&&)                    :: Bool -> Bool -> Bool
 499 True  && x              =  x
 500 False && _              =  False
 501
 502 -- | Boolean \"or\"
 503 (||)                    :: Bool -> Bool -> Bool
 504 True  || _              =  True
 505 False || x              =  x
 506
 507 -- | Boolean \"not\"
 508 not                     :: Bool -> Bool
 509 not True                =  False
 510 not False               =  True
 511
 512 -- |'otherwise' is defined as the value 'True'.  It helps to make
 513 -- guards more readable.  eg.
 514 --
 515 -- >  f x | x < 0     = ...
 516 -- >      | otherwise = ...
 517 otherwise               :: Bool
 518 otherwise               =  True
 519 \end{code}
 520
 521 %*********************************************************
 522 %*                                                      *
 523 \subsection{The @()@ type}
 524 %*                                                      *
 525 %*********************************************************
 526
 527 The Unit type is here because virtually any program needs it (whereas
 528 some programs may get away without consulting GHC.Tup).  Furthermore,
 529 the renamer currently *always* asks for () to be in scope, so that
 530 ccalls can use () as their default type; so when compiling GHC.Base we
 531 need ().  (We could arrange suck in () only if -fglasgow-exts, but putting
 532 it here seems more direct.)
 533
 534 \begin{code}
 535 -- | The unit datatype @()@ has one non-undefined member, the nullary
 536 -- constructor @()@.
 537 data () = ()
 538
 539 instance Eq () where
 540     () == () = True
 541     () /= () = False
 542
 543 instance Ord () where
 544     () <= () = True
 545     () <  () = False
 546     () >= () = True
 547     () >  () = False
 548     max () () = ()
 549     min () () = ()
 550     compare () () = EQ
 551 \end{code}
 552
 553
 554 %*********************************************************
 555 %*                                                      *
 556 \subsection{Type @Ordering@}
 557 %*                                                      *
 558 %*********************************************************
 559
 560 \begin{code}
 561 -- | Represents an ordering relationship between two values: less
 562 -- than, equal to, or greater than.  An 'Ordering' is returned by
 563 -- 'compare'.
 564 data Ordering = LT | EQ | GT deriving (Eq, Ord)
 565         -- Read in GHC.Read, Show in GHC.Show
 566 \end{code}
 567
 568
 569 %*********************************************************
 570 %*                                                      *
 571 \subsection{Type @Char@ and @String@}
 572 %*                                                      *
 573 %*********************************************************
 574
 575 \begin{code}
 576 -- | A 'String' is a list of characters.  String constants in Haskell are values
 577 -- of type 'String'.
 578 --
 579 type String = [Char]
 580
 581 {-| The character type 'Char' is an enumeration whose values represent
 582 Unicode (or equivalently ISO\/IEC 10646) characters
 583 (see <http://www.unicode.org/> for details).
 584 This set extends the ISO 8859-1 (Latin-1) character set
 585 (the first 256 charachers), which is itself an extension of the ASCII
 586 character set (the first 128 characters).
 587 A character literal in Haskell has type 'Char'.
 588
 589 To convert a 'Char' to or from the corresponding 'Int' value defined
 590 by Unicode, use 'Prelude.toEnum' and 'Prelude.fromEnum' from the
 591 'Prelude.Enum' class respectively (or equivalently 'ord' and 'chr').
 592 -}
 593 data Char = C# Char#
 594
 595 -- We don't use deriving for Eq and Ord, because for Ord the derived
 596 -- instance defines only compare, which takes two primops.  Then
 597 -- '>' uses compare, and therefore takes two primops instead of one.
 598
 599 instance Eq Char where
 600     (C# c1) == (C# c2) = c1 `eqChar#` c2
 601     (C# c1) /= (C# c2) = c1 `neChar#` c2
 602
 603 instance Ord Char where
 604     (C# c1) >  (C# c2) = c1 `gtChar#` c2
 605     (C# c1) >= (C# c2) = c1 `geChar#` c2
 606     (C# c1) <= (C# c2) = c1 `leChar#` c2
 607     (C# c1) <  (C# c2) = c1 `ltChar#` c2
 608
 609 {-# RULES
 610 "x# `eqChar#` x#" forall x#. x# `eqChar#` x# = True
 611 "x# `neChar#` x#" forall x#. x# `neChar#` x# = False
 612 "x# `gtChar#` x#" forall x#. x# `gtChar#` x# = False
 613 "x# `geChar#` x#" forall x#. x# `geChar#` x# = True
 614 "x# `leChar#` x#" forall x#. x# `leChar#` x# = True
 615 "x# `ltChar#` x#" forall x#. x# `ltChar#` x# = False
 616   #-}
 617
 618 -- | The 'Prelude.toEnum' method restricted to the type 'Data.Char.Char'.
 619 chr :: Int -> Char
 620 chr (I# i#) | int2Word# i# `leWord#` int2Word# 0x10FFFF# = C# (chr# i#)
 621             | otherwise                                  = error "Prelude.chr: bad argument"
 622
 623 unsafeChr :: Int -> Char
 624 unsafeChr (I# i#) = C# (chr# i#)
 625
 626 -- | The 'Prelude.fromEnum' method restricted to the type 'Data.Char.Char'.
 627 ord :: Char -> Int
 628 ord (C# c#) = I# (ord# c#)
 629 \end{code}
 630
 631 String equality is used when desugaring pattern-matches against strings.
 632
 633 \begin{code}
 634 eqString :: String -> String -> Bool
 635 eqString []       []       = True
 636 eqString (c1:cs1) (c2:cs2) = c1 == c2 && cs1 `eqString` cs2
 637 eqString cs1      cs2      = False
 638
 639 {-# RULES "eqString" (==) = eqString #-}
 640 -- eqString also has a BuiltInRule in PrelRules.lhs:
 641 --      eqString (unpackCString# (Lit s1)) (unpackCString# (Lit s2) = s1==s2
 642 \end{code}
 643
 644
 645 %*********************************************************
 646 %*                                                      *
 647 \subsection{Type @Int@}
 648 %*                                                      *
 649 %*********************************************************
 650
 651 \begin{code}
 652 data Int = I# Int#
 653 -- ^A fixed-precision integer type with at least the range @[-2^29 .. 2^29-1]@.
 654 -- The exact range for a given implementation can be determined by using
 655 -- 'Prelude.minBound' and 'Prelude.maxBound' from the 'Prelude.Bounded' class.
 656
 657 zeroInt, oneInt, twoInt, maxInt, minInt :: Int
 658 zeroInt = I# 0#
 659 oneInt  = I# 1#
 660 twoInt  = I# 2#
 661
 662 {- Seems clumsy. Should perhaps put minInt and MaxInt directly into MachDeps.h -}
 663 #if WORD_SIZE_IN_BITS == 31
 664 minInt  = I# (-0x40000000#)
 665 maxInt  = I# 0x3FFFFFFF#
 666 #elif WORD_SIZE_IN_BITS == 32
 667 minInt  = I# (-0x80000000#)
 668 maxInt  = I# 0x7FFFFFFF#
 669 #else
 670 minInt  = I# (-0x8000000000000000#)
 671 maxInt  = I# 0x7FFFFFFFFFFFFFFF#
 672 #endif
 673
 674 instance Eq Int where
 675     (==) = eqInt
 676     (/=) = neInt
 677
 678 instance Ord Int where
 679     compare = compareInt
 680     (<)     = ltInt
 681     (<=)    = leInt
 682     (>=)    = geInt
 683     (>)     = gtInt
 684
 685 compareInt :: Int -> Int -> Ordering
 686 (I# x#) `compareInt` (I# y#) = compareInt# x# y#
 687
 688 compareInt# :: Int# -> Int# -> Ordering
 689 compareInt# x# y#
 690     | x# <#  y# = LT
 691     | x# ==# y# = EQ
 692     | otherwise = GT
 693 \end{code}
 694
 695
 696 %*********************************************************
 697 %*                                                      *
 698 \subsection{The function type}
 699 %*                                                      *
 700 %*********************************************************
 701
 702 \begin{code}
 703 -- | Identity function.
 704 id                      :: a -> a
 705 id x                    =  x
 706
 707 -- | The call '(lazy e)' means the same as 'e', but 'lazy' has a
 708 -- magical strictness property: it is lazy in its first argument,
 709 -- even though its semantics is strict.
 710 lazy :: a -> a
 711 lazy x = x
 712 -- Implementation note: its strictness and unfolding are over-ridden
 713 -- by the definition in MkId.lhs; in both cases to nothing at all.
 714 -- That way, 'lazy' does not get inlined, and the strictness analyser
 715 -- sees it as lazy.  Then the worker/wrapper phase inlines it.
 716 -- Result: happiness
 717
 718
 719 -- | The call '(inline f)' reduces to 'f', but 'inline' has a BuiltInRule
 720 -- that tries to inline 'f' (if it has an unfolding) unconditionally
 721 -- The 'NOINLINE' pragma arranges that inline only gets inlined (and
 722 -- hence eliminated) late in compilation, after the rule has had
 723 -- a god chance to fire.
 724 inline :: a -> a
 725 {-# NOINLINE[0] inline #-}
 726 inline x = x
 727
 728 -- Assertion function.  This simply ignores its boolean argument.
 729 -- The compiler may rewrite it to @('assertError' line)@.
 730
 731 -- | If the first argument evaluates to 'True', then the result is the
 732 -- second argument.  Otherwise an 'AssertionFailed' exception is raised,
 733 -- containing a 'String' with the source file and line number of the
 734 -- call to 'assert'.
 735 --
 736 -- Assertions can normally be turned on or off with a compiler flag
 737 -- (for GHC, assertions are normally on unless optimisation is turned on
 738 -- with @-O@ or the @-fignore-asserts@
 739 -- option is given).  When assertions are turned off, the first
 740 -- argument to 'assert' is ignored, and the second argument is
 741 -- returned as the result.
 742
 743 --      SLPJ: in 5.04 etc 'assert' is in GHC.Prim,
 744 --      but from Template Haskell onwards it's simply
 745 --      defined here in Base.lhs
 746 assert :: Bool -> a -> a
 747 assert pred r = r
 748
 749 breakpoint :: a -> a
 750 breakpoint r = r
 751
 752 breakpointCond :: Bool -> a -> a
 753 breakpointCond _ r = r
 754
 755 data Opaque = forall a. O a
 756
 757 -- | Constant function.
 758 const                   :: a -> b -> a
 759 const x _               =  x
 760
 761 -- | Function composition.
 762 {-# INLINE (.) #-}
 763 (.)       :: (b -> c) -> (a -> b) -> a -> c
 764 (.) f g x = f (g x)
 765
 766 -- | @'flip' f@ takes its (first) two arguments in the reverse order of @f@.
 767 flip                    :: (a -> b -> c) -> b -> a -> c
 768 flip f x y              =  f y x
 769
 770 -- | Application operator.  This operator is redundant, since ordinary
 771 -- application @(f x)@ means the same as @(f '$' x)@. However, '$' has
 772 -- low, right-associative binding precedence, so it sometimes allows
 773 -- parentheses to be omitted; for example:
 774 --
 775 -- >     f $ g $ h x  =  f (g (h x))
 776 --
 777 -- It is also useful in higher-order situations, such as @'map' ('$' 0) xs@,
 778 -- or @'Data.List.zipWith' ('$') fs xs@.
 779 {-# INLINE ($) #-}
 780 ($)                     :: (a -> b) -> a -> b
 781 f $ x                   =  f x
 782
 783 -- | @'until' p f@ yields the result of applying @f@ until @p@ holds.
 784 until                   :: (a -> Bool) -> (a -> a) -> a -> a
 785 until p f x | p x       =  x
 786             | otherwise =  until p f (f x)
 787
 788 -- | 'asTypeOf' is a type-restricted version of 'const'.  It is usually
 789 -- used as an infix operator, and its typing forces its first argument
 790 -- (which is usually overloaded) to have the same type as the second.
 791 asTypeOf                :: a -> a -> a
 792 asTypeOf                =  const
 793 \end{code}
 794
 795 %*********************************************************
 796 %*                                                      *
 797 \subsection{@getTag@}
 798 %*                                                      *
 799 %*********************************************************
 800
 801 Returns the 'tag' of a constructor application; this function is used
 802 by the deriving code for Eq, Ord and Enum.
 803
 804 The primitive dataToTag# requires an evaluated constructor application
 805 as its argument, so we provide getTag as a wrapper that performs the
 806 evaluation before calling dataToTag#.  We could have dataToTag#
 807 evaluate its argument, but we prefer to do it this way because (a)
 808 dataToTag# can be an inline primop if it doesn't need to do any
 809 evaluation, and (b) we want to expose the evaluation to the
 810 simplifier, because it might be possible to eliminate the evaluation
 811 in the case when the argument is already known to be evaluated.
 812
 813 \begin{code}
 814 {-# INLINE getTag #-}
 815 getTag :: a -> Int#
 816 getTag x = x `seq` dataToTag# x
 817 \end{code}
 818
 819 %*********************************************************
 820 %*                                                      *
 821 \subsection{Numeric primops}
 822 %*                                                      *
 823 %*********************************************************
 824
 825 \begin{code}
 826 divInt# :: Int# -> Int# -> Int#
 827 x# `divInt#` y#
 828         -- Be careful NOT to overflow if we do any additional arithmetic
 829         -- on the arguments...  the following  previous version of this
 830         -- code has problems with overflow:
 831 --    | (x# ># 0#) && (y# <# 0#) = ((x# -# y#) -# 1#) `quotInt#` y#
 832 --    | (x# <# 0#) && (y# ># 0#) = ((x# -# y#) +# 1#) `quotInt#` y#
 833     | (x# ># 0#) && (y# <# 0#) = ((x# -# 1#) `quotInt#` y#) -# 1#
 834     | (x# <# 0#) && (y# ># 0#) = ((x# +# 1#) `quotInt#` y#) -# 1#
 835     | otherwise                = x# `quotInt#` y#
 836
 837 modInt# :: Int# -> Int# -> Int#
 838 x# `modInt#` y#
 839     | (x# ># 0#) && (y# <# 0#) ||
 840       (x# <# 0#) && (y# ># 0#)    = if r# /=# 0# then r# +# y# else 0#
 841     | otherwise                   = r#
 842     where
 843     r# = x# `remInt#` y#
 844 \end{code}
 845
 846 Definitions of the boxed PrimOps; these will be
 847 used in the case of partial applications, etc.
 848
 849 \begin{code}
 850 {-# INLINE eqInt #-}
 851 {-# INLINE neInt #-}
 852 {-# INLINE gtInt #-}
 853 {-# INLINE geInt #-}
 854 {-# INLINE ltInt #-}
 855 {-# INLINE leInt #-}
 856 {-# INLINE plusInt #-}
 857 {-# INLINE minusInt #-}
 858 {-# INLINE timesInt #-}
 859 {-# INLINE quotInt #-}
 860 {-# INLINE remInt #-}
 861 {-# INLINE negateInt #-}
 862
 863 plusInt, minusInt, timesInt, quotInt, remInt, divInt, modInt, gcdInt :: Int -> Int -> Int
 864 (I# x) `plusInt`  (I# y) = I# (x +# y)
 865 (I# x) `minusInt` (I# y) = I# (x -# y)
 866 (I# x) `timesInt` (I# y) = I# (x *# y)
 867 (I# x) `quotInt`  (I# y) = I# (x `quotInt#` y)
 868 (I# x) `remInt`   (I# y) = I# (x `remInt#`  y)
 869 (I# x) `divInt`   (I# y) = I# (x `divInt#`  y)
 870 (I# x) `modInt`   (I# y) = I# (x `modInt#`  y)
 871
 872 {-# RULES
 873 "x# +# 0#" forall x#. x# +# 0# = x#
 874 "0# +# x#" forall x#. 0# +# x# = x#
 875 "x# -# 0#" forall x#. x# -# 0# = x#
 876 "x# -# x#" forall x#. x# -# x# = 0#
 877 "x# *# 0#" forall x#. x# *# 0# = 0#
 878 "0# *# x#" forall x#. 0# *# x# = 0#
 879 "x# *# 1#" forall x#. x# *# 1# = x#
 880 "1# *# x#" forall x#. 1# *# x# = x#
 881   #-}
 882
 883 gcdInt (I# a) (I# b) = g a b
 884    where g 0# 0# = error "GHC.Base.gcdInt: gcd 0 0 is undefined"
 885          g 0# _  = I# absB
 886          g _  0# = I# absA
 887          g _  _  = I# (gcdInt# absA absB)
 888
 889          absInt x = if x <# 0# then negateInt# x else x
 890
 891          absA     = absInt a
 892          absB     = absInt b
 893
 894 negateInt :: Int -> Int
 895 negateInt (I# x) = I# (negateInt# x)
 896
 897 gtInt, geInt, eqInt, neInt, ltInt, leInt :: Int -> Int -> Bool
 898 (I# x) `gtInt` (I# y) = x >#  y
 899 (I# x) `geInt` (I# y) = x >=# y
 900 (I# x) `eqInt` (I# y) = x ==# y
 901 (I# x) `neInt` (I# y) = x /=# y
 902 (I# x) `ltInt` (I# y) = x <#  y
 903 (I# x) `leInt` (I# y) = x <=# y
 904
 905 {-# RULES
 906 "x# ># x#"  forall x#. x# >#  x# = False
 907 "x# >=# x#" forall x#. x# >=# x# = True
 908 "x# ==# x#" forall x#. x# ==# x# = True
 909 "x# /=# x#" forall x#. x# /=# x# = False
 910 "x# <# x#"  forall x#. x# <#  x# = False
 911 "x# <=# x#" forall x#. x# <=# x# = True
 912   #-}
 913
 914 {-# RULES
 915 "plusFloat x 0.0"   forall x#. plusFloat#  x#   0.0# = x#
 916 "plusFloat 0.0 x"   forall x#. plusFloat#  0.0# x#   = x#
 917 "minusFloat x 0.0"  forall x#. minusFloat# x#   0.0# = x#
 918 "minusFloat x x"    forall x#. minusFloat# x#   x#   = 0.0#
 919 "timesFloat x 0.0"  forall x#. timesFloat# x#   0.0# = 0.0#
 920 "timesFloat0.0 x"   forall x#. timesFloat# 0.0# x#   = 0.0#
 921 "timesFloat x 1.0"  forall x#. timesFloat# x#   1.0# = x#
 922 "timesFloat 1.0 x"  forall x#. timesFloat# 1.0# x#   = x#
 923 "divideFloat x 1.0" forall x#. divideFloat# x#  1.0# = x#
 924   #-}
 925
 926 {-# RULES
 927 "plusDouble x 0.0"   forall x#. (+##) x#    0.0## = x#
 928 "plusDouble 0.0 x"   forall x#. (+##) 0.0## x#    = x#
 929 "minusDouble x 0.0"  forall x#. (-##) x#    0.0## = x#
 930 "timesDouble x 1.0"  forall x#. (*##) x#    1.0## = x#
 931 "timesDouble 1.0 x"  forall x#. (*##) 1.0## x#    = x#
 932 "divideDouble x 1.0" forall x#. (/##) x#    1.0## = x#
 933   #-}
 934
 935 {-
 936 We'd like to have more rules, but for example:
 937
 938 This gives wrong answer (0) for NaN - NaN (should be NaN):
 939     "minusDouble x x"    forall x#. (-##) x#    x#    = 0.0##
 940
 941 This gives wrong answer (0) for 0 * NaN (should be NaN):
 942     "timesDouble 0.0 x"  forall x#. (*##) 0.0## x#    = 0.0##
 943
 944 This gives wrong answer (0) for NaN * 0 (should be NaN):
 945     "timesDouble x 0.0"  forall x#. (*##) x#    0.0## = 0.0##
 946
 947 These are tested by num014.
 948 -}
 949
 950 -- Wrappers for the shift operations.  The uncheckedShift# family are
 951 -- undefined when the amount being shifted by is greater than the size
 952 -- in bits of Int#, so these wrappers perform a check and return
 953 -- either zero or -1 appropriately.
 954 --
 955 -- Note that these wrappers still produce undefined results when the
 956 -- second argument (the shift amount) is negative.
 957
 958 -- | Shift the argument left by the specified number of bits
 959 -- (which must be non-negative).
 960 shiftL# :: Word# -> Int# -> Word#
 961 a `shiftL#` b   | b >=# WORD_SIZE_IN_BITS# = int2Word# 0#
 962                 | otherwise                = a `uncheckedShiftL#` b
 963
 964 -- | Shift the argument right by the specified number of bits
 965 -- (which must be non-negative).
 966 shiftRL# :: Word# -> Int# -> Word#
 967 a `shiftRL#` b  | b >=# WORD_SIZE_IN_BITS# = int2Word# 0#
 968                 | otherwise                = a `uncheckedShiftRL#` b
 969
 970 -- | Shift the argument left by the specified number of bits
 971 -- (which must be non-negative).
 972 iShiftL# :: Int# -> Int# -> Int#
 973 a `iShiftL#` b  | b >=# WORD_SIZE_IN_BITS# = 0#
 974                 | otherwise                = a `uncheckedIShiftL#` b
 975
 976 -- | Shift the argument right (signed) by the specified number of bits
 977 -- (which must be non-negative).
 978 iShiftRA# :: Int# -> Int# -> Int#
 979 a `iShiftRA#` b | b >=# WORD_SIZE_IN_BITS# = if a <# 0# then (-1#) else 0#
 980                 | otherwise                = a `uncheckedIShiftRA#` b
 981
 982 -- | Shift the argument right (unsigned) by the specified number of bits
 983 -- (which must be non-negative).
 984 iShiftRL# :: Int# -> Int# -> Int#
 985 a `iShiftRL#` b | b >=# WORD_SIZE_IN_BITS# = 0#
 986                 | otherwise                = a `uncheckedIShiftRL#` b
 987
 988 #if WORD_SIZE_IN_BITS == 32
 989 {-# RULES
 990 "narrow32Int#"  forall x#. narrow32Int#   x# = x#
 991 "narrow32Word#" forall x#. narrow32Word#   x# = x#
 992    #-}
 993 #endif
 994
 995 {-# RULES
 996 "int2Word2Int"  forall x#. int2Word# (word2Int# x#) = x#
 997 "word2Int2Word" forall x#. word2Int# (int2Word# x#) = x#
 998   #-}
 999 \end{code}
1000
1001
1002 %********************************************************
1003 %*                                                      *
1004 \subsection{Unpacking C strings}
1005 %*                                                      *
1006 %********************************************************
1007
1008 This code is needed for virtually all programs, since it's used for
1009 unpacking the strings of error messages.
1010
1011 \begin{code}
1012 unpackCString# :: Addr# -> [Char]
1013 {-# NOINLINE [1] unpackCString# #-}
1014 unpackCString# addr
1015   = unpack 0#
1016   where
1017     unpack nh
1018       | ch `eqChar#` '\0'# = []
1019       | otherwise          = C# ch : unpack (nh +# 1#)
1020       where
1021         ch = indexCharOffAddr# addr nh
1022
1023 unpackAppendCString# :: Addr# -> [Char] -> [Char]
1024 unpackAppendCString# addr rest
1025   = unpack 0#
1026   where
1027     unpack nh
1028       | ch `eqChar#` '\0'# = rest
1029       | otherwise          = C# ch : unpack (nh +# 1#)
1030       where
1031         ch = indexCharOffAddr# addr nh
1032
1033 unpackFoldrCString# :: Addr# -> (Char  -> a -> a) -> a -> a
1034 {-# NOINLINE [0] unpackFoldrCString# #-}
1035 -- Don't inline till right at the end;
1036 -- usually the unpack-list rule turns it into unpackCStringList
1037 -- It also has a BuiltInRule in PrelRules.lhs:
1038 --      unpackFoldrCString# "foo" c (unpackFoldrCString# "baz" c n)
1039 --        =  unpackFoldrCString# "foobaz" c n
1040 unpackFoldrCString# addr f z
1041   = unpack 0#
1042   where
1043     unpack nh
1044       | ch `eqChar#` '\0'# = z
1045       | otherwise          = C# ch `f` unpack (nh +# 1#)
1046       where
1047         ch = indexCharOffAddr# addr nh
1048
1049 unpackCStringUtf8# :: Addr# -> [Char]
1050 unpackCStringUtf8# addr
1051   = unpack 0#
1052   where
1053     unpack nh
1054       | ch `eqChar#` '\0'#   = []
1055       | ch `leChar#` '\x7F'# = C# ch : unpack (nh +# 1#)
1056       | ch `leChar#` '\xDF'# =
1057           C# (chr# (((ord# ch                                  -# 0xC0#) `uncheckedIShiftL#`  6#) +#
1058                      (ord# (indexCharOffAddr# addr (nh +# 1#)) -# 0x80#))) :
1059           unpack (nh +# 2#)
1060       | ch `leChar#` '\xEF'# =
1061           C# (chr# (((ord# ch                                  -# 0xE0#) `uncheckedIShiftL#` 12#) +#
1062                     ((ord# (indexCharOffAddr# addr (nh +# 1#)) -# 0x80#) `uncheckedIShiftL#`  6#) +#
1063                      (ord# (indexCharOffAddr# addr (nh +# 2#)) -# 0x80#))) :
1064           unpack (nh +# 3#)
1065       | otherwise            =
1066           C# (chr# (((ord# ch                                  -# 0xF0#) `uncheckedIShiftL#` 18#) +#
1067                     ((ord# (indexCharOffAddr# addr (nh +# 1#)) -# 0x80#) `uncheckedIShiftL#` 12#) +#
1068                     ((ord# (indexCharOffAddr# addr (nh +# 2#)) -# 0x80#) `uncheckedIShiftL#`  6#) +#
1069                      (ord# (indexCharOffAddr# addr (nh +# 3#)) -# 0x80#))) :
1070           unpack (nh +# 4#)
1071       where
1072         ch = indexCharOffAddr# addr nh
1073
1074 unpackNBytes# :: Addr# -> Int# -> [Char]
1075 unpackNBytes# _addr 0#   = []
1076 unpackNBytes#  addr len# = unpack [] (len# -# 1#)
1077     where
1078      unpack acc i#
1079       | i# <# 0#  = acc
1080       | otherwise =
1081          case indexCharOffAddr# addr i# of
1082             ch -> unpack (C# ch : acc) (i# -# 1#)
1083
1084 {-# RULES
1085 "unpack"       [~1] forall a   . unpackCString# a                  = build (unpackFoldrCString# a)
1086 "unpack-list"  [1]  forall a   . unpackFoldrCString# a (:) [] = unpackCString# a
1087 "unpack-append"     forall a n . unpackFoldrCString# a (:) n  = unpackAppendCString# a n
1088
1089 -- There's a built-in rule (in PrelRules.lhs) for
1090 --      unpackFoldr "foo" c (unpackFoldr "baz" c n)  =  unpackFoldr "foobaz" c n
1091
1092   #-}
1093 \end{code}
1094
1095 #ifdef __HADDOCK__
1096 \begin{code}
1097 -- | A special argument for the 'Control.Monad.ST.ST' type constructor,
1098 -- indexing a state embedded in the 'Prelude.IO' monad by
1099 -- 'Control.Monad.ST.stToIO'.
1100 data RealWorld
1101 \end{code}
1102 #endif