ghc/lib/std/PrelBase.lhs

   1 %
   2 % (c) The GRAP/AQUA Project, Glasgow University, 1992-1996
   3 %
   4 \section[PrelBase]{Module @PrelBase@}
   5
   6
   7 The overall structure of the GHC Prelude is a bit tricky.
   8
   9   a) We want to avoid "orphan modules", i.e. ones with instance
  10         decls that don't belong either to a tycon or a class
  11         defined in the same module
  12
  13   b) We want to avoid giant modules
  14
  15 So the rough structure is as follows, in (linearised) dependency order
  16
  17
  18 PrelGHC         Has no implementation.  It defines built-in things, and
  19                 by importing it you bring them into scope.
  20                 The source file is PrelGHC.hi-boot, which is just
  21                 copied to make PrelGHC.hi
  22
  23                 Classes: CCallable, CReturnable
  24
  25 PrelBase        Classes: Eq, Ord, Functor, Monad
  26                 Types:   list, (), Int, Bool, Ordering, Char, String
  27
  28 PrelTup         Types: tuples, plus instances for PrelBase classes
  29
  30 PrelShow        Class: Show, plus instances for PrelBase/PrelTup types
  31
  32 PrelEnum        Class: Enum,  plus instances for PrelBase/PrelTup types
  33
  34 PrelMaybe       Type: Maybe, plus instances for PrelBase classes
  35
  36 PrelNum         Class: Num, plus instances for Int
  37                 Type:  Integer, plus instances for all classes so far (Eq, Ord, Num, Show)
  38
  39                 Integer is needed here because it is mentioned in the signature
  40                 of 'fromInteger' in class Num
  41
  42 PrelReal        Classes: Real, Integral, Fractional, RealFrac
  43                          plus instances for Int, Integer
  44                 Types:  Ratio, Rational
  45                         plus intances for classes so far
  46
  47                 Rational is needed here because it is mentioned in the signature
  48                 of 'toRational' in class Real
  49
  50 Ix              Classes: Ix, plus instances for Int, Bool, Char, Integer, Ordering, tuples
  51
  52 PrelArr         Types: Array, MutableArray, MutableVar
  53
  54                 Does *not* contain any ByteArray stuff (see PrelByteArr)
  55                 Arrays are used by a function in PrelFloat
  56
  57 PrelFloat       Classes: Floating, RealFloat
  58                 Types:   Float, Double, plus instances of all classes so far
  59
  60                 This module contains everything to do with floating point.
  61                 It is a big module (900 lines)
  62                 With a bit of luck, many modules can be compiled without ever reading PrelFloat.hi
  63
  64 PrelByteArr     Types: ByteArray, MutableByteArray
  65
  66                 We want this one to be after PrelFloat, because it defines arrays
  67                 of unboxed floats.
  68
  69
  70 Other Prelude modules are much easier with fewer complex dependencies.
  71
  72
  73 \begin{code}
  74 {-# OPTIONS -fno-implicit-prelude #-}
  75
  76 module PrelBase
  77         (
  78         module PrelBase,
  79         module PrelGHC          -- Re-export PrelGHC, to avoid lots of people
  80                                 -- having to import it explicitly
  81   )
  82         where
  83
  84 import {-# SOURCE #-} PrelErr ( error )
  85 import {-# SOURCE #-} PrelNum ( addr2Integer )
  86   -- Otherwise the system import of addr2Integer looks for PrelNum.hi
  87
  88 import PrelGHC
  89
  90 infixr 9  .
  91 infixr 5  ++, :
  92 infix  4  ==, /=, <, <=, >=, >
  93 infixr 3  &&
  94 infixr 2  ||
  95 infixl 1  >>, >>=
  96 infixr 0  $
  97
  98 default ()              -- Double isn't available yet
  99 \end{code}
 100
 101
 102 %*********************************************************
 103 %*                                                      *
 104 \subsection{DEBUGGING STUFF}
 105 %*  (for use when compiling PrelBase itself doesn't work)
 106 %*                                                      *
 107 %*********************************************************
 108
 109 \begin{code}
 110 {-
 111 data  Bool  =  False | True
 112 data Ordering = LT | EQ | GT
 113 data Char = C# Char#
 114 type  String = [Char]
 115 data Int = I# Int#
 116 data  ()  =  ()
 117 -- data [] a = MkNil
 118
 119 not True = False
 120 (&&) True True = True
 121 otherwise = True
 122
 123 build = error "urk"
 124 foldr = error "urk"
 125
 126 unpackCString#  :: Addr# -> [Char]
 127 unpackFoldrCString#  :: Addr# -> (Char  -> a -> a) -> a -> a
 128 unpackAppendCString# :: Addr# -> [Char] -> [Char]
 129 unpackNBytes#      :: Addr# -> Int#   -> [Char]
 130 unpackNBytes# a b = error "urk"
 131 unpackCString# a = error "urk"
 132 unpackFoldrCString# a = error "urk"
 133 unpackAppendCString# a = error "urk"
 134 -}
 135 \end{code}
 136
 137
 138 %*********************************************************
 139 %*                                                      *
 140 \subsection{Standard classes @Eq@, @Ord@}
 141 %*                                                      *
 142 %*********************************************************
 143
 144 \begin{code}
 145 class  Eq a  where
 146     (==), (/=)          :: a -> a -> Bool
 147
 148 --    x /= y            = not (x == y)
 149 --    x == y            = not (x /= y)
 150 --    x /= y            =  True
 151     (/=) x y            = not  ((==) x y)
 152     x == y              =  True
 153
 154 class  (Eq a) => Ord a  where
 155     compare             :: a -> a -> Ordering
 156     (<), (<=), (>=), (>):: a -> a -> Bool
 157     max, min            :: a -> a -> a
 158
 159 -- An instance of Ord should define either compare or <=
 160 -- Using compare can be more efficient for complex types.
 161     compare x y
 162             | x == y    = EQ
 163             | x <= y    = LT    -- NB: must be '<=' not '<' to validate the
 164                                 -- above claim about the minimal things that can
 165                                 -- be defined for an instance of Ord
 166             | otherwise = GT
 167
 168     x <= y  = case compare x y of { GT -> False; _other -> True }
 169     x <  y  = case compare x y of { LT -> True;  _other -> False }
 170     x >= y  = case compare x y of { LT -> False; _other -> True }
 171     x >  y  = case compare x y of { GT -> True;  _other -> False }
 172
 173         -- These two default methods use '>' rather than compare
 174         -- because the latter is often more expensive
 175     max x y = if x > y then x else y
 176     min x y = if x > y then y else x
 177 \end{code}
 178
 179 %*********************************************************
 180 %*                                                      *
 181 \subsection{Monadic classes @Functor@, @Monad@ }
 182 %*                                                      *
 183 %*********************************************************
 184
 185 \begin{code}
 186 class  Functor f  where
 187     fmap         :: (a -> b) -> f a -> f b
 188
 189 class  Monad m  where
 190     (>>=)       :: m a -> (a -> m b) -> m b
 191     (>>)        :: m a -> m b -> m b
 192     return      :: a -> m a
 193     fail        :: String -> m a
 194
 195     m >> k      =  m >>= \_ -> k
 196     fail s      = error s
 197
 198 \end{code}
 199
 200
 201 %*********************************************************
 202 %*                                                      *
 203 \subsection{The list type}
 204 %*                                                      *
 205 %*********************************************************
 206
 207 \begin{code}
 208 data [] a = [] | a : [a]  -- do explicitly: deriving (Eq, Ord)
 209                           -- to avoid weird names like con2tag_[]#
 210
 211
 212 instance (Eq a) => Eq [a]  where
 213 {-
 214     {-# SPECIALISE instance Eq [Char] #-}
 215 -}
 216     []     == []     = True
 217     (x:xs) == (y:ys) = x == y && xs == ys
 218     _xs    == _ys    = False
 219
 220     xs     /= ys     = if (xs == ys) then False else True
 221
 222 instance (Ord a) => Ord [a] where
 223 {-
 224     {-# SPECIALISE instance Ord [Char] #-}
 225 -}
 226     a <  b  = case compare a b of { LT -> True;  EQ -> False; GT -> False }
 227     a <= b  = case compare a b of { LT -> True;  EQ -> True;  GT -> False }
 228     a >= b  = case compare a b of { LT -> False; EQ -> True;  GT -> True  }
 229     a >  b  = case compare a b of { LT -> False; EQ -> False; GT -> True  }
 230
 231     compare []     []     = EQ
 232     compare (_:_)  []     = GT
 233     compare []     (_:_)  = LT
 234     compare (x:xs) (y:ys) = case compare x y of
 235                                  LT -> LT
 236                                  GT -> GT
 237                                  EQ -> compare xs ys
 238
 239 instance Functor [] where
 240     fmap = map
 241
 242 instance  Monad []  where
 243     m >>= k             = foldr ((++) . k) [] m
 244     m >> k              = foldr ((++) . (\ _ -> k)) [] m
 245     return x            = [x]
 246     fail _              = []
 247 \end{code}
 248
 249 A few list functions that appear here because they are used here.
 250 The rest of the prelude list functions are in PrelList.
 251
 252 ----------------------------------------------
 253 --      foldr/build/augment
 254 ----------------------------------------------
 255
 256 \begin{code}
 257 foldr            :: (a -> b -> b) -> b -> [a] -> b
 258 -- foldr _ z []     =  z
 259 -- foldr f z (x:xs) =  f x (foldr f z xs)
 260 {-# INLINE foldr #-}
 261 foldr k z xs = go xs
 262              where
 263                go []     = z
 264                go (x:xs) = x `k` go xs
 265
 266 build   :: forall a. (forall b. (a -> b -> b) -> b -> b) -> [a]
 267 {-# INLINE 2 build #-}
 268         -- The INLINE is important, even though build is tiny,
 269         -- because it prevents [] getting inlined in the version that
 270         -- appears in the interface file.  If [] *is* inlined, it
 271         -- won't match with [] appearing in rules in an importing module.
 272         --
 273         -- The "2" says to inline in phase 2
 274
 275 build g = g (:) []
 276
 277 augment :: forall a. (forall b. (a->b->b) -> b -> b) -> [a] -> [a]
 278 {-# INLINE 2 augment #-}
 279 augment g xs = g (:) xs
 280
 281 {-# RULES
 282 "fold/build"    forall k z (g::forall b. (a->b->b) -> b -> b) .
 283                 foldr k z (build g) = g k z
 284
 285 "foldr/augment" forall k z xs (g::forall b. (a->b->b) -> b -> b) .
 286                 foldr k z (augment g xs) = g k (foldr k z xs)
 287
 288 "foldr/id"      foldr (:) [] = \x->x
 289 "foldr/app"     forall xs ys. foldr (:) ys xs = append xs ys
 290
 291 "foldr/cons"    forall k z x xs. foldr k z (x:xs) = k x (foldr k z xs)
 292 "foldr/nil"     forall k z.      foldr k z []     = z
 293
 294 "augment/build" forall (g::forall b. (a->b->b) -> b -> b)
 295                        (h::forall b. (a->b->b) -> b -> b) .
 296                        augment g (build h) = build (\c n -> g c (h c n))
 297 "augment/nil"   forall (g::forall b. (a->b->b) -> b -> b) .
 298                         augment g [] = build g
 299  #-}
 300
 301 -- This rule is true, but not (I think) useful:
 302 --      augment g (augment h t) = augment (\cn -> g c (h c n)) t
 303 \end{code}
 304
 305
 306 ----------------------------------------------
 307 --              map
 308 ----------------------------------------------
 309
 310 \begin{code}
 311 map :: (a -> b) -> [a] -> [b]
 312 map = mapList
 313
 314 -- Note eta expanded
 315 mapFB c f x ys = c (f x) ys
 316
 317 mapList :: (a -> b) -> [a] -> [b]
 318 mapList _ []     = []
 319 mapList f (x:xs) = f x : mapList f xs
 320
 321 {-# RULES
 322 "map"       forall f xs.        map f xs                = build (\c n -> foldr (mapFB c f) n xs)
 323 "mapFB"     forall c f g.       mapFB (mapFB c f) g     = mapFB c (f.g)
 324 "mapList"   forall f.           foldr (mapFB (:) f) []  = mapList f
 325  #-}
 326 \end{code}
 327
 328
 329 ----------------------------------------------
 330 --              append
 331 ----------------------------------------------
 332 \begin{code}
 333 (++) :: [a] -> [a] -> [a]
 334 (++) = append
 335
 336 {-# RULES
 337   "++"  forall xs ys. (++) xs ys = augment (\c n -> foldr c n xs) ys
 338  #-}
 339
 340 append :: [a] -> [a] -> [a]
 341 append []     ys = ys
 342 append (x:xs) ys = x : append xs ys
 343 \end{code}
 344
 345
 346 %*********************************************************
 347 %*                                                      *
 348 \subsection{Type @Bool@}
 349 %*                                                      *
 350 %*********************************************************
 351
 352 \begin{code}
 353 data  Bool  =  False | True  deriving (Eq, Ord)
 354         -- Read in PrelRead, Show in PrelShow
 355
 356 -- Boolean functions
 357
 358 (&&), (||)              :: Bool -> Bool -> Bool
 359 True  && x              =  x
 360 False && _              =  False
 361 True  || _              =  True
 362 False || x              =  x
 363
 364 not                     :: Bool -> Bool
 365 not True                =  False
 366 not False               =  True
 367
 368 otherwise               :: Bool
 369 otherwise               =  True
 370 \end{code}
 371
 372
 373 %*********************************************************
 374 %*                                                      *
 375 \subsection{The @()@ type}
 376 %*                                                      *
 377 %*********************************************************
 378
 379 The Unit type is here because virtually any program needs it (whereas
 380 some programs may get away without consulting PrelTup).  Furthermore,
 381 the renamer currently *always* asks for () to be in scope, so that
 382 ccalls can use () as their default type; so when compiling PrelBase we
 383 need ().  (We could arrange suck in () only if -fglasgow-exts, but putting
 384 it here seems more direct.)
 385
 386 \begin{code}
 387 data  ()  =  ()
 388
 389 instance Eq () where
 390     () == () = True
 391     () /= () = False
 392
 393 instance Ord () where
 394     () <= () = True
 395     () <  () = False
 396     () >= () = True
 397     () >  () = False
 398     max () () = ()
 399     min () () = ()
 400     compare () () = EQ
 401 \end{code}
 402
 403
 404 %*********************************************************
 405 %*                                                      *
 406 \subsection{Type @Ordering@}
 407 %*                                                      *
 408 %*********************************************************
 409
 410 \begin{code}
 411 data Ordering = LT | EQ | GT deriving (Eq, Ord)
 412         -- Read in PrelRead, Show in PrelShow
 413 \end{code}
 414
 415
 416 %*********************************************************
 417 %*                                                      *
 418 \subsection{Type @Char@ and @String@}
 419 %*                                                      *
 420 %*********************************************************
 421
 422 \begin{code}
 423 type  String = [Char]
 424
 425 data Char = C# Char#
 426
 427 -- We don't use deriving for Eq and Ord, because for Ord the derived
 428 -- instance defines only compare, which takes two primops.  Then
 429 -- '>' uses compare, and therefore takes two primops instead of one.
 430
 431 instance Eq Char where
 432   (C# c1) == (C# c2) = c1 `eqChar#` c2
 433   (C# c1) /= (C# c2) = c1 `neChar#` c2
 434
 435 instance Ord Char where
 436   (C# c1) >  (C# c2) = c1 `gtChar#` c2
 437   (C# c1) >= (C# c2) = c1 `geChar#` c2
 438   (C# c1) <= (C# c2) = c1 `leChar#` c2
 439   (C# c1) <  (C# c2) = c1 `ltChar#` c2
 440
 441 chr :: Int -> Char
 442 chr (I# i) | i >=# 0# && i <=# 255# = C# (chr# i)
 443            | otherwise = error ("Prelude.chr: bad argument")
 444
 445 unsafeChr :: Int -> Char
 446 unsafeChr (I# i) =  C# (chr# i)
 447
 448 ord :: Char -> Int
 449 ord (C# c) =  I# (ord# c)
 450 \end{code}
 451
 452
 453 %*********************************************************
 454 %*                                                      *
 455 \subsection{Type @Int@}
 456 %*                                                      *
 457 %*********************************************************
 458
 459 \begin{code}
 460 data Int = I# Int#
 461
 462 zeroInt, oneInt, twoInt, maxInt, minInt :: Int
 463 zeroInt = I# 0#
 464 oneInt  = I# 1#
 465 twoInt  = I# 2#
 466 minInt  = I# (-2147483648#)     -- GHC <= 2.09 had this at -2147483647
 467 maxInt  = I# 2147483647#
 468
 469 instance Eq Int where
 470     (==) x y = x `eqInt` y
 471     (/=) x y = x `neInt` y
 472
 473 instance Ord Int where
 474     compare x y = compareInt x y
 475
 476     (<)  x y = ltInt x y
 477     (<=) x y = leInt x y
 478     (>=) x y = geInt x y
 479     (>)  x y = gtInt x y
 480
 481 compareInt :: Int -> Int -> Ordering
 482 (I# x) `compareInt` (I# y) | x <# y    = LT
 483                            | x ==# y   = EQ
 484                            | otherwise = GT
 485 \end{code}
 486
 487
 488 %*********************************************************
 489 %*                                                      *
 490 \subsection{The function type}
 491 %*                                                      *
 492 %*********************************************************
 493
 494 \begin{code}
 495 -- identity function
 496 id                      :: a -> a
 497 id x                    =  x
 498
 499 -- constant function
 500 const                   :: a -> b -> a
 501 const x _               =  x
 502
 503 -- function composition
 504 {-# INLINE (.) #-}
 505 (.)       :: (b -> c) -> (a -> b) -> a -> c
 506 (.) f g x = f (g x)
 507
 508 -- flip f  takes its (first) two arguments in the reverse order of f.
 509 flip                    :: (a -> b -> c) -> b -> a -> c
 510 flip f x y              =  f y x
 511
 512 -- right-associating infix application operator (useful in continuation-
 513 -- passing style)
 514 ($)                     :: (a -> b) -> a -> b
 515 f $ x                   =  f x
 516
 517 -- until p f  yields the result of applying f until p holds.
 518 until                   :: (a -> Bool) -> (a -> a) -> a -> a
 519 until p f x | p x       =  x
 520             | otherwise =  until p f (f x)
 521
 522 -- asTypeOf is a type-restricted version of const.  It is usually used
 523 -- as an infix operator, and its typing forces its first argument
 524 -- (which is usually overloaded) to have the same type as the second.
 525 asTypeOf                :: a -> a -> a
 526 asTypeOf                =  const
 527 \end{code}
 528
 529 %*********************************************************
 530 %*                                                      *
 531 \subsection{CCallable instances}
 532 %*                                                      *
 533 %*********************************************************
 534
 535 Defined here to avoid orphans
 536
 537 \begin{code}
 538 instance CCallable Char
 539 instance CReturnable Char
 540
 541 instance CCallable   Int
 542 instance CReturnable Int
 543
 544 instance CReturnable () -- Why, exactly?
 545 \end{code}
 546
 547
 548 %*********************************************************
 549 %*                                                      *
 550 \subsection{Numeric primops}
 551 %*                                                      *
 552 %*********************************************************
 553
 554 Definitions of the boxed PrimOps; these will be
 555 used in the case of partial applications, etc.
 556
 557 \begin{code}
 558 {-# INLINE eqInt #-}
 559 {-# INLINE neInt #-}
 560 {-# INLINE gtInt #-}
 561 {-# INLINE geInt #-}
 562 {-# INLINE ltInt #-}
 563 {-# INLINE leInt #-}
 564 {-# INLINE plusInt #-}
 565 {-# INLINE minusInt #-}
 566 {-# INLINE timesInt #-}
 567 {-# INLINE quotInt #-}
 568 {-# INLINE remInt #-}
 569 {-# INLINE negateInt #-}
 570
 571 plusInt, minusInt, timesInt, quotInt, remInt, gcdInt :: Int -> Int -> Int
 572 plusInt (I# x) (I# y) = I# (x +# y)
 573 minusInt(I# x) (I# y) = I# (x -# y)
 574 timesInt(I# x) (I# y) = I# (x *# y)
 575 quotInt (I# x) (I# y) = I# (quotInt# x y)
 576 remInt  (I# x) (I# y) = I# (remInt#  x y)
 577
 578 gcdInt  (I# 0#) (I# 0#) = error "PrelBase.gcdInt: gcd 0 0 is undefined"
 579 gcdInt  a       (I# 0#) = a
 580 gcdInt  (I# 0#) b       = b
 581 gcdInt  (I# a)  (I# b)  = I# (gcdInt# (absInt a) (absInt b))
 582    where absInt x = if x <# 0# then negateInt# x else x
 583
 584 negateInt :: Int -> Int
 585 negateInt (I# x) = I# (negateInt# x)
 586
 587 divInt, modInt :: Int -> Int -> Int
 588 x `divInt` y
 589   | x > zeroInt && y < zeroInt = quotInt ((x `minusInt` y) `minusInt` oneInt) y
 590   | x < zeroInt && y > zeroInt = quotInt ((x `minusInt` y) `plusInt`  oneInt) y
 591   | otherwise      = quotInt x y
 592
 593 x `modInt` y
 594   | x > zeroInt && y < zeroInt ||
 595     x < zeroInt && y > zeroInt  = if r/=zeroInt then r `plusInt` y else zeroInt
 596   | otherwise                   = r
 597   where
 598     r = remInt x y
 599
 600 gtInt, geInt, eqInt, neInt, ltInt, leInt :: Int -> Int -> Bool
 601 gtInt   (I# x) (I# y) = x ># y
 602 geInt   (I# x) (I# y) = x >=# y
 603 eqInt   (I# x) (I# y) = x ==# y
 604 neInt   (I# x) (I# y) = x /=# y
 605 ltInt   (I# x) (I# y) = x <# y
 606 leInt   (I# x) (I# y) = x <=# y
 607 \end{code}
 608
 609
 610 %********************************************************
 611 %*                                                      *
 612 \subsection{Unpacking C strings}
 613 %*                                                      *
 614 %********************************************************
 615
 616 This code is needed for virtually all programs, since it's used for
 617 unpacking the strings of error messages.
 618
 619 \begin{code}
 620 unpackCString#  :: Addr# -> [Char]
 621 unpackCString# a = unpackCStringList# a
 622
 623 unpackCStringList#  :: Addr# -> [Char]
 624 unpackCStringList# addr
 625   = unpack 0#
 626   where
 627     unpack nh
 628       | ch `eqChar#` '\0'# = []
 629       | otherwise          = C# ch : unpack (nh +# 1#)
 630       where
 631         ch = indexCharOffAddr# addr nh
 632
 633 unpackAppendCString# :: Addr# -> [Char] -> [Char]
 634 unpackAppendCString# addr rest
 635   = unpack 0#
 636   where
 637     unpack nh
 638       | ch `eqChar#` '\0'# = rest
 639       | otherwise          = C# ch : unpack (nh +# 1#)
 640       where
 641         ch = indexCharOffAddr# addr nh
 642
 643 unpackFoldrCString#  :: Addr# -> (Char  -> a -> a) -> a -> a
 644 unpackFoldrCString# addr f z
 645   = unpack 0#
 646   where
 647     unpack nh
 648       | ch `eqChar#` '\0'# = z
 649       | otherwise          = C# ch `f` unpack (nh +# 1#)
 650       where
 651         ch = indexCharOffAddr# addr nh
 652
 653 unpackNBytes#      :: Addr# -> Int#   -> [Char]
 654   -- This one is called by the compiler to unpack literal
 655   -- strings with NULs in them; rare. It's strict!
 656   -- We don't try to do list deforestation for this one
 657
 658 unpackNBytes# _addr 0#   = []
 659 unpackNBytes#  addr len# = unpack [] (len# -# 1#)
 660     where
 661      unpack acc i#
 662       | i# <# 0#  = acc
 663       | otherwise =
 664          case indexCharOffAddr# addr i# of
 665             ch -> unpack (C# ch : acc) (i# -# 1#)
 666
 667 {-# RULES
 668 "unpack"         forall a   . unpackCString# a             = build (unpackFoldrCString# a)
 669 "unpack-list"    forall a   . unpackFoldrCString# a (:) [] = unpackCStringList# a
 670 "unpack-append"  forall a n . unpackFoldrCString# a (:) n  = unpackAppendCString# a n
 671
 672 -- There's a built-in rule (in PrelRules.lhs) for
 673 --      unpackFoldr "foo" c (unpackFoldr "baz" c n)  =  unpackFoldr "foobaz" c n
 674
 675   #-}
 676
 677 \end{code}