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