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