[project @ 2001-04-11 10:41:46 by sewardj]
[ghc-hetmet.git] / ghc / lib / std / Ratio.lhs
1 % ------------------------------------------------------------------------------
2 % $Id: Ratio.lhs,v 1.7 2000/06/30 13:39:36 simonmar Exp $
3 %
4 % (c) The University of Glasgow, 1994-2000
5 %
6
7 \section[Ratio]{Module @Ratio@}
8
9 Standard functions on rational numbers
10
11 \begin{code}
12 module  Ratio
13     ( Ratio
14     , Rational
15     , (%)               -- :: (Integral a) => a -> a -> Ratio a
16     , numerator         -- :: (Integral a) => Ratio a -> a
17     , denominator       -- :: (Integral a) => Ratio a -> a
18     , approxRational    -- :: (RealFrac a) => a -> a -> Rational
19
20     -- Ratio instances: 
21     --   (Integral a) => Eq   (Ratio a)
22     --   (Integral a) => Ord  (Ratio a)
23     --   (Integral a) => Num  (Ratio a)
24     --   (Integral a) => Real (Ratio a)
25     --   (Integral a) => Fractional (Ratio a)
26     --   (Integral a) => RealFrac (Ratio a)
27     --   (Integral a) => Enum     (Ratio a)
28     --   (Read a, Integral a) => Read (Ratio a)
29     --   (Integral a) => Show     (Ratio a)
30     --
31     -- Implementation checked wrt. Haskell 98 lib report, 1/99.
32
33   ) where
34 \end{code}
35
36
37 #ifndef __HUGS__
38
39 \begin{code}
40 import Prelude          -- To generate the dependencies
41 import PrelReal         -- The basic defns for Ratio
42 \end{code}
43
44 %*********************************************************
45 %*                                                      *
46 \subsection{approxRational}
47 %*                                                      *
48 %*********************************************************
49
50 @approxRational@, applied to two real fractional numbers x and epsilon,
51 returns the simplest rational number within epsilon of x.  A rational
52 number n%d in reduced form is said to be simpler than another n'%d' if
53 abs n <= abs n' && d <= d'.  Any real interval contains a unique
54 simplest rational; here, for simplicity, we assume a closed rational
55 interval.  If such an interval includes at least one whole number, then
56 the simplest rational is the absolutely least whole number.  Otherwise,
57 the bounds are of the form q%1 + r%d and q%1 + r'%d', where abs r < d
58 and abs r' < d', and the simplest rational is q%1 + the reciprocal of
59 the simplest rational between d'%r' and d%r.
60
61 \begin{code}
62 approxRational          :: (RealFrac a) => a -> a -> Rational
63 approxRational rat eps  =  simplest (rat-eps) (rat+eps)
64         where simplest x y | y < x      =  simplest y x
65                            | x == y     =  xr
66                            | x > 0      =  simplest' n d n' d'
67                            | y < 0      =  - simplest' (-n') d' (-n) d
68                            | otherwise  =  0 :% 1
69                                         where xr  = toRational x
70                                               n   = numerator xr
71                                               d   = denominator xr
72                                               nd' = toRational y
73                                               n'  = numerator nd'
74                                               d'  = denominator nd'
75
76               simplest' n d n' d'       -- assumes 0 < n%d < n'%d'
77                         | r == 0     =  q :% 1
78                         | q /= q'    =  (q+1) :% 1
79                         | otherwise  =  (q*n''+d'') :% n''
80                                      where (q,r)      =  quotRem n d
81                                            (q',r')    =  quotRem n' d'
82                                            nd''       =  simplest' d' r' d r
83                                            n''        =  numerator nd''
84                                            d''        =  denominator nd''
85
86 \end{code}
87
88 #else
89
90 \begin{code}
91 -- Hugs already has this functionally inside its prelude
92 \end{code}
93
94 #endif
95
96
97