407 lines
32 KiB
HTML
407 lines
32 KiB
HTML
<?xml version="1.0" encoding="iso-8859-1" ?>
|
|
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN"
|
|
"http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
|
|
<!--http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd-->
|
|
<html xmlns="http://www.w3.org/1999/xhtml"
|
|
>
|
|
<head><title>22 Data.Ratio</title>
|
|
<meta http-equiv="Content-Type" content="text/html; charset=iso-8859-1" />
|
|
<meta name="generator" content="TeX4ht (http://www.cse.ohio-state.edu/~gurari/TeX4ht/)" />
|
|
<meta name="originator" content="TeX4ht (http://www.cse.ohio-state.edu/~gurari/TeX4ht/)" />
|
|
<!-- 2,html,xhtml -->
|
|
<meta name="src" content="haskell.tex" />
|
|
<meta name="date" content="2010-07-20 13:11:00" />
|
|
<link rel="stylesheet" type="text/css" href="haskell.css" />
|
|
</head><body
|
|
>
|
|
<!--l. 1--><div class="crosslinks"><p class="noindent">[<a
|
|
href="haskellch23.html" >next</a>] [<a
|
|
href="haskellch21.html" >prev</a>] [<a
|
|
href="haskellch21.html#tailhaskellch21.html" >prev-tail</a>] [<a
|
|
href="#tailhaskellch22.html">tail</a>] [<a
|
|
href="haskellpa2.html#haskellch22.html" >up</a>] </p></div>
|
|
<h2 class="chapterHead"><span class="titlemark">Chapter 22</span><br /><a
|
|
id="x30-25800022"></a><span
|
|
class="pcrr7t-">Data.Ratio</span></h2>
|
|
<div class="quote">
|
|
|
|
|
|
|
|
<div class="verbatim" id="verbatim-434">
|
|
module Data.Ratio (
|
|
 <br />    Ratio,  Rational,  (%),  numerator,  denominator,  approxRational
|
|
 <br />  ) where
|
|
</div>
|
|
<p class="noindent"></div>
|
|
<dl><dt class="haddockdesc">
|
|
<!--tex4ht:inline--><div class="tabular"> <table id="TBL-374" class="tabular"
|
|
cellspacing="0" cellpadding="0" rules="groups"
|
|
><colgroup id="TBL-374-1g"><col
|
|
id="TBL-374-1" /></colgroup><tr
|
|
style="vertical-align:baseline;" id="TBL-374-1-"><td style="white-space:nowrap; text-align:left;" id="TBL-374-1-1"
|
|
class="td11"><span
|
|
class="pcrb7t-">data</span><span
|
|
class="pcrb7t-"> Integral</span><span
|
|
class="pcrb7t-"> a</span><span
|
|
class="pcrb7t-"> =></span><span
|
|
class="pcrb7t-"> Ratio</span><span
|
|
class="pcrb7t-"> a </span></td>
|
|
</tr></table> </div> <dd class="haddockdesc">
|
|
Rational numbers, with numerator and denominator of some <span
|
|
class="pcrr7t-">Integral</span><a
|
|
id="dx30-258001"></a> type.
|
|
</dl>
|
|
<dl> <dt class="haddockdesc">
|
|
<!--tex4ht:inline--><div class="tabular"> <table id="TBL-375" class="tabular"
|
|
cellspacing="0" cellpadding="0" rules="groups"
|
|
><colgroup id="TBL-375-1g"><col
|
|
id="TBL-375-1" /></colgroup><tr
|
|
style="vertical-align:baseline;" id="TBL-375-1-"><td style="white-space:nowrap; text-align:left;" id="TBL-375-1-1"
|
|
class="td11"><span
|
|
class="pcrb7t-">instance</span><span
|
|
class="pcrb7t-"> Integral</span><span
|
|
class="pcrb7t-"> a</span><span
|
|
class="pcrb7t-"> =></span><span
|
|
class="pcrb7t-"> Enum</span><span
|
|
class="pcrb7t-"> (Ratio</span><span
|
|
class="pcrb7t-"> a) </span></td>
|
|
</tr><tr
|
|
style="vertical-align:baseline;" id="TBL-375-2-"><td style="white-space:nowrap; text-align:left;" id="TBL-375-2-1"
|
|
class="td11"><span
|
|
class="pcrb7t-">instance</span><span
|
|
class="pcrb7t-"> Integral</span><span
|
|
class="pcrb7t-"> a</span><span
|
|
class="pcrb7t-"> =></span><span
|
|
class="pcrb7t-"> Eq</span><span
|
|
class="pcrb7t-"> (Ratio</span><span
|
|
class="pcrb7t-"> a) </span></td>
|
|
</tr><tr
|
|
style="vertical-align:baseline;" id="TBL-375-3-"><td style="white-space:nowrap; text-align:left;" id="TBL-375-3-1"
|
|
class="td11"><span
|
|
class="pcrb7t-">instance</span><span
|
|
class="pcrb7t-"> Integral</span><span
|
|
class="pcrb7t-"> a</span><span
|
|
class="pcrb7t-"> =></span><span
|
|
class="pcrb7t-"> Fractional</span><span
|
|
class="pcrb7t-"> (Ratio</span><span
|
|
class="pcrb7t-"> a) </span></td>
|
|
</tr><tr
|
|
style="vertical-align:baseline;" id="TBL-375-4-"><td style="white-space:nowrap; text-align:left;" id="TBL-375-4-1"
|
|
class="td11"><span
|
|
class="pcrb7t-">instance</span><span
|
|
class="pcrb7t-"> Integral</span><span
|
|
class="pcrb7t-"> a</span><span
|
|
class="pcrb7t-"> =></span><span
|
|
class="pcrb7t-"> Num</span><span
|
|
class="pcrb7t-"> (Ratio</span><span
|
|
class="pcrb7t-"> a) </span></td>
|
|
</tr><tr
|
|
style="vertical-align:baseline;" id="TBL-375-5-"><td style="white-space:nowrap; text-align:left;" id="TBL-375-5-1"
|
|
class="td11"><span
|
|
class="pcrb7t-">instance</span><span
|
|
class="pcrb7t-"> Integral</span><span
|
|
class="pcrb7t-"> a</span><span
|
|
class="pcrb7t-"> =></span><span
|
|
class="pcrb7t-"> Ord</span><span
|
|
class="pcrb7t-"> (Ratio</span><span
|
|
class="pcrb7t-"> a) </span></td>
|
|
</tr><tr
|
|
style="vertical-align:baseline;" id="TBL-375-6-"><td style="white-space:nowrap; text-align:left;" id="TBL-375-6-1"
|
|
class="td11"><span
|
|
class="pcrb7t-">instance</span><span
|
|
class="pcrb7t-"> (Integral</span><span
|
|
class="pcrb7t-"> a,</span><span
|
|
class="pcrb7t-"> Read</span><span
|
|
class="pcrb7t-"> a)</span><span
|
|
class="pcrb7t-"> =></span><span
|
|
class="pcrb7t-"> Read</span><span
|
|
class="pcrb7t-"> (Ratio</span><span
|
|
class="pcrb7t-"> a) </span></td>
|
|
</tr><tr
|
|
style="vertical-align:baseline;" id="TBL-375-7-"><td style="white-space:nowrap; text-align:left;" id="TBL-375-7-1"
|
|
class="td11"><span
|
|
class="pcrb7t-">instance</span><span
|
|
class="pcrb7t-"> Integral</span><span
|
|
class="pcrb7t-"> a</span><span
|
|
class="pcrb7t-"> =></span><span
|
|
class="pcrb7t-"> Real</span><span
|
|
class="pcrb7t-"> (Ratio</span><span
|
|
class="pcrb7t-"> a) </span></td>
|
|
</tr><tr
|
|
style="vertical-align:baseline;" id="TBL-375-8-"><td style="white-space:nowrap; text-align:left;" id="TBL-375-8-1"
|
|
class="td11"><span
|
|
class="pcrb7t-">instance</span><span
|
|
class="pcrb7t-"> Integral</span><span
|
|
class="pcrb7t-"> a</span><span
|
|
class="pcrb7t-"> =></span><span
|
|
class="pcrb7t-"> RealFrac</span><span
|
|
class="pcrb7t-"> (Ratio</span><span
|
|
class="pcrb7t-"> a) </span></td>
|
|
</tr><tr
|
|
style="vertical-align:baseline;" id="TBL-375-9-"><td style="white-space:nowrap; text-align:left;" id="TBL-375-9-1"
|
|
class="td11"><span
|
|
class="pcrb7t-">instance</span><span
|
|
class="pcrb7t-"> Integral</span><span
|
|
class="pcrb7t-"> a</span><span
|
|
class="pcrb7t-"> =></span><span
|
|
class="pcrb7t-"> Show</span><span
|
|
class="pcrb7t-"> (Ratio</span><span
|
|
class="pcrb7t-"> a) </span></td>
|
|
</tr></table> </div> <dd class="haddockdesc">
|
|
</dl>
|
|
<dl><dt class="haddockdesc">
|
|
<!--tex4ht:inline--><div class="tabular"> <table id="TBL-376" class="tabular"
|
|
cellspacing="0" cellpadding="0" rules="groups"
|
|
><colgroup id="TBL-376-1g"><col
|
|
id="TBL-376-1" /></colgroup><tr
|
|
style="vertical-align:baseline;" id="TBL-376-1-"><td style="white-space:nowrap; text-align:left;" id="TBL-376-1-1"
|
|
class="td11"><span
|
|
class="pcrb7t-">type</span><span
|
|
class="pcrb7t-"> Rational</span><span
|
|
class="pcrb7t-"> =</span><span
|
|
class="pcrb7t-"> Ratio</span><span
|
|
class="pcrb7t-"> Integer </span></td>
|
|
</tr></table> </div> <dd class="haddockdesc">
|
|
Arbitrary-precision rational numbers, represented as a ratio of two <span
|
|
class="pcrr7t-">Integer</span><a
|
|
id="dx30-258002"></a> values. A rational
|
|
number may be constructed using the <span
|
|
class="pcrr7t-">%</span><a
|
|
id="dx30-258003"></a> operator.
|
|
</dl>
|
|
<dl> <dt class="haddockdesc">
|
|
<!--tex4ht:inline--><div class="tabular"> <table id="TBL-377" class="tabular"
|
|
cellspacing="0" cellpadding="0" rules="groups"
|
|
><colgroup id="TBL-377-1g"><col
|
|
id="TBL-377-1" /></colgroup><tr
|
|
style="vertical-align:baseline;" id="TBL-377-1-"><td style="white-space:nowrap; text-align:left;" id="TBL-377-1-1"
|
|
class="td11"><span
|
|
class="pcrb7t-">(%)</span><span
|
|
class="pcrb7t-"> ::</span><span
|
|
class="pcrb7t-"> Integral</span><span
|
|
class="pcrb7t-"> a</span><span
|
|
class="pcrb7t-"> =></span><span
|
|
class="pcrb7t-"> a</span><span
|
|
class="pcrb7t-"> -></span><span
|
|
class="pcrb7t-"> a</span><span
|
|
class="pcrb7t-"> -></span><span
|
|
class="pcrb7t-"> Ratio</span><span
|
|
class="pcrb7t-"> a </span></td>
|
|
</tr></table> </div> <dd class="haddockdesc">
|
|
Forms the ratio of two integral numbers.
|
|
</dl>
|
|
<dl> <dt class="haddockdesc">
|
|
<!--tex4ht:inline--><div class="tabular"> <table id="TBL-378" class="tabular"
|
|
cellspacing="0" cellpadding="0" rules="groups"
|
|
><colgroup id="TBL-378-1g"><col
|
|
id="TBL-378-1" /></colgroup><tr
|
|
style="vertical-align:baseline;" id="TBL-378-1-"><td style="white-space:nowrap; text-align:left;" id="TBL-378-1-1"
|
|
class="td11"><span
|
|
class="pcrb7t-">numerator</span><span
|
|
class="pcrb7t-"> ::</span><span
|
|
class="pcrb7t-"> Integral</span><span
|
|
class="pcrb7t-"> a</span><span
|
|
class="pcrb7t-"> =></span><span
|
|
class="pcrb7t-"> Ratio</span><span
|
|
class="pcrb7t-"> a</span><span
|
|
class="pcrb7t-"> -></span><span
|
|
class="pcrb7t-"> a </span></td>
|
|
</tr></table> </div> <dd class="haddockdesc">
|
|
Extract the numerator of the ratio in reduced form: the numerator and denominator have no common
|
|
factor and the denominator is positive.
|
|
</dl>
|
|
<dl> <dt class="haddockdesc">
|
|
<!--tex4ht:inline--><div class="tabular"> <table id="TBL-379" class="tabular"
|
|
cellspacing="0" cellpadding="0" rules="groups"
|
|
><colgroup id="TBL-379-1g"><col
|
|
id="TBL-379-1" /></colgroup><tr
|
|
style="vertical-align:baseline;" id="TBL-379-1-"><td style="white-space:nowrap; text-align:left;" id="TBL-379-1-1"
|
|
class="td11"><span
|
|
class="pcrb7t-">denominator</span><span
|
|
class="pcrb7t-"> ::</span><span
|
|
class="pcrb7t-"> Integral</span><span
|
|
class="pcrb7t-"> a</span><span
|
|
class="pcrb7t-"> =></span><span
|
|
class="pcrb7t-"> Ratio</span><span
|
|
class="pcrb7t-"> a</span><span
|
|
class="pcrb7t-"> -></span><span
|
|
class="pcrb7t-"> a </span></td>
|
|
</tr></table> </div> <dd class="haddockdesc">
|
|
Extract the denominator of the ratio in reduced form: the numerator and denominator have no common
|
|
factor and the denominator is positive.
|
|
</dl>
|
|
<dl> <dt class="haddockdesc">
|
|
<!--tex4ht:inline--><div class="tabular"> <table id="TBL-380" class="tabular"
|
|
cellspacing="0" cellpadding="0" rules="groups"
|
|
><colgroup id="TBL-380-1g"><col
|
|
id="TBL-380-1" /></colgroup><tr
|
|
style="vertical-align:baseline;" id="TBL-380-1-"><td style="white-space:nowrap; text-align:left;" id="TBL-380-1-1"
|
|
class="td11"><span
|
|
class="pcrb7t-">approxRational</span><span
|
|
class="pcrb7t-"> ::</span><span
|
|
class="pcrb7t-"> RealFrac</span><span
|
|
class="pcrb7t-"> a</span><span
|
|
class="pcrb7t-"> =></span><span
|
|
class="pcrb7t-"> a</span><span
|
|
class="pcrb7t-"> -></span><span
|
|
class="pcrb7t-"> a</span><span
|
|
class="pcrb7t-"> -></span><span
|
|
class="pcrb7t-"> Rational </span></td>
|
|
</tr></table> </div> <dd class="haddockdesc">
|
|
<span
|
|
class="pcrr7t-">approxRational</span><a
|
|
id="dx30-258004"></a>, applied to two real fractional numbers <span
|
|
class="pcrr7t-">x </span>and <span
|
|
class="pcrr7t-">epsilon</span>, returns the simplest
|
|
rational number within <span
|
|
class="pcrr7t-">epsilon </span>of <span
|
|
class="pcrr7t-">x</span>. A rational number <span
|
|
class="pcrr7t-">y </span>is said to be <span
|
|
class="ptmri7t-">simpler </span>than another <span
|
|
class="pcrr7t-">y' </span>if
|
|
|
|
|
|
|
|
<ul class="itemize1">
|
|
<li class="itemize"><span
|
|
class="pcrr7t-">abs</span><span
|
|
class="pcrr7t-"> (numerator</span><span
|
|
class="pcrr7t-"> y)</span><span
|
|
class="pcrr7t-"> <=</span><span
|
|
class="pcrr7t-"> abs</span><span
|
|
class="pcrr7t-"> (numerator</span><span
|
|
class="pcrr7t-"> y')</span>, and
|
|
</li>
|
|
<li class="itemize"><span
|
|
class="pcrr7t-">denominator</span><span
|
|
class="pcrr7t-"> y</span><span
|
|
class="pcrr7t-"> <=</span><span
|
|
class="pcrr7t-"> denominator</span><span
|
|
class="pcrr7t-"> y'</span>.
|
|
</li></ul>
|
|
<p class="noindent"> Any real interval contains a unique simplest rational; in particular, note that <span
|
|
class="pcrr7t-">0/1 </span>is the simplest rational of
|
|
all.
|
|
</dl>
|
|
<h3 class="sectionHead"><span class="titlemark">22.1 </span> <a
|
|
id="x30-25900022.1"></a>Specification </h3>
|
|
<p class="noindent">
|
|
<div class="quote">
|
|
|
|
|
|
|
|
<div class="verbatim" id="verbatim-435">
|
|
 module  Data.Ratio (
|
|
 <br />     Ratio, Rational, (%), numerator, denominator, approxRational ) where
|
|
 <br />
|
|
 <br /> infixl 7  %
|
|
 <br />
|
|
 <br /> ratPrec = 7 :: Int
|
|
 <br />
|
|
 <br /> data  (Integral a)      => Ratio a = !a :% !a  deriving (Eq)
|
|
 <br /> type  Rational          =  Ratio Integer
|
|
 <br />
|
|
 <br /> (%)                     :: (Integral a) => a -> a -> Ratio a
|
|
 <br /> numerator, denominator  :: (Integral a) => Ratio a -> a
|
|
 <br /> approxRational          :: (RealFrac a) => a -> a -> Rational
|
|
 <br />
|
|
 <br />
|
|
 <br /> -- "reduce" is a subsidiary function used only in this module.
|
|
 <br /> -- It normalises a ratio by dividing both numerator
|
|
 <br /> -- and denominator by their greatest common divisor.
|
|
 <br /> --
|
|
 <br /> -- E.g., 12 ‘reduce‘ 8    ==  3 :%   2
|
|
 <br /> --       12 ‘reduce‘ (-8) ==  3 :% (-2)
|
|
 <br />
|
|
 <br /> reduce _ 0              =  error "Data.Ratio.% : zero denominator"
|
|
 <br /> reduce x y              =  (x ‘quot‘ d) :% (y ‘quot‘ d)
|
|
 <br />                            where d = gcd x y
|
|
 <br />
|
|
 <br /> x % y                   =  reduce (x ⋆ signum y) (abs y)
|
|
 <br />
|
|
 <br /> numerator (x :% _)      =  x
|
|
 <br />
|
|
 <br /> denominator (_ :% y)    =  y
|
|
 <br />
|
|
 <br />
|
|
 <br /> instance  (Integral a)  => Ord (Ratio a)  where
|
|
 <br />     (x:%y) <= (x':%y')  =  x ⋆ y' <= x' ⋆ y
|
|
 <br />     (x:%y) <  (x':%y')  =  x ⋆ y' <  x' ⋆ y
|
|
 <br />
|
|
 <br /> instance  (Integral a)  => Num (Ratio a)  where
|
|
 <br />     (x:%y) + (x':%y')   =  reduce (x⋆y' + x'⋆y) (y⋆y')
|
|
 <br />     (x:%y) ⋆ (x':%y')   =  reduce (x ⋆ x') (y ⋆ y')
|
|
 <br />     negate (x:%y)       =  (-x) :% y
|
|
 <br />     abs (x:%y)          =  abs x :% y
|
|
 <br />     signum (x:%y)       =  signum x :% 1
|
|
 <br />     fromInteger x       =  fromInteger x :% 1
|
|
 <br />
|
|
 <br /> instance  (Integral a)  => Real (Ratio a)  where
|
|
 <br />     toRational (x:%y)   =  toInteger x :% toInteger y
|
|
|
|
|
|
|
|
 <br />
|
|
 <br /> instance  (Integral a)  => Fractional (Ratio a)  where
|
|
 <br />     (x:%y) / (x':%y')   =  (x⋆y') % (y⋆x')
|
|
 <br />     recip (x:%y)        =  y % x
|
|
 <br />     fromRational (x:%y) =  fromInteger x :% fromInteger y
|
|
 <br />
|
|
 <br /> instance  (Integral a)  => RealFrac (Ratio a)  where
|
|
 <br />     properFraction (x:%y) = (fromIntegral q, r:%y)
|
|
 <br />                             where (q,r) = quotRem x y
|
|
 <br />
|
|
 <br /> instance  (Integral a)  => Enum (Ratio a)  where
|
|
 <br />     succ x           =  x+1
|
|
 <br />     pred x           =  x-1
|
|
 <br />     toEnum           =  fromIntegral
|
|
 <br />     fromEnum         =  fromInteger . truncate        -- May overflow
|
|
 <br />     enumFrom         =  numericEnumFrom               -- These numericEnumXXX functions
|
|
 <br />     enumFromThen     =  numericEnumFromThen   -- are as defined in Prelude.hs
|
|
 <br />     enumFromTo       =  numericEnumFromTo     -- but not exported from it!
|
|
 <br />     enumFromThenTo   =  numericEnumFromThenTo
|
|
 <br />
|
|
 <br /> instance  (Read a, Integral a)  => Read (Ratio a)  where
|
|
 <br />     readsPrec p  =  readParen (p > ratPrec)
|
|
 <br />                               (\r -> [(x%y,u) | (x,s)   <- readsPrec (ratPrec+1) r,
|
|
 <br />                                                 ("%",t) <- lex s,
|
|
 <br />                                                 (y,u)   <- readsPrec (ratPrec+1) t ])
|
|
 <br />
|
|
 <br /> instance  (Integral a)  => Show (Ratio a)  where
|
|
 <br />     showsPrec p (x:%y)  =  showParen (p > ratPrec)
|
|
 <br />                               showsPrec (ratPrec+1) x .
|
|
 <br />                               showString " % " .
|
|
 <br />                               showsPrec (ratPrec+1) y)
|
|
 <br />
|
|
 <br />
|
|
 <br />
|
|
 <br /> approxRational x eps    =  simplest (x-eps) (x+eps)
|
|
 <br />         where simplest x y | y < x      =  simplest y x
|
|
 <br />                            | x == y     =  xr
|
|
 <br />                            | x > 0      =  simplest' n d n' d'
|
|
 <br />                            | y < 0      =  - simplest' (-n') d' (-n) d
|
|
 <br />                            | otherwise  =  0 :% 1
|
|
 <br />                                         where xr@(n:%d) = toRational x
|
|
 <br />                                               (n':%d')  = toRational y
|
|
 <br />
|
|
 <br />               simplest' n d n' d'       -- assumes 0 < n%d < n'%d'
|
|
 <br />                         | r == 0     =  q :% 1
|
|
 <br />                         | q /= q'    =  (q+1) :% 1
|
|
 <br />                         | otherwise  =  (q⋆n''+d'') :% n''
|
|
 <br />                                      where (q,r)      =  quotRem n d
|
|
 <br />                                            (q',r')    =  quotRem n' d'
|
|
 <br />                                            (n'':%d'') =  simplest' d' r' d r
|
|
</div>
|
|
|
|
|
|
|
|
<p class="noindent"></div>
|
|
<!--l. 1--><div class="crosslinks"><p class="noindent">[<a
|
|
href="haskellch23.html" >next</a>] [<a
|
|
href="haskellch21.html" >prev</a>] [<a
|
|
href="haskellch21.html#tailhaskellch21.html" >prev-tail</a>] [<a
|
|
href="haskellch22.html" >front</a>] [<a
|
|
href="haskellpa2.html#haskellch22.html" >up</a>] </p></div>
|
|
<p class="noindent"> <a
|
|
id="tailhaskellch22.html"></a>
|
|
</body></html>
|