ghc/lib/std/Ratio.lhs

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