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