Remove Control.Parallel*, now in package parallel
[packages/random.git] / Data / Ratio.hs
1 -----------------------------------------------------------------------------
2 -- |
3 -- Module : Data.Ratio
4 -- Copyright : (c) The University of Glasgow 2001
5 -- License : BSD-style (see the file libraries/base/LICENSE)
6 --
7 -- Maintainer : libraries@haskell.org
8 -- Stability : stable
9 -- Portability : portable
10 --
11 -- Standard functions on rational numbers
12 --
13 -----------------------------------------------------------------------------
14
15 module Data.Ratio
16 ( Ratio
17 , Rational
18 , (%) -- :: (Integral a) => a -> a -> Ratio a
19 , numerator -- :: (Integral a) => Ratio a -> a
20 , denominator -- :: (Integral a) => Ratio a -> a
21 , approxRational -- :: (RealFrac a) => a -> a -> Rational
22
23 -- Ratio instances:
24 -- (Integral a) => Eq (Ratio a)
25 -- (Integral a) => Ord (Ratio a)
26 -- (Integral a) => Num (Ratio a)
27 -- (Integral a) => Real (Ratio a)
28 -- (Integral a) => Fractional (Ratio a)
29 -- (Integral a) => RealFrac (Ratio a)
30 -- (Integral a) => Enum (Ratio a)
31 -- (Read a, Integral a) => Read (Ratio a)
32 -- (Integral a) => Show (Ratio a)
33
34 ) where
35
36 import Prelude
37
38 #ifdef __GLASGOW_HASKELL__
39 import GHC.Real -- The basic defns for Ratio
40 #endif
41
42 #ifdef __HUGS__
43 import Hugs.Prelude(Ratio(..), (%), numerator, denominator)
44 #endif
45
46 #ifdef __NHC__
47 import Ratio (Ratio(..), (%), numerator, denominator, approxRational)
48 #else
49
50 -- -----------------------------------------------------------------------------
51 -- approxRational
52
53 -- | 'approxRational', applied to two real fractional numbers @x@ and @epsilon@,
54 -- returns the simplest rational number within @epsilon@ of @x@.
55 -- A rational number @y@ is said to be /simpler/ than another @y'@ if
56 --
57 -- * @'abs' ('numerator' y) <= 'abs' ('numerator' y')@, and
58 --
59 -- * @'denominator' y <= 'denominator' y'@.
60 --
61 -- Any real interval contains a unique simplest rational;
62 -- in particular, note that @0\/1@ is the simplest rational of all.
63
64 -- Implementation details: Here, for simplicity, we assume a closed rational
65 -- interval. If such an interval includes at least one whole number, then
66 -- the simplest rational is the absolutely least whole number. Otherwise,
67 -- the bounds are of the form q%1 + r%d and q%1 + r'%d', where abs r < d
68 -- and abs r' < d', and the simplest rational is q%1 + the reciprocal of
69 -- the simplest rational between d'%r' and d%r.
70
71 approxRational :: (RealFrac a) => a -> a -> Rational
72 approxRational rat eps = simplest (rat-eps) (rat+eps)
73 where simplest x y | y < x = simplest y x
74 | x == y = xr
75 | x > 0 = simplest' n d n' d'
76 | y < 0 = - simplest' (-n') d' (-n) d
77 | otherwise = 0 :% 1
78 where xr = toRational x
79 n = numerator xr
80 d = denominator xr
81 nd' = toRational y
82 n' = numerator nd'
83 d' = denominator nd'
84
85 simplest' n d n' d' -- assumes 0 < n%d < n'%d'
86 | r == 0 = q :% 1
87 | q /= q' = (q+1) :% 1
88 | otherwise = (q*n''+d'') :% n''
89 where (q,r) = quotRem n d
90 (q',r') = quotRem n' d'
91 nd'' = simplest' d' r' d r
92 n'' = numerator nd''
93 d'' = denominator nd''
94 #endif