Prime -> 2010
[haskell-report.git] / report / lib-code / Ratio.hs
1 -- Standard functions on rational numbers
2
3 module Ratio (
4 Ratio, Rational, (%), numerator, denominator, approxRational ) where
5
6 infixl 7 %
7
8 ratPrec = 7 :: Int
9
10 data (Integral a) => Ratio a = !a :% !a deriving (Eq)
11 type Rational = Ratio Integer
12
13 (%) :: (Integral a) => a -> a -> Ratio a
14 numerator, denominator :: (Integral a) => Ratio a -> a
15 approxRational :: (RealFrac a) => a -> a -> Rational
16
17
18 -- "reduce" is a subsidiary function used only in this module.
19 -- It normalises a ratio by dividing both numerator
20 -- and denominator by their greatest common divisor.
21 --
22 -- E.g., 12 `reduce` 8 == 3 :% 2
23 -- 12 `reduce` (-8) == 3 :% (-2)
24
25 reduce _ 0 = error "Ratio.% : zero denominator"
26 reduce x y = (x `quot` d) :% (y `quot` d)
27 where d = gcd x y
28
29 x % y = reduce (x * signum y) (abs y)
30
31 numerator (x :% _) = x
32
33 denominator (_ :% y) = y
34
35
36 instance (Integral a) => Ord (Ratio a) where
37 (x:%y) <= (x':%y') = x * y' <= x' * y
38 (x:%y) < (x':%y') = x * y' < x' * y
39
40 instance (Integral a) => Num (Ratio a) where
41 (x:%y) + (x':%y') = reduce (x*y' + x'*y) (y*y')
42 (x:%y) * (x':%y') = reduce (x * x') (y * y')
43 negate (x:%y) = (-x) :% y
44 abs (x:%y) = abs x :% y
45 signum (x:%y) = signum x :% 1
46 fromInteger x = fromInteger x :% 1
47
48 instance (Integral a) => Real (Ratio a) where
49 toRational (x:%y) = toInteger x :% toInteger y
50
51 instance (Integral a) => Fractional (Ratio a) where
52 (x:%y) / (x':%y') = (x*y') % (y*x')
53 recip (x:%y) = y % x
54 fromRational (x:%y) = fromInteger x :% fromInteger y
55
56 instance (Integral a) => RealFrac (Ratio a) where
57 properFraction (x:%y) = (fromIntegral q, r:%y)
58 where (q,r) = quotRem x y
59
60 instance (Integral a) => Enum (Ratio a) where
61 succ x = x+1
62 pred x = x-1
63 toEnum = fromIntegral
64 fromEnum = fromInteger . truncate -- May overflow
65 enumFrom = numericEnumFrom -- These numericEnumXXX functions
66 enumFromThen = numericEnumFromThen -- are as defined in Prelude.hs
67 enumFromTo = numericEnumFromTo -- but not exported from it!
68 enumFromThenTo = numericEnumFromThenTo
69
70 instance (Read a, Integral a) => Read (Ratio a) where
71 readsPrec p = readParen (p > ratPrec)
72 (\r -> [(x%y,u) | (x,s) <- readsPrec (ratPrec+1) r,
73 ("%",t) <- lex s,
74 (y,u) <- readsPrec (ratPrec+1) t ])
75
76 instance (Integral a) => Show (Ratio a) where
77 showsPrec p (x:%y) = showParen (p > ratPrec)
78 (showsPrec (ratPrec+1) x .
79 showString " % " .
80 showsPrec (ratPrec+1) y)
81
82
83
84 approxRational x eps = simplest (x-eps) (x+eps)
85 where simplest x y | y < x = simplest y x
86 | x == y = xr
87 | x > 0 = simplest' n d n' d'
88 | y < 0 = - simplest' (-n') d' (-n) d
89 | otherwise = 0 :% 1
90 where xr@(n:%d) = toRational x
91 (n':%d') = toRational y
92
93 simplest' n d n' d' -- assumes 0 < n%d < n'%d'
94 | r == 0 = q :% 1
95 | q /= q' = (q+1) :% 1
96 | otherwise = (q*n''+d'') :% n''
97 where (q,r) = quotRem n d
98 (q',r') = quotRem n' d'
99 (n'':%d'') = simplest' d' r' d r