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