Add export lists to some modules.
[ghc.git] / libraries / base / GHC / Real.hs
1 {-# LANGUAGE Trustworthy #-}
2 {-# LANGUAGE CPP, NoImplicitPrelude, MagicHash, UnboxedTuples, BangPatterns #-}
3 {-# OPTIONS_GHC -fno-warn-orphans #-}
4 {-# OPTIONS_HADDOCK hide #-}
5
6 -----------------------------------------------------------------------------
7 -- |
8 -- Module : GHC.Real
9 -- Copyright : (c) The University of Glasgow, 1994-2002
10 -- License : see libraries/base/LICENSE
11 --
12 -- Maintainer : cvs-ghc@haskell.org
13 -- Stability : internal
14 -- Portability : non-portable (GHC Extensions)
15 --
16 -- The types 'Ratio' and 'Rational', and the classes 'Real', 'Fractional',
17 -- 'Integral', and 'RealFrac'.
18 --
19 -----------------------------------------------------------------------------
20
21 module GHC.Real
22 (
23 Fractional(..), Integral(..), Ratio(..), Real(..), RealFrac(..),
24
25 Rational,
26
27 (%), (^), (^%^), (^^), (^^%^^), denominator, divZeroError, even,
28 fromIntegral, gcd, gcdInt', gcdWord', infinity, integralEnumFrom,
29 integralEnumFromThen, integralEnumFromThenTo, integralEnumFromTo, lcm,
30 notANumber, numerator, numericEnumFrom, numericEnumFromThen,
31 numericEnumFromThenTo, numericEnumFromTo, odd, overflowError, ratioPrec,
32 ratioPrec1, ratioZeroDenominatorError, realToFrac, reduce, showSigned
33 ) where
34
35 import GHC.Base
36 import GHC.Num
37 import GHC.List
38 import GHC.Enum
39 import GHC.Show
40 import {-# SOURCE #-} GHC.Exception( divZeroException, overflowException, ratioZeroDenomException )
41
42 #ifdef OPTIMISE_INTEGER_GCD_LCM
43 # if defined(MIN_VERSION_integer_gmp)
44 import GHC.Integer.GMP.Internals
45 # else
46 # error unsupported OPTIMISE_INTEGER_GCD_LCM configuration
47 # endif
48 #endif
49
50 infixr 8 ^, ^^
51 infixl 7 /, `quot`, `rem`, `div`, `mod`
52 infixl 7 %
53
54 default () -- Double isn't available yet,
55 -- and we shouldn't be using defaults anyway
56
57 ------------------------------------------------------------------------
58 -- Divide by zero and arithmetic overflow
59 ------------------------------------------------------------------------
60
61 -- We put them here because they are needed relatively early
62 -- in the libraries before the Exception type has been defined yet.
63
64 {-# NOINLINE divZeroError #-}
65 divZeroError :: a
66 divZeroError = raise# divZeroException
67
68 {-# NOINLINE ratioZeroDenominatorError #-}
69 ratioZeroDenominatorError :: a
70 ratioZeroDenominatorError = raise# ratioZeroDenomException
71
72 {-# NOINLINE overflowError #-}
73 overflowError :: a
74 overflowError = raise# overflowException
75
76 --------------------------------------------------------------
77 -- The Ratio and Rational types
78 --------------------------------------------------------------
79
80 -- | Rational numbers, with numerator and denominator of some 'Integral' type.
81 data Ratio a = !a :% !a deriving (Eq)
82
83 -- | Arbitrary-precision rational numbers, represented as a ratio of
84 -- two 'Integer' values. A rational number may be constructed using
85 -- the '%' operator.
86 type Rational = Ratio Integer
87
88 ratioPrec, ratioPrec1 :: Int
89 ratioPrec = 7 -- Precedence of ':%' constructor
90 ratioPrec1 = ratioPrec + 1
91
92 infinity, notANumber :: Rational
93 infinity = 1 :% 0
94 notANumber = 0 :% 0
95
96 -- Use :%, not % for Inf/NaN; the latter would
97 -- immediately lead to a runtime error, because it normalises.
98
99 -- | Forms the ratio of two integral numbers.
100 {-# SPECIALISE (%) :: Integer -> Integer -> Rational #-}
101 (%) :: (Integral a) => a -> a -> Ratio a
102
103 -- | Extract the numerator of the ratio in reduced form:
104 -- the numerator and denominator have no common factor and the denominator
105 -- is positive.
106 numerator :: (Integral a) => Ratio a -> a
107
108 -- | Extract the denominator of the ratio in reduced form:
109 -- the numerator and denominator have no common factor and the denominator
110 -- is positive.
111 denominator :: (Integral a) => Ratio a -> a
112
113
114 -- | 'reduce' is a subsidiary function used only in this module.
115 -- It normalises a ratio by dividing both numerator and denominator by
116 -- their greatest common divisor.
117 reduce :: (Integral a) => a -> a -> Ratio a
118 {-# SPECIALISE reduce :: Integer -> Integer -> Rational #-}
119 reduce _ 0 = ratioZeroDenominatorError
120 reduce x y = (x `quot` d) :% (y `quot` d)
121 where d = gcd x y
122
123 x % y = reduce (x * signum y) (abs y)
124
125 numerator (x :% _) = x
126 denominator (_ :% y) = y
127
128 --------------------------------------------------------------
129 -- Standard numeric classes
130 --------------------------------------------------------------
131
132 class (Num a, Ord a) => Real a where
133 -- | the rational equivalent of its real argument with full precision
134 toRational :: a -> Rational
135
136 -- | Integral numbers, supporting integer division.
137 class (Real a, Enum a) => Integral a where
138 -- | integer division truncated toward zero
139 quot :: a -> a -> a
140 -- | integer remainder, satisfying
141 --
142 -- > (x `quot` y)*y + (x `rem` y) == x
143 rem :: a -> a -> a
144 -- | integer division truncated toward negative infinity
145 div :: a -> a -> a
146 -- | integer modulus, satisfying
147 --
148 -- > (x `div` y)*y + (x `mod` y) == x
149 mod :: a -> a -> a
150 -- | simultaneous 'quot' and 'rem'
151 quotRem :: a -> a -> (a,a)
152 -- | simultaneous 'div' and 'mod'
153 divMod :: a -> a -> (a,a)
154 -- | conversion to 'Integer'
155 toInteger :: a -> Integer
156
157 {-# INLINE quot #-}
158 {-# INLINE rem #-}
159 {-# INLINE div #-}
160 {-# INLINE mod #-}
161 n `quot` d = q where (q,_) = quotRem n d
162 n `rem` d = r where (_,r) = quotRem n d
163 n `div` d = q where (q,_) = divMod n d
164 n `mod` d = r where (_,r) = divMod n d
165
166 divMod n d = if signum r == negate (signum d) then (q-1, r+d) else qr
167 where qr@(q,r) = quotRem n d
168
169 -- | Fractional numbers, supporting real division.
170 class (Num a) => Fractional a where
171 {-# MINIMAL fromRational, (recip | (/)) #-}
172
173 -- | fractional division
174 (/) :: a -> a -> a
175 -- | reciprocal fraction
176 recip :: a -> a
177 -- | Conversion from a 'Rational' (that is @'Ratio' 'Integer'@).
178 -- A floating literal stands for an application of 'fromRational'
179 -- to a value of type 'Rational', so such literals have type
180 -- @('Fractional' a) => a@.
181 fromRational :: Rational -> a
182
183 {-# INLINE recip #-}
184 {-# INLINE (/) #-}
185 recip x = 1 / x
186 x / y = x * recip y
187
188 -- | Extracting components of fractions.
189 class (Real a, Fractional a) => RealFrac a where
190 -- | The function 'properFraction' takes a real fractional number @x@
191 -- and returns a pair @(n,f)@ such that @x = n+f@, and:
192 --
193 -- * @n@ is an integral number with the same sign as @x@; and
194 --
195 -- * @f@ is a fraction with the same type and sign as @x@,
196 -- and with absolute value less than @1@.
197 --
198 -- The default definitions of the 'ceiling', 'floor', 'truncate'
199 -- and 'round' functions are in terms of 'properFraction'.
200 properFraction :: (Integral b) => a -> (b,a)
201 -- | @'truncate' x@ returns the integer nearest @x@ between zero and @x@
202 truncate :: (Integral b) => a -> b
203 -- | @'round' x@ returns the nearest integer to @x@;
204 -- the even integer if @x@ is equidistant between two integers
205 round :: (Integral b) => a -> b
206 -- | @'ceiling' x@ returns the least integer not less than @x@
207 ceiling :: (Integral b) => a -> b
208 -- | @'floor' x@ returns the greatest integer not greater than @x@
209 floor :: (Integral b) => a -> b
210
211 {-# INLINE truncate #-}
212 truncate x = m where (m,_) = properFraction x
213
214 round x = let (n,r) = properFraction x
215 m = if r < 0 then n - 1 else n + 1
216 in case signum (abs r - 0.5) of
217 -1 -> n
218 0 -> if even n then n else m
219 1 -> m
220 _ -> error "round default defn: Bad value"
221
222 ceiling x = if r > 0 then n + 1 else n
223 where (n,r) = properFraction x
224
225 floor x = if r < 0 then n - 1 else n
226 where (n,r) = properFraction x
227
228 -- These 'numeric' enumerations come straight from the Report
229
230 numericEnumFrom :: (Fractional a) => a -> [a]
231 numericEnumFrom n = n `seq` (n : numericEnumFrom (n + 1))
232
233 numericEnumFromThen :: (Fractional a) => a -> a -> [a]
234 numericEnumFromThen n m = n `seq` m `seq` (n : numericEnumFromThen m (m+m-n))
235
236 numericEnumFromTo :: (Ord a, Fractional a) => a -> a -> [a]
237 numericEnumFromTo n m = takeWhile (<= m + 1/2) (numericEnumFrom n)
238
239 numericEnumFromThenTo :: (Ord a, Fractional a) => a -> a -> a -> [a]
240 numericEnumFromThenTo e1 e2 e3
241 = takeWhile predicate (numericEnumFromThen e1 e2)
242 where
243 mid = (e2 - e1) / 2
244 predicate | e2 >= e1 = (<= e3 + mid)
245 | otherwise = (>= e3 + mid)
246
247 --------------------------------------------------------------
248 -- Instances for Int
249 --------------------------------------------------------------
250
251 instance Real Int where
252 toRational x = toInteger x :% 1
253
254 instance Integral Int where
255 toInteger (I# i) = smallInteger i
256
257 a `quot` b
258 | b == 0 = divZeroError
259 | b == (-1) && a == minBound = overflowError -- Note [Order of tests]
260 -- in GHC.Int
261 | otherwise = a `quotInt` b
262
263 a `rem` b
264 | b == 0 = divZeroError
265 -- The quotRem CPU instruction fails for minBound `quotRem` -1,
266 -- but minBound `rem` -1 is well-defined (0). We therefore
267 -- special-case it.
268 | b == (-1) = 0
269 | otherwise = a `remInt` b
270
271 a `div` b
272 | b == 0 = divZeroError
273 | b == (-1) && a == minBound = overflowError -- Note [Order of tests]
274 -- in GHC.Int
275 | otherwise = a `divInt` b
276
277 a `mod` b
278 | b == 0 = divZeroError
279 -- The divMod CPU instruction fails for minBound `divMod` -1,
280 -- but minBound `mod` -1 is well-defined (0). We therefore
281 -- special-case it.
282 | b == (-1) = 0
283 | otherwise = a `modInt` b
284
285 a `quotRem` b
286 | b == 0 = divZeroError
287 -- Note [Order of tests] in GHC.Int
288 | b == (-1) && a == minBound = (overflowError, 0)
289 | otherwise = a `quotRemInt` b
290
291 a `divMod` b
292 | b == 0 = divZeroError
293 -- Note [Order of tests] in GHC.Int
294 | b == (-1) && a == minBound = (overflowError, 0)
295 | otherwise = a `divModInt` b
296
297 --------------------------------------------------------------
298 -- Instances for @Word@
299 --------------------------------------------------------------
300
301 instance Real Word where
302 toRational x = toInteger x % 1
303
304 instance Integral Word where
305 quot (W# x#) y@(W# y#)
306 | y /= 0 = W# (x# `quotWord#` y#)
307 | otherwise = divZeroError
308 rem (W# x#) y@(W# y#)
309 | y /= 0 = W# (x# `remWord#` y#)
310 | otherwise = divZeroError
311 div (W# x#) y@(W# y#)
312 | y /= 0 = W# (x# `quotWord#` y#)
313 | otherwise = divZeroError
314 mod (W# x#) y@(W# y#)
315 | y /= 0 = W# (x# `remWord#` y#)
316 | otherwise = divZeroError
317 quotRem (W# x#) y@(W# y#)
318 | y /= 0 = case x# `quotRemWord#` y# of
319 (# q, r #) ->
320 (W# q, W# r)
321 | otherwise = divZeroError
322 divMod (W# x#) y@(W# y#)
323 | y /= 0 = (W# (x# `quotWord#` y#), W# (x# `remWord#` y#))
324 | otherwise = divZeroError
325 toInteger (W# x#) = wordToInteger x#
326
327 --------------------------------------------------------------
328 -- Instances for Integer
329 --------------------------------------------------------------
330
331 instance Real Integer where
332 toRational x = x :% 1
333
334 -- Note [Integer division constant folding]
335 -- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
336 --
337 -- Constant folding of quot, rem, div, mod, divMod and quotRem for
338 -- Integer arguments depends crucially on inlining. Constant folding
339 -- rules defined in compiler/prelude/PrelRules.lhs trigger for
340 -- quotInteger, remInteger and so on. So if calls to quot, rem and so on
341 -- were not inlined the rules would not fire. The rules would also not
342 -- fire if calls to quotInteger and so on were inlined, but this does not
343 -- happen because they are all marked with NOINLINE pragma - see documentation
344 -- of integer-gmp or integer-simple.
345
346 instance Integral Integer where
347 toInteger n = n
348
349 {-# INLINE quot #-}
350 _ `quot` 0 = divZeroError
351 n `quot` d = n `quotInteger` d
352
353 {-# INLINE rem #-}
354 _ `rem` 0 = divZeroError
355 n `rem` d = n `remInteger` d
356
357 {-# INLINE div #-}
358 _ `div` 0 = divZeroError
359 n `div` d = n `divInteger` d
360
361 {-# INLINE mod #-}
362 _ `mod` 0 = divZeroError
363 n `mod` d = n `modInteger` d
364
365 {-# INLINE divMod #-}
366 _ `divMod` 0 = divZeroError
367 n `divMod` d = case n `divModInteger` d of
368 (# x, y #) -> (x, y)
369
370 {-# INLINE quotRem #-}
371 _ `quotRem` 0 = divZeroError
372 n `quotRem` d = case n `quotRemInteger` d of
373 (# q, r #) -> (q, r)
374
375 --------------------------------------------------------------
376 -- Instances for @Ratio@
377 --------------------------------------------------------------
378
379 instance (Integral a) => Ord (Ratio a) where
380 {-# SPECIALIZE instance Ord Rational #-}
381 (x:%y) <= (x':%y') = x * y' <= x' * y
382 (x:%y) < (x':%y') = x * y' < x' * y
383
384 instance (Integral a) => Num (Ratio a) where
385 {-# SPECIALIZE instance Num Rational #-}
386 (x:%y) + (x':%y') = reduce (x*y' + x'*y) (y*y')
387 (x:%y) - (x':%y') = reduce (x*y' - x'*y) (y*y')
388 (x:%y) * (x':%y') = reduce (x * x') (y * y')
389 negate (x:%y) = (-x) :% y
390 abs (x:%y) = abs x :% y
391 signum (x:%_) = signum x :% 1
392 fromInteger x = fromInteger x :% 1
393
394 {-# RULES "fromRational/id" fromRational = id :: Rational -> Rational #-}
395 instance (Integral a) => Fractional (Ratio a) where
396 {-# SPECIALIZE instance Fractional Rational #-}
397 (x:%y) / (x':%y') = (x*y') % (y*x')
398 recip (0:%_) = ratioZeroDenominatorError
399 recip (x:%y)
400 | x < 0 = negate y :% negate x
401 | otherwise = y :% x
402 fromRational (x:%y) = fromInteger x % fromInteger y
403
404 instance (Integral a) => Real (Ratio a) where
405 {-# SPECIALIZE instance Real Rational #-}
406 toRational (x:%y) = toInteger x :% toInteger y
407
408 instance (Integral a) => RealFrac (Ratio a) where
409 {-# SPECIALIZE instance RealFrac Rational #-}
410 properFraction (x:%y) = (fromInteger (toInteger q), r:%y)
411 where (q,r) = quotRem x y
412
413 instance (Integral a, Show a) => Show (Ratio a) where
414 {-# SPECIALIZE instance Show Rational #-}
415 showsPrec p (x:%y) = showParen (p > ratioPrec) $
416 showsPrec ratioPrec1 x .
417 showString " % " .
418 -- H98 report has spaces round the %
419 -- but we removed them [May 04]
420 -- and added them again for consistency with
421 -- Haskell 98 [Sep 08, #1920]
422 showsPrec ratioPrec1 y
423
424 instance (Integral a) => Enum (Ratio a) where
425 {-# SPECIALIZE instance Enum Rational #-}
426 succ x = x + 1
427 pred x = x - 1
428
429 toEnum n = fromIntegral n :% 1
430 fromEnum = fromInteger . truncate
431
432 enumFrom = numericEnumFrom
433 enumFromThen = numericEnumFromThen
434 enumFromTo = numericEnumFromTo
435 enumFromThenTo = numericEnumFromThenTo
436
437 --------------------------------------------------------------
438 -- Coercions
439 --------------------------------------------------------------
440
441 -- | general coercion from integral types
442 {-# NOINLINE [1] fromIntegral #-}
443 fromIntegral :: (Integral a, Num b) => a -> b
444 fromIntegral = fromInteger . toInteger
445
446 {-# RULES
447 "fromIntegral/Int->Int" fromIntegral = id :: Int -> Int
448 #-}
449
450 {-# RULES
451 "fromIntegral/Int->Word" fromIntegral = \(I# x#) -> W# (int2Word# x#)
452 "fromIntegral/Word->Int" fromIntegral = \(W# x#) -> I# (word2Int# x#)
453 "fromIntegral/Word->Word" fromIntegral = id :: Word -> Word
454 #-}
455
456 -- | general coercion to fractional types
457 realToFrac :: (Real a, Fractional b) => a -> b
458 {-# NOINLINE [1] realToFrac #-}
459 realToFrac = fromRational . toRational
460
461 --------------------------------------------------------------
462 -- Overloaded numeric functions
463 --------------------------------------------------------------
464
465 -- | Converts a possibly-negative 'Real' value to a string.
466 showSigned :: (Real a)
467 => (a -> ShowS) -- ^ a function that can show unsigned values
468 -> Int -- ^ the precedence of the enclosing context
469 -> a -- ^ the value to show
470 -> ShowS
471 showSigned showPos p x
472 | x < 0 = showParen (p > 6) (showChar '-' . showPos (-x))
473 | otherwise = showPos x
474
475 even, odd :: (Integral a) => a -> Bool
476 even n = n `rem` 2 == 0
477 odd = not . even
478 {-# SPECIALISE even :: Int -> Bool #-}
479 {-# SPECIALISE odd :: Int -> Bool #-}
480 {-# SPECIALISE even :: Integer -> Bool #-}
481 {-# SPECIALISE odd :: Integer -> Bool #-}
482
483 -------------------------------------------------------
484 -- | raise a number to a non-negative integral power
485 {-# SPECIALISE [1] (^) ::
486 Integer -> Integer -> Integer,
487 Integer -> Int -> Integer,
488 Int -> Int -> Int #-}
489 {-# INLINABLE [1] (^) #-} -- See Note [Inlining (^)]
490 (^) :: (Num a, Integral b) => a -> b -> a
491 x0 ^ y0 | y0 < 0 = error "Negative exponent"
492 | y0 == 0 = 1
493 | otherwise = f x0 y0
494 where -- f : x0 ^ y0 = x ^ y
495 f x y | even y = f (x * x) (y `quot` 2)
496 | y == 1 = x
497 | otherwise = g (x * x) ((y - 1) `quot` 2) x
498 -- g : x0 ^ y0 = (x ^ y) * z
499 g x y z | even y = g (x * x) (y `quot` 2) z
500 | y == 1 = x * z
501 | otherwise = g (x * x) ((y - 1) `quot` 2) (x * z)
502
503 -- | raise a number to an integral power
504 (^^) :: (Fractional a, Integral b) => a -> b -> a
505 {-# INLINABLE [1] (^^) #-} -- See Note [Inlining (^)
506 x ^^ n = if n >= 0 then x^n else recip (x^(negate n))
507
508 {- Note [Inlining (^)
509 ~~~~~~~~~~~~~~~~~~~~~
510 The INLINABLE pragma allows (^) to be specialised at its call sites.
511 If it is called repeatedly at the same type, that can make a huge
512 difference, because of those constants which can be repeatedly
513 calculated.
514
515 Currently the fromInteger calls are not floated because we get
516 \d1 d2 x y -> blah
517 after the gentle round of simplification. -}
518
519 {- Rules for powers with known small exponent
520 see #5237
521 For small exponents, (^) is inefficient compared to manually
522 expanding the multiplication tree.
523 Here, rules for the most common exponent types are given.
524 The range of exponents for which rules are given is quite
525 arbitrary and kept small to not unduly increase the number of rules.
526 0 and 1 are excluded based on the assumption that nobody would
527 write x^0 or x^1 in code and the cases where an exponent could
528 be statically resolved to 0 or 1 are rare.
529
530 It might be desirable to have corresponding rules also for
531 exponents of other types, in particular Word, but we can't
532 have those rules here (importing GHC.Word or GHC.Int would
533 create a cyclic module dependency), and it's doubtful they
534 would fire, since the exponents of other types tend to get
535 floated out before the rule has a chance to fire.
536
537 Also desirable would be rules for (^^), but I haven't managed
538 to get those to fire.
539
540 Note: Trying to save multiplications by sharing the square for
541 exponents 4 and 5 does not save time, indeed, for Double, it is
542 up to twice slower, so the rules contain flat sequences of
543 multiplications.
544 -}
545
546 {-# RULES
547 "^2/Int" forall x. x ^ (2 :: Int) = let u = x in u*u
548 "^3/Int" forall x. x ^ (3 :: Int) = let u = x in u*u*u
549 "^4/Int" forall x. x ^ (4 :: Int) = let u = x in u*u*u*u
550 "^5/Int" forall x. x ^ (5 :: Int) = let u = x in u*u*u*u*u
551 "^2/Integer" forall x. x ^ (2 :: Integer) = let u = x in u*u
552 "^3/Integer" forall x. x ^ (3 :: Integer) = let u = x in u*u*u
553 "^4/Integer" forall x. x ^ (4 :: Integer) = let u = x in u*u*u*u
554 "^5/Integer" forall x. x ^ (5 :: Integer) = let u = x in u*u*u*u*u
555 #-}
556
557 -------------------------------------------------------
558 -- Special power functions for Rational
559 --
560 -- see #4337
561 --
562 -- Rationale:
563 -- For a legitimate Rational (n :% d), the numerator and denominator are
564 -- coprime, i.e. they have no common prime factor.
565 -- Therefore all powers (n ^ a) and (d ^ b) are also coprime, so it is
566 -- not necessary to compute the greatest common divisor, which would be
567 -- done in the default implementation at each multiplication step.
568 -- Since exponentiation quickly leads to very large numbers and
569 -- calculation of gcds is generally very slow for large numbers,
570 -- avoiding the gcd leads to an order of magnitude speedup relatively
571 -- soon (and an asymptotic improvement overall).
572 --
573 -- Note:
574 -- We cannot use these functions for general Ratio a because that would
575 -- change results in a multitude of cases.
576 -- The cause is that if a and b are coprime, their remainders by any
577 -- positive modulus generally aren't, so in the default implementation
578 -- reduction occurs.
579 --
580 -- Example:
581 -- (17 % 3) ^ 3 :: Ratio Word8
582 -- Default:
583 -- (17 % 3) ^ 3 = ((17 % 3) ^ 2) * (17 % 3)
584 -- = ((289 `mod` 256) % 9) * (17 % 3)
585 -- = (33 % 9) * (17 % 3)
586 -- = (11 % 3) * (17 % 3)
587 -- = (187 % 9)
588 -- But:
589 -- ((17^3) `mod` 256) % (3^3) = (4913 `mod` 256) % 27
590 -- = 49 % 27
591 --
592 -- TODO:
593 -- Find out whether special-casing for numerator, denominator or
594 -- exponent = 1 (or -1, where that may apply) gains something.
595
596 -- Special version of (^) for Rational base
597 {-# RULES "(^)/Rational" (^) = (^%^) #-}
598 (^%^) :: Integral a => Rational -> a -> Rational
599 (n :% d) ^%^ e
600 | e < 0 = error "Negative exponent"
601 | e == 0 = 1 :% 1
602 | otherwise = (n ^ e) :% (d ^ e)
603
604 -- Special version of (^^) for Rational base
605 {-# RULES "(^^)/Rational" (^^) = (^^%^^) #-}
606 (^^%^^) :: Integral a => Rational -> a -> Rational
607 (n :% d) ^^%^^ e
608 | e > 0 = (n ^ e) :% (d ^ e)
609 | e == 0 = 1 :% 1
610 | n > 0 = (d ^ (negate e)) :% (n ^ (negate e))
611 | n == 0 = ratioZeroDenominatorError
612 | otherwise = let nn = d ^ (negate e)
613 dd = (negate n) ^ (negate e)
614 in if even e then (nn :% dd) else (negate nn :% dd)
615
616 -------------------------------------------------------
617 -- | @'gcd' x y@ is the non-negative factor of both @x@ and @y@ of which
618 -- every common factor of @x@ and @y@ is also a factor; for example
619 -- @'gcd' 4 2 = 2@, @'gcd' (-4) 6 = 2@, @'gcd' 0 4@ = @4@. @'gcd' 0 0@ = @0@.
620 -- (That is, the common divisor that is \"greatest\" in the divisibility
621 -- preordering.)
622 --
623 -- Note: Since for signed fixed-width integer types, @'abs' 'minBound' < 0@,
624 -- the result may be negative if one of the arguments is @'minBound'@ (and
625 -- necessarily is if the other is @0@ or @'minBound'@) for such types.
626 gcd :: (Integral a) => a -> a -> a
627 {-# NOINLINE [1] gcd #-}
628 gcd x y = gcd' (abs x) (abs y)
629 where gcd' a 0 = a
630 gcd' a b = gcd' b (a `rem` b)
631
632 -- | @'lcm' x y@ is the smallest positive integer that both @x@ and @y@ divide.
633 lcm :: (Integral a) => a -> a -> a
634 {-# SPECIALISE lcm :: Int -> Int -> Int #-}
635 {-# NOINLINE [1] lcm #-}
636 lcm _ 0 = 0
637 lcm 0 _ = 0
638 lcm x y = abs ((x `quot` (gcd x y)) * y)
639
640 #ifdef OPTIMISE_INTEGER_GCD_LCM
641 {-# RULES
642 "gcd/Int->Int->Int" gcd = gcdInt'
643 "gcd/Integer->Integer->Integer" gcd = gcdInteger
644 "lcm/Integer->Integer->Integer" lcm = lcmInteger
645 #-}
646
647 gcdInt' :: Int -> Int -> Int
648 gcdInt' (I# x) (I# y) = I# (gcdInt x y)
649
650 #if MIN_VERSION_integer_gmp(1,0,0)
651 {-# RULES
652 "gcd/Word->Word->Word" gcd = gcdWord'
653 #-}
654
655 gcdWord' :: Word -> Word -> Word
656 gcdWord' (W# x) (W# y) = W# (gcdWord x y)
657 #endif
658 #endif
659
660 integralEnumFrom :: (Integral a, Bounded a) => a -> [a]
661 integralEnumFrom n = map fromInteger [toInteger n .. toInteger (maxBound `asTypeOf` n)]
662
663 integralEnumFromThen :: (Integral a, Bounded a) => a -> a -> [a]
664 integralEnumFromThen n1 n2
665 | i_n2 >= i_n1 = map fromInteger [i_n1, i_n2 .. toInteger (maxBound `asTypeOf` n1)]
666 | otherwise = map fromInteger [i_n1, i_n2 .. toInteger (minBound `asTypeOf` n1)]
667 where
668 i_n1 = toInteger n1
669 i_n2 = toInteger n2
670
671 integralEnumFromTo :: Integral a => a -> a -> [a]
672 integralEnumFromTo n m = map fromInteger [toInteger n .. toInteger m]
673
674 integralEnumFromThenTo :: Integral a => a -> a -> a -> [a]
675 integralEnumFromThenTo n1 n2 m
676 = map fromInteger [toInteger n1, toInteger n2 .. toInteger m]