1 % -----------------------------------------------------------------------------
2 % $Id: PrelBase.lhs,v 1.39 2000/10/03 08:43:05 simonpj Exp $
4 % (c) The University of Glasgow, 1992-2000
6 \section[PrelBase]{Module @PrelBase@}
9 The overall structure of the GHC Prelude is a bit tricky.
11 a) We want to avoid "orphan modules", i.e. ones with instance
12 decls that don't belong either to a tycon or a class
13 defined in the same module
15 b) We want to avoid giant modules
17 So the rough structure is as follows, in (linearised) dependency order
20 PrelGHC Has no implementation. It defines built-in things, and
21 by importing it you bring them into scope.
22 The source file is PrelGHC.hi-boot, which is just
23 copied to make PrelGHC.hi
25 Classes: CCallable, CReturnable
27 PrelBase Classes: Eq, Ord, Functor, Monad
28 Types: list, (), Int, Bool, Ordering, Char, String
30 PrelTup Types: tuples, plus instances for PrelBase classes
32 PrelShow Class: Show, plus instances for PrelBase/PrelTup types
34 PrelEnum Class: Enum, plus instances for PrelBase/PrelTup types
36 PrelMaybe Type: Maybe, plus instances for PrelBase classes
38 PrelNum Class: Num, plus instances for Int
39 Type: Integer, plus instances for all classes so far (Eq, Ord, Num, Show)
41 Integer is needed here because it is mentioned in the signature
42 of 'fromInteger' in class Num
44 PrelReal Classes: Real, Integral, Fractional, RealFrac
45 plus instances for Int, Integer
46 Types: Ratio, Rational
47 plus intances for classes so far
49 Rational is needed here because it is mentioned in the signature
50 of 'toRational' in class Real
52 Ix Classes: Ix, plus instances for Int, Bool, Char, Integer, Ordering, tuples
54 PrelArr Types: Array, MutableArray, MutableVar
56 Does *not* contain any ByteArray stuff (see PrelByteArr)
57 Arrays are used by a function in PrelFloat
59 PrelFloat Classes: Floating, RealFloat
60 Types: Float, Double, plus instances of all classes so far
62 This module contains everything to do with floating point.
63 It is a big module (900 lines)
64 With a bit of luck, many modules can be compiled without ever reading PrelFloat.hi
66 PrelByteArr Types: ByteArray, MutableByteArray
68 We want this one to be after PrelFloat, because it defines arrays
72 Other Prelude modules are much easier with fewer complex dependencies.
76 {-# OPTIONS -fno-implicit-prelude #-}
81 module PrelGHC, -- Re-export PrelGHC, PrelErr & PrelNum, to avoid lots
82 module PrelErr -- of people having to import it explicitly
87 import {-# SOURCE #-} PrelErr
91 infix 4 ==, /=, <, <=, >=, >
97 default () -- Double isn't available yet
101 %*********************************************************
103 \subsection{DEBUGGING STUFF}
104 %* (for use when compiling PrelBase itself doesn't work)
106 %*********************************************************
110 data Bool = False | True
111 data Ordering = LT | EQ | GT
119 (&&) True True = True
125 unpackCString# :: Addr# -> [Char]
126 unpackFoldrCString# :: Addr# -> (Char -> a -> a) -> a -> a
127 unpackAppendCString# :: Addr# -> [Char] -> [Char]
128 unpackCStringUtf8# :: Addr# -> [Char]
129 unpackCString# a = error "urk"
130 unpackFoldrCString# a = error "urk"
131 unpackAppendCString# a = error "urk"
132 unpackCStringUtf8# a = error "urk"
137 %*********************************************************
139 \subsection{Standard classes @Eq@, @Ord@}
141 %*********************************************************
145 (==), (/=) :: a -> a -> Bool
147 (/=) x y = not ((==) x y)
148 (==) x y = not ((/=) x y)
150 class (Eq a) => Ord a where
151 compare :: a -> a -> Ordering
152 (<), (<=), (>=), (>):: a -> a -> Bool
153 max, min :: a -> a -> a
155 -- An instance of Ord should define either compare or <=
156 -- Using compare can be more efficient for complex types.
159 | x <= y = LT -- NB: must be '<=' not '<' to validate the
160 -- above claim about the minimal things that can
161 -- be defined for an instance of Ord
164 x <= y = case compare x y of { GT -> False; _other -> True }
165 x < y = case compare x y of { LT -> True; _other -> False }
166 x >= y = case compare x y of { LT -> False; _other -> True }
167 x > y = case compare x y of { GT -> True; _other -> False }
169 -- These two default methods use '>' rather than compare
170 -- because the latter is often more expensive
171 max x y = if x > y then x else y
172 min x y = if x > y then y else x
175 %*********************************************************
177 \subsection{Monadic classes @Functor@, @Monad@ }
179 %*********************************************************
182 class Functor f where
183 fmap :: (a -> b) -> f a -> f b
186 (>>=) :: m a -> (a -> m b) -> m b
187 (>>) :: m a -> m b -> m b
189 fail :: String -> m a
191 m >> k = m >>= \_ -> k
196 %*********************************************************
198 \subsection{The list type}
200 %*********************************************************
203 data [] a = [] | a : [a] -- do explicitly: deriving (Eq, Ord)
204 -- to avoid weird names like con2tag_[]#
207 instance (Eq a) => Eq [a] where
209 {-# SPECIALISE instance Eq [Char] #-}
212 (x:xs) == (y:ys) = x == y && xs == ys
215 xs /= ys = if (xs == ys) then False else True
217 instance (Ord a) => Ord [a] where
219 {-# SPECIALISE instance Ord [Char] #-}
221 a < b = case compare a b of { LT -> True; EQ -> False; GT -> False }
222 a <= b = case compare a b of { LT -> True; EQ -> True; GT -> False }
223 a >= b = case compare a b of { LT -> False; EQ -> True; GT -> True }
224 a > b = case compare a b of { LT -> False; EQ -> False; GT -> True }
227 compare (_:_) [] = GT
228 compare [] (_:_) = LT
229 compare (x:xs) (y:ys) = case compare x y of
234 instance Functor [] where
237 instance Monad [] where
238 m >>= k = foldr ((++) . k) [] m
239 m >> k = foldr ((++) . (\ _ -> k)) [] m
244 A few list functions that appear here because they are used here.
245 The rest of the prelude list functions are in PrelList.
247 ----------------------------------------------
248 -- foldr/build/augment
249 ----------------------------------------------
252 foldr :: (a -> b -> b) -> b -> [a] -> b
254 -- foldr f z (x:xs) = f x (foldr f z xs)
259 go (y:ys) = y `k` go ys
261 build :: forall a. (forall b. (a -> b -> b) -> b -> b) -> [a]
262 {-# INLINE 2 build #-}
263 -- The INLINE is important, even though build is tiny,
264 -- because it prevents [] getting inlined in the version that
265 -- appears in the interface file. If [] *is* inlined, it
266 -- won't match with [] appearing in rules in an importing module.
268 -- The "2" says to inline in phase 2
272 augment :: forall a. (forall b. (a->b->b) -> b -> b) -> [a] -> [a]
273 {-# INLINE 2 augment #-}
274 augment g xs = g (:) xs
277 "fold/build" forall k z (g::forall b. (a->b->b) -> b -> b) .
278 foldr k z (build g) = g k z
280 "foldr/augment" forall k z xs (g::forall b. (a->b->b) -> b -> b) .
281 foldr k z (augment g xs) = g k (foldr k z xs)
283 "foldr/id" foldr (:) [] = \x->x
284 "foldr/app" forall xs ys. foldr (:) ys xs = append xs ys
286 "foldr/cons" forall k z x xs. foldr k z (x:xs) = k x (foldr k z xs)
287 "foldr/nil" forall k z. foldr k z [] = z
289 "augment/build" forall (g::forall b. (a->b->b) -> b -> b)
290 (h::forall b. (a->b->b) -> b -> b) .
291 augment g (build h) = build (\c n -> g c (h c n))
292 "augment/nil" forall (g::forall b. (a->b->b) -> b -> b) .
293 augment g [] = build g
296 -- This rule is true, but not (I think) useful:
297 -- augment g (augment h t) = augment (\cn -> g c (h c n)) t
301 ----------------------------------------------
303 ----------------------------------------------
306 map :: (a -> b) -> [a] -> [b]
310 mapFB :: (elt -> lst -> lst) -> (a -> elt) -> a -> lst -> lst
311 mapFB c f x ys = c (f x) ys
313 mapList :: (a -> b) -> [a] -> [b]
315 mapList f (x:xs) = f x : mapList f xs
318 "map" forall f xs. map f xs = build (\c n -> foldr (mapFB c f) n xs)
319 "mapFB" forall c f g. mapFB (mapFB c f) g = mapFB c (f.g)
320 "mapList" forall f. foldr (mapFB (:) f) [] = mapList f
325 ----------------------------------------------
327 ----------------------------------------------
329 (++) :: [a] -> [a] -> [a]
333 "++" forall xs ys. (++) xs ys = augment (\c n -> foldr c n xs) ys
336 append :: [a] -> [a] -> [a]
338 append (x:xs) ys = x : append xs ys
342 %*********************************************************
344 \subsection{Type @Bool@}
346 %*********************************************************
349 data Bool = False | True deriving (Eq, Ord)
350 -- Read in PrelRead, Show in PrelShow
354 (&&), (||) :: Bool -> Bool -> Bool
369 %*********************************************************
371 \subsection{The @()@ type}
373 %*********************************************************
375 The Unit type is here because virtually any program needs it (whereas
376 some programs may get away without consulting PrelTup). Furthermore,
377 the renamer currently *always* asks for () to be in scope, so that
378 ccalls can use () as their default type; so when compiling PrelBase we
379 need (). (We could arrange suck in () only if -fglasgow-exts, but putting
380 it here seems more direct.)
389 instance Ord () where
400 %*********************************************************
402 \subsection{Type @Ordering@}
404 %*********************************************************
407 data Ordering = LT | EQ | GT deriving (Eq, Ord)
408 -- Read in PrelRead, Show in PrelShow
412 %*********************************************************
414 \subsection{Type @Char@ and @String@}
416 %*********************************************************
423 -- We don't use deriving for Eq and Ord, because for Ord the derived
424 -- instance defines only compare, which takes two primops. Then
425 -- '>' uses compare, and therefore takes two primops instead of one.
427 instance Eq Char where
428 (C# c1) == (C# c2) = c1 `eqChar#` c2
429 (C# c1) /= (C# c2) = c1 `neChar#` c2
431 instance Ord Char where
432 (C# c1) > (C# c2) = c1 `gtChar#` c2
433 (C# c1) >= (C# c2) = c1 `geChar#` c2
434 (C# c1) <= (C# c2) = c1 `leChar#` c2
435 (C# c1) < (C# c2) = c1 `ltChar#` c2
438 chr (I# i) | i >=# 0#
439 #if INT_SIZE_IN_BYTES > 4
443 | otherwise = error ("Prelude.chr: bad argument")
445 unsafeChr :: Int -> Char
446 unsafeChr (I# i) = C# (chr# i)
449 ord (C# c) = I# (ord# c)
452 String equality is used when desugaring pattern-matches against strings.
453 It's worth making it fast, and providing a rule to use the fast version
457 eqString :: String -> String -> Bool
458 eqString [] [] = True
459 eqString (C# c1 : cs1) (C# c2 : cs2) = c1 `eqChar#` c2 && cs1 `eqString` cs2
463 "eqString" (==) = eqString
467 %*********************************************************
469 \subsection{Type @Int@}
471 %*********************************************************
476 zeroInt, oneInt, twoInt, maxInt, minInt :: Int
480 minInt = I# (-2147483648#) -- GHC <= 2.09 had this at -2147483647
481 maxInt = I# 2147483647#
483 instance Eq Int where
484 (==) x y = x `eqInt` y
485 (/=) x y = x `neInt` y
487 instance Ord Int where
488 compare x y = compareInt x y
495 compareInt :: Int -> Int -> Ordering
496 (I# x) `compareInt` (I# y) | x <# y = LT
502 %*********************************************************
504 \subsection{The function type}
506 %*********************************************************
517 -- function composition
519 (.) :: (b -> c) -> (a -> b) -> a -> c
522 -- flip f takes its (first) two arguments in the reverse order of f.
523 flip :: (a -> b -> c) -> b -> a -> c
526 -- right-associating infix application operator (useful in continuation-
528 ($) :: (a -> b) -> a -> b
531 -- until p f yields the result of applying f until p holds.
532 until :: (a -> Bool) -> (a -> a) -> a -> a
533 until p f x | p x = x
534 | otherwise = until p f (f x)
536 -- asTypeOf is a type-restricted version of const. It is usually used
537 -- as an infix operator, and its typing forces its first argument
538 -- (which is usually overloaded) to have the same type as the second.
539 asTypeOf :: a -> a -> a
543 %*********************************************************
545 \subsection{CCallable instances}
547 %*********************************************************
549 Defined here to avoid orphans
552 instance CCallable Char
553 instance CReturnable Char
555 instance CCallable Int
556 instance CReturnable Int
558 instance CReturnable () -- Why, exactly?
562 %*********************************************************
564 \subsection{Generics}
566 %*********************************************************
570 data a :+: b = Inl a | Inr b
571 data a :*: b = a :*: b
575 %*********************************************************
577 \subsection{Numeric primops}
579 %*********************************************************
581 Definitions of the boxed PrimOps; these will be
582 used in the case of partial applications, etc.
591 {-# INLINE plusInt #-}
592 {-# INLINE minusInt #-}
593 {-# INLINE timesInt #-}
594 {-# INLINE quotInt #-}
595 {-# INLINE remInt #-}
596 {-# INLINE negateInt #-}
598 plusInt, minusInt, timesInt, quotInt, remInt, gcdInt :: Int -> Int -> Int
599 plusInt (I# x) (I# y) = I# (x +# y)
600 minusInt(I# x) (I# y) = I# (x -# y)
601 timesInt(I# x) (I# y) = I# (x *# y)
602 quotInt (I# x) (I# y) = I# (quotInt# x y)
603 remInt (I# x) (I# y) = I# (remInt# x y)
605 gcdInt (I# a) (I# b) = g a b
606 where g 0# 0# = error "PrelBase.gcdInt: gcd 0 0 is undefined"
609 g _ _ = I# (gcdInt# absA absB)
611 absInt x = if x <# 0# then negateInt# x else x
616 negateInt :: Int -> Int
617 negateInt (I# x) = I# (negateInt# x)
619 divInt, modInt :: Int -> Int -> Int
621 | x > zeroInt && y < zeroInt = quotInt ((x `minusInt` y) `minusInt` oneInt) y
622 | x < zeroInt && y > zeroInt = quotInt ((x `minusInt` y) `plusInt` oneInt) y
623 | otherwise = quotInt x y
626 | x > zeroInt && y < zeroInt ||
627 x < zeroInt && y > zeroInt = if r/=zeroInt then r `plusInt` y else zeroInt
632 gtInt, geInt, eqInt, neInt, ltInt, leInt :: Int -> Int -> Bool
633 gtInt (I# x) (I# y) = x ># y
634 geInt (I# x) (I# y) = x >=# y
635 eqInt (I# x) (I# y) = x ==# y
636 neInt (I# x) (I# y) = x /=# y
637 ltInt (I# x) (I# y) = x <# y
638 leInt (I# x) (I# y) = x <=# y
642 %********************************************************
644 \subsection{Unpacking C strings}
646 %********************************************************
648 This code is needed for virtually all programs, since it's used for
649 unpacking the strings of error messages.
652 unpackCString# :: Addr# -> [Char]
653 unpackCString# a = unpackCStringList# a
655 unpackCStringList# :: Addr# -> [Char]
656 unpackCStringList# addr
660 | ch `eqChar#` '\0'# = []
661 | otherwise = C# ch : unpack (nh +# 1#)
663 ch = indexCharOffAddr# addr nh
665 unpackAppendCString# :: Addr# -> [Char] -> [Char]
666 unpackAppendCString# addr rest
670 | ch `eqChar#` '\0'# = rest
671 | otherwise = C# ch : unpack (nh +# 1#)
673 ch = indexCharOffAddr# addr nh
675 unpackFoldrCString# :: Addr# -> (Char -> a -> a) -> a -> a
676 unpackFoldrCString# addr f z
680 | ch `eqChar#` '\0'# = z
681 | otherwise = C# ch `f` unpack (nh +# 1#)
683 ch = indexCharOffAddr# addr nh
685 unpackCStringUtf8# :: Addr# -> [Char]
686 unpackCStringUtf8# addr
690 | ch `eqChar#` '\0'# = []
691 | ch `leChar#` '\x7F'# = C# ch : unpack (nh +# 1#)
692 | ch `leChar#` '\xDF'# = C# (chr# ((ord# ch `iShiftL#` 6#) +#
693 (ord# (indexCharOffAddr# addr (nh +# 1#))) -# 0x3080#))
695 | ch `leChar#` '\xEF'# = C# (chr# ((ord# ch `iShiftL#` 12#) +#
696 (ord# (indexCharOffAddr# addr (nh +# 1#)) `iShiftL#` 6#) +#
697 (ord# (indexCharOffAddr# addr (nh +# 2#))) -# 0xE2080#))
699 | ch `leChar#` '\xF7'# = C# (chr# ((ord# ch `iShiftL#` 18#) +#
700 (ord# (indexCharOffAddr# addr (nh +# 1#)) `iShiftL#` 12#) +#
701 (ord# (indexCharOffAddr# addr (nh +# 2#)) `iShiftL#` 6#) +#
702 (ord# (indexCharOffAddr# addr (nh +# 3#))) -# 0x3C82080#))
704 | ch `leChar#` '\xFB'# = C# (chr# ((ord# ch -# 0xF8# `iShiftL#` 24#) +#
705 (ord# (indexCharOffAddr# addr (nh +# 1#)) `iShiftL#` 18#) +#
706 (ord# (indexCharOffAddr# addr (nh +# 2#)) `iShiftL#` 12#) +#
707 (ord# (indexCharOffAddr# addr (nh +# 3#)) `iShiftL#` 6#) +#
708 (ord# (indexCharOffAddr# addr (nh +# 4#))) -# 0x2082080#))
710 | otherwise = C# (chr# (((ord# ch -# 0xFC#) `iShiftL#` 30#) +#
711 ((ord# (indexCharOffAddr# addr (nh +# 1#)) -# 0x80#)
713 (ord# (indexCharOffAddr# addr (nh +# 2#)) `iShiftL#` 18#) +#
714 (ord# (indexCharOffAddr# addr (nh +# 3#)) `iShiftL#` 12#) +#
715 (ord# (indexCharOffAddr# addr (nh +# 4#)) `iShiftL#` 6#) +#
716 (ord# (indexCharOffAddr# addr (nh +# 5#))) -# 0x2082080#))
719 ch = indexCharOffAddr# addr nh
721 unpackNBytes# :: Addr# -> Int# -> [Char]
722 unpackNBytes# _addr 0# = []
723 unpackNBytes# addr len# = unpack [] (len# -# 1#)
728 case indexCharOffAddr# addr i# of
729 ch -> unpack (C# ch : acc) (i# -# 1#)
732 "unpack" forall a . unpackCString# a = build (unpackFoldrCString# a)
733 "unpack-list" forall a . unpackFoldrCString# a (:) [] = unpackCStringList# a
734 "unpack-append" forall a n . unpackFoldrCString# a (:) n = unpackAppendCString# a n
736 -- There's a built-in rule (in PrelRules.lhs) for
737 -- unpackFoldr "foo" c (unpackFoldr "baz" c n) = unpackFoldr "foobaz" c n