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