Movatterモバイル変換

{-# LANGUAGE Trustworthy #-}{-# LANGUAGE CPP, NoImplicitPrelude, MagicHash, UnboxedTuples #-}{-# OPTIONS_HADDOCK hide #-}------------------------------------------------------------------------------- |-- Module      :  GHC.Real-- Copyright   :  (c) The University of Glasgow, 1994-2002-- License     :  see libraries/base/LICENSE---- Maintainer  :  cvs-ghc@haskell.org-- Stability   :  internal-- Portability :  non-portable (GHC Extensions)---- The types 'Ratio' and 'Rational', and the classes 'Real', 'Fractional',-- 'Integral', and 'RealFrac'.--------------------------------------------------------------------------------- #hidemoduleGHC.RealwhereimportGHC.BaseimportGHC.NumimportGHC.ListimportGHC.EnumimportGHC.ShowimportGHC.Errinfixr8^,^^infixl7/,`quot`,`rem`,`div`,`mod`infixl7%default()-- Double isn't available yet,-- and we shouldn't be using defaults anyway

-- | Rational numbers, with numerator and denominator of some 'Integral' type.dataRatioa=!a:%!aderiving(Eq)-- | Arbitrary-precision rational numbers, represented as a ratio of-- two 'Integer' values.  A rational number may be constructed using-- the '%' operator.typeRational=RatioIntegerratioPrec,ratioPrec1::IntratioPrec=7-- Precedence of ':%' constructorratioPrec1=ratioPrec+1infinity,notANumber::Rationalinfinity=1:%0notANumber=0:%0-- Use :%, not % for Inf/NaN; the latter would-- immediately lead to a runtime error, because it normalises.

-- | Forms the ratio of two integral numbers.{-# SPECIALISE (%) :: Integer -> Integer -> Rational #-}(%)::(Integrala)=>a->a->Ratioa-- | Extract the numerator of the ratio in reduced form:-- the numerator and denominator have no common factor and the denominator-- is positive.numerator::(Integrala)=>Ratioa->a-- | Extract the denominator of the ratio in reduced form:-- the numerator and denominator have no common factor and the denominator-- is positive.denominator::(Integrala)=>Ratioa->a

reduce::(Integrala)=>a->a->Ratioa{-# SPECIALISE reduce :: Integer -> Integer -> Rational #-}reduce_0=error"Ratio.%: zero denominator"reducexy=(x`quot`d):%(y`quot`d)whered=gcdxy

x%y=reduce(x*signumy)(absy)numerator(x:%_)=xdenominator(_:%y)=y

class(Numa,Orda)=>Realawhere-- | the rational equivalent of its real argument with full precisiontoRational::a->Rational-- | Integral numbers, supporting integer division.---- Minimal complete definition: 'quotRem' and 'toInteger'class(Reala,Enuma)=>Integralawhere-- | integer division truncated toward zeroquot::a->a->a-- | integer remainder, satisfying---- > (x `quot` y)*y + (x `rem` y) == xrem::a->a->a-- | integer division truncated toward negative infinitydiv::a->a->a-- | integer modulus, satisfying---- > (x `div` y)*y + (x `mod` y) == xmod::a->a->a-- | simultaneous 'quot' and 'rem'quotRem::a->a->(a,a)-- | simultaneous 'div' and 'mod'divMod::a->a->(a,a)-- | conversion to 'Integer'toInteger::a->Integer{-# INLINE quot #-}{-# INLINE rem #-}{-# INLINE div #-}{-# INLINE mod #-}n`quot`d=qwhere(q,_)=quotRemndn`rem`d=rwhere(_,r)=quotRemndn`div`d=qwhere(q,_)=divModndn`mod`d=rwhere(_,r)=divModnddivModnd=ifsignumr==negate(signumd)then(q-1,r+d)elseqrwhereqr@(q,r)=quotRemnd-- | Fractional numbers, supporting real division.---- Minimal complete definition: 'fromRational' and ('recip' or @('/')@)class(Numa)=>Fractionalawhere-- | fractional division(/)::a->a->a-- | reciprocal fractionrecip::a->a-- | Conversion from a 'Rational' (that is @'Ratio' 'Integer'@).-- A floating literal stands for an application of 'fromRational'-- to a value of type 'Rational', so such literals have type-- @('Fractional' a) => a@.fromRational::Rational->a{-# INLINE recip #-}{-# INLINE (/) #-}recipx=1/xx/y=x*recipy-- | Extracting components of fractions.---- Minimal complete definition: 'properFraction'class(Reala,Fractionala)=>RealFracawhere-- | The function 'properFraction' takes a real fractional number @x@-- and returns a pair @(n,f)@ such that @x = n+f@, and:---- * @n@ is an integral number with the same sign as @x@; and---- * @f@ is a fraction with the same type and sign as @x@,--   and with absolute value less than @1@.---- The default definitions of the 'ceiling', 'floor', 'truncate'-- and 'round' functions are in terms of 'properFraction'.properFraction::(Integralb)=>a->(b,a)-- | @'truncate' x@ returns the integer nearest @x@ between zero and @x@truncate::(Integralb)=>a->b-- | @'round' x@ returns the nearest integer to @x@;--   the even integer if @x@ is equidistant between two integersround::(Integralb)=>a->b-- | @'ceiling' x@ returns the least integer not less than @x@ceiling::(Integralb)=>a->b-- | @'floor' x@ returns the greatest integer not greater than @x@floor::(Integralb)=>a->b{-# INLINE truncate #-}truncatex=mwhere(m,_)=properFractionxroundx=let(n,r)=properFractionxm=ifr<0thenn-1elsen+1incasesignum(absr-0.5)of-1->n0->ifevennthennelsem1->m_->error"round default defn: Bad value"ceilingx=ifr>0thenn+1elsenwhere(n,r)=properFractionxfloorx=ifr<0thenn-1elsenwhere(n,r)=properFractionx

numericEnumFrom::(Fractionala)=>a->[a]numericEnumFromn=n`seq`(n:numericEnumFrom(n+1))numericEnumFromThen::(Fractionala)=>a->a->[a]numericEnumFromThennm=n`seq`m`seq`(n:numericEnumFromThenm(m+m-n))numericEnumFromTo::(Orda,Fractionala)=>a->a->[a]numericEnumFromTonm=takeWhile(<=m+1/2)(numericEnumFromn)numericEnumFromThenTo::(Orda,Fractionala)=>a->a->a->[a]numericEnumFromThenToe1e2e3=takeWhilepredicate(numericEnumFromThene1e2)wheremid=(e2-e1)/2predicate|e2>=e1=(<=e3+mid)|otherwise=(>=e3+mid)

instanceRealIntwheretoRationalx=toIntegerx%1instanceIntegralIntwheretoInteger(I#i)=smallIntegeria`quot`b|b==0=divZeroError|b==(-1)&&a==minBound=overflowError-- Note [Order of tests]-- in GHC.Int|otherwise=a`quotInt`ba`rem`b|b==0=divZeroError-- The quotRem CPU instruction fails for minBound `quotRem` -1,-- but minBound `rem` -1 is well-defined (0). We therefore-- special-case it.|b==(-1)=0|otherwise=a`remInt`ba`div`b|b==0=divZeroError|b==(-1)&&a==minBound=overflowError-- Note [Order of tests]-- in GHC.Int|otherwise=a`divInt`ba`mod`b|b==0=divZeroError-- The divMod CPU instruction fails for minBound `divMod` -1,-- but minBound `mod` -1 is well-defined (0). We therefore-- special-case it.|b==(-1)=0|otherwise=a`modInt`ba`quotRem`b|b==0=divZeroError-- Note [Order of tests] in GHC.Int|b==(-1)&&a==minBound=(overflowError,0)|otherwise=a`quotRemInt`ba`divMod`b|b==0=divZeroError-- Note [Order of tests] in GHC.Int|b==(-1)&&a==minBound=(overflowError,0)|otherwise=a`divModInt`b

instanceRealIntegerwheretoRationalx=x%1instanceIntegralIntegerwheretoIntegern=n_`quot`0=divZeroErrorn`quot`d=n`quotInteger`d_`rem`0=divZeroErrorn`rem`d=n`remInteger`d_`divMod`0=divZeroErrora`divMod`b=casea`divModInteger`bof(#x,y#)->(x,y)_`quotRem`0=divZeroErrora`quotRem`b=casea`quotRemInteger`bof(#q,r#)->(q,r)-- use the defaults for div & mod

instance(Integrala)=>Ord(Ratioa)where{-# SPECIALIZE instance Ord Rational #-}(x:%y)<=(x':%y')=x*y'<=x'*y(x:%y)<(x':%y')=x*y'<x'*yinstance(Integrala)=>Num(Ratioa)where{-# SPECIALIZE instance Num Rational #-}(x:%y)+(x':%y')=reduce(x*y'+x'*y)(y*y')(x:%y)-(x':%y')=reduce(x*y'-x'*y)(y*y')(x:%y)*(x':%y')=reduce(x*x')(y*y')negate(x:%y)=(-x):%yabs(x:%y)=absx:%ysignum(x:%_)=signumx:%1fromIntegerx=fromIntegerx:%1{-# RULES "fromRational/id" fromRational = id :: Rational -> Rational #-}instance(Integrala)=>Fractional(Ratioa)where{-# SPECIALIZE instance Fractional Rational #-}(x:%y)/(x':%y')=(x*y')%(y*x')recip(0:%_)=error"Ratio.%: zero denominator"recip(x:%y)|x<0=negatey:%negatex|otherwise=y:%xfromRational(x:%y)=fromIntegerx%fromIntegeryinstance(Integrala)=>Real(Ratioa)where{-# SPECIALIZE instance Real Rational #-}toRational(x:%y)=toIntegerx:%toIntegeryinstance(Integrala)=>RealFrac(Ratioa)where{-# SPECIALIZE instance RealFrac Rational #-}properFraction(x:%y)=(fromInteger(toIntegerq),r:%y)where(q,r)=quotRemxyinstance(Integrala)=>Show(Ratioa)where{-# SPECIALIZE instance Show Rational #-}showsPrecp(x:%y)=showParen(p>ratioPrec)$showsPrecratioPrec1x.showString" % ".-- H98 report has spaces round the %-- but we removed them [May 04]-- and added them again for consistency with-- Haskell 98 [Sep 08, #1920]showsPrecratioPrec1yinstance(Integrala)=>Enum(Ratioa)where{-# SPECIALIZE instance Enum Rational #-}succx=x+1predx=x-1toEnumn=fromIntegraln:%1fromEnum=fromInteger.truncateenumFrom=numericEnumFromenumFromThen=numericEnumFromThenenumFromTo=numericEnumFromToenumFromThenTo=numericEnumFromThenTo

-- | general coercion from integral typesfromIntegral::(Integrala,Numb)=>a->bfromIntegral=fromInteger.toInteger{-# RULES"fromIntegral/Int->Int" fromIntegral = id :: Int -> Int    #-}-- | general coercion to fractional typesrealToFrac::(Reala,Fractionalb)=>a->brealToFrac=fromRational.toRational{-# RULES"realToFrac/Int->Int" realToFrac = id :: Int -> Int    #-}

-- | Converts a possibly-negative 'Real' value to a string.showSigned::(Reala)=>(a->ShowS)-- ^ a function that can show unsigned values->Int-- ^ the precedence of the enclosing context->a-- ^ the value to show->ShowSshowSignedshowPospx|x<0=showParen(p>6)(showChar'-'.showPos(-x))|otherwise=showPosxeven,odd::(Integrala)=>a->Boolevenn=n`rem`2==0odd=not.even--------------------------------------------------------- | raise a number to a non-negative integral power{-# SPECIALISE (^) ::        Integer -> Integer -> Integer,        Integer -> Int -> Integer,        Int -> Int -> Int #-}{-# INLINABLE (^) #-}-- See Note [Inlining (^)](^)::(Numa,Integralb)=>a->b->ax0^y0|y0<0=error"Negative exponent"|y0==0=1|otherwise=fx0y0where-- f : x0 ^ y0 = x ^ yfxy|eveny=f(x*x)(y`quot`2)|y==1=x|otherwise=g(x*x)((y-1)`quot`2)x-- g : x0 ^ y0 = (x ^ y) * zgxyz|eveny=g(x*x)(y`quot`2)z|y==1=x*z|otherwise=g(x*x)((y-1)`quot`2)(x*z)-- | raise a number to an integral power(^^)::(Fractionala,Integralb)=>a->b->a{-# INLINABLE (^^) #-}-- See Note [Inlining (^)x^^n=ifn>=0thenx^nelserecip(x^(negaten)){- Note [Inlining (^)   ~~~~~~~~~~~~~~~~~~~~~   The INLINABLE pragma allows (^) to be specialised at its call sites.   If it is called repeatedly at the same type, that can make a huge   difference, because of those constants which can be repeatedly   calculated.   Currently the fromInteger calls are not floated because we get             \d1 d2 x y -> blah   after the gentle round of simplification. -}--------------------------------------------------------- Special power functions for Rational---- see #4337---- Rationale:-- For a legitimate Rational (n :% d), the numerator and denominator are-- coprime, i.e. they have no common prime factor.-- Therefore all powers (n ^ a) and (d ^ b) are also coprime, so it is-- not necessary to compute the greatest common divisor, which would be-- done in the default implementation at each multiplication step.-- Since exponentiation quickly leads to very large numbers and-- calculation of gcds is generally very slow for large numbers,-- avoiding the gcd leads to an order of magnitude speedup relatively-- soon (and an asymptotic improvement overall).---- Note:-- We cannot use these functions for general Ratio a because that would-- change results in a multitude of cases.-- The cause is that if a and b are coprime, their remainders by any-- positive modulus generally aren't, so in the default implementation-- reduction occurs.---- Example:-- (17 % 3) ^ 3 :: Ratio Word8-- Default:-- (17 % 3) ^ 3 = ((17 % 3) ^ 2) * (17 % 3)--              = ((289 `mod` 256) % 9) * (17 % 3)--              = (33 % 9) * (17 % 3)--              = (11 % 3) * (17 % 3)--              = (187 % 9)-- But:-- ((17^3) `mod` 256) % (3^3)   = (4913 `mod` 256) % 27--                              = 49 % 27---- TODO:-- Find out whether special-casing for numerator, denominator or-- exponent = 1 (or -1, where that may apply) gains something.-- Special version of (^) for Rational base{-# RULES "(^)/Rational"    (^) = (^%^) #-}(^%^)::Integrala=>Rational->a->Rational(n:%d)^%^e|e<0=error"Negative exponent"|e==0=1:%1|otherwise=(n^e):%(d^e)-- Special version of (^^) for Rational base{-# RULES "(^^)/Rational"   (^^) = (^^%^^) #-}(^^%^^)::Integrala=>Rational->a->Rational(n:%d)^^%^^e|e>0=(n^e):%(d^e)|e==0=1:%1|n>0=(d^(negatee)):%(n^(negatee))|n==0=error"Ratio.%: zero denominator"|otherwise=letnn=d^(negatee)dd=(negaten)^(negatee)inifevenethen(nn:%dd)else(negatenn:%dd)--------------------------------------------------------- | @'gcd' x y@ is the non-negative factor of both @x@ and @y@ of which-- every common factor of @x@ and @y@ is also a factor; for example-- @'gcd' 4 2 = 2@, @'gcd' (-4) 6 = 2@, @'gcd' 0 4@ = @4@. @'gcd' 0 0@ = @0@.-- (That is, the common divisor that is \"greatest\" in the divisibility-- preordering.)---- Note: Since for signed fixed-width integer types, @'abs' 'minBound' < 0@,-- the result may be negative if one of the arguments is @'minBound'@ (and-- necessarily is if the other is @0@ or @'minBound'@) for such types.gcd::(Integrala)=>a->a->agcdxy=gcd'(absx)(absy)wheregcd'a0=agcd'ab=gcd'b(a`rem`b)-- | @'lcm' x y@ is the smallest positive integer that both @x@ and @y@ divide.lcm::(Integrala)=>a->a->a{-# SPECIALISE lcm :: Int -> Int -> Int #-}lcm_0=0lcm0_=0lcmxy=abs((x`quot`(gcdxy))*y)#ifdef OPTIMISE_INTEGER_GCD_LCM{-# RULES"gcd/Int->Int->Int"             gcd = gcdInt"gcd/Integer->Integer->Integer" gcd = gcdInteger"lcm/Integer->Integer->Integer" lcm = lcmInteger #-}gcdInt::Int->Int->IntgcdIntab=fromIntegral(gcdInteger(fromIntegrala)(fromIntegralb))#endifintegralEnumFrom::(Integrala,Boundeda)=>a->[a]integralEnumFromn=mapfromInteger[toIntegern..toInteger(maxBound`asTypeOf`n)]integralEnumFromThen::(Integrala,Boundeda)=>a->a->[a]integralEnumFromThenn1n2|i_n2>=i_n1=mapfromInteger[i_n1,i_n2..toInteger(maxBound`asTypeOf`n1)]|otherwise=mapfromInteger[i_n1,i_n2..toInteger(minBound`asTypeOf`n1)]wherei_n1=toIntegern1i_n2=toIntegern2integralEnumFromTo::Integrala=>a->a->[a]integralEnumFromTonm=mapfromInteger[toIntegern..toIntegerm]integralEnumFromThenTo::Integrala=>a->a->a->[a]integralEnumFromThenTon1n2m=mapfromInteger[toIntegern1,toIntegern2..toIntegerm]