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/core/LICENSE)
   6 --
   7 -- Maintainer  :  libraries@haskell.org
   8 -- Stability   :  provisional
   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 -- -----------------------------------------------------------------------------
  43 -- approxRational
  44
  45 -- @approxRational@, applied to two real fractional numbers x and epsilon,
  46 -- returns the simplest rational number within epsilon of x.  A rational
  47 -- number n%d in reduced form is said to be simpler than another n'%d' if
  48 -- abs n <= abs n' && d <= d'.  Any real interval contains a unique
  49 -- simplest rational; here, for simplicity, we assume a closed rational
  50 -- interval.  If such an interval includes at least one whole number, then
  51 -- the simplest rational is the absolutely least whole number.  Otherwise,
  52 -- the bounds are of the form q%1 + r%d and q%1 + r'%d', where abs r < d
  53 -- and abs r' < d', and the simplest rational is q%1 + the reciprocal of
  54 -- the simplest rational between d'%r' and d%r.
  55
  56 approxRational          :: (RealFrac a) => a -> a -> Rational
  57 approxRational rat eps  =  simplest (rat-eps) (rat+eps)
  58         where simplest x y | y < x      =  simplest y x
  59                            | x == y     =  xr
  60                            | x > 0      =  simplest' n d n' d'
  61                            | y < 0      =  - simplest' (-n') d' (-n) d
  62                            | otherwise  =  0 :% 1
  63                                         where xr  = toRational x
  64                                               n   = numerator xr
  65                                               d   = denominator xr
  66                                               nd' = toRational y
  67                                               n'  = numerator nd'
  68                                               d'  = denominator nd'
  69
  70               simplest' n d n' d'       -- assumes 0 < n%d < n'%d'
  71                         | r == 0     =  q :% 1
  72                         | q /= q'    =  (q+1) :% 1
  73                         | otherwise  =  (q*n''+d'') :% n''
  74                                      where (q,r)      =  quotRem n d
  75                                            (q',r')    =  quotRem n' d'
  76                                            nd''       =  simplest' d' r' d r
  77                                            n''        =  numerator nd''
  78                                            d''        =  denominator nd''
  79