{-# LANGUAGE Trustworthy #-}{-# LANGUAGE CPP, NoImplicitPrelude, MagicHash, UnboxedTuples, BangPatterns #-}{-# OPTIONS_GHC -Wno-orphans #-}{-# OPTIONS_HADDOCK not-home #-}------------------------------------------------------------------------------- |-- Module : GHC.Internal.Real-- Copyright : (c) The University of Glasgow, 1994-2002-- License : see libraries/base/LICENSE---- Maintainer : ghc-devs@haskell.org-- Stability : internal-- Portability : non-portable (GHC Extensions)---- The types 'Ratio' and 'Rational', and the classes 'Real', 'Fractional',-- 'Integral', and 'RealFrac'.-------------------------------------------------------------------------------moduleGHC.Internal.Real (-- * ClassesReal (..),Integral (..),Fractional (..),RealFrac (..)-- * Conversion,fromIntegral ,realToFrac -- * Formatting,showSigned -- * Predicates,even ,odd -- * Arithmetic,(^) ,(^^) ,gcd ,lcm -- * 'Ratio',Ratio (..),Rational ,infinity ,notANumber -- * 'Enum' helpers,numericEnumFrom ,numericEnumFromThen ,numericEnumFromTo ,numericEnumFromThenTo ,integralEnumFrom ,integralEnumFromThen ,integralEnumFromTo ,integralEnumFromThenTo -- ** Construction,(%) -- ** Projection,numerator ,denominator -- ** Operations,reduce -- * Internal,ratioPrec ,ratioPrec1 ,divZeroError ,ratioZeroDenominatorError ,overflowError ,underflowError ,mkRationalBase2 ,mkRationalBase10 ,FractionalExponentBase (..),(^%^) ,(^^%^^) ,mkRationalWithExponentBase ,powImpl ,powImplAcc )where
#include "MachDeps.h"
importGHC.Internal.Base importGHC.Internal.Num importGHC.Internal.List importGHC.Internal.Enum importGHC.Internal.Show import{-# SOURCE#-}GHC.Internal.Exception (divZeroException ,overflowException ,underflowException ,ratioZeroDenomException )importGHC.Num.BigNat (gcdInt ,gcdWord )infixr8^ ,^^ infixl7/ ,`quot` ,`rem` ,`div` ,`mod` infixl7% default()-- Double isn't available yet,-- and we shouldn't be using defaults anyway{- Note [Allow time for type-specialisation rules to fire]
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Consider
 lcm = ...
 {-# RULES "lcm/Integer->Integer->Integer" lcm = integerLcm #-}
We want to delay inlining `lcm` until the rule (which is a form of manual
type specialisation) has had a chance to fire. It can fire in InitialPhase,
so INLINE[2] seems sufficient. c.f. #20709
-}-------------------------------------------------------------------------- Divide by zero and arithmetic overflow-------------------------------------------------------------------------- We put them here because they are needed relatively early-- in the libraries before the Exception type has been defined yet.{-# NOINLINEdivZeroError #-}divZeroError ::a divZeroError :: forall a. a
divZeroError =SomeException -> a
forall a b. a -> b
raise# SomeException
divZeroException {-# NOINLINEratioZeroDenominatorError #-}ratioZeroDenominatorError ::a ratioZeroDenominatorError :: forall a. a
ratioZeroDenominatorError =SomeException -> a
forall a b. a -> b
raise# SomeException
ratioZeroDenomException {-# NOINLINEoverflowError #-}overflowError ::a overflowError :: forall a. a
overflowError =SomeException -> a
forall a b. a -> b
raise# SomeException
overflowException {-# NOINLINEunderflowError #-}underflowError ::a underflowError :: forall a. a
underflowError =SomeException -> a
forall a b. a -> b
raise# SomeException
underflowException ---------------------------------------------------------------- The Ratio and Rational types---------------------------------------------------------------- | Rational numbers, with numerator and denominator of some 'Integral' type.---- Note that `Ratio`'s instances inherit the deficiencies from the type-- parameter's. For example, @Ratio Natural@'s 'Num' instance has similar-- problems to `Numeric.Natural.Natural`'s.dataRatio a =!a :% !a derivingRatio a -> Ratio a -> Bool
(Ratio a -> Ratio a -> Bool)
-> (Ratio a -> Ratio a -> Bool) -> Eq (Ratio a)
forall a. Eq a => Ratio a -> Ratio a -> Bool
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
$c== :: forall a. Eq a => Ratio a -> Ratio a -> Bool
== :: Ratio a -> Ratio a -> Bool
$c/= :: forall a. Eq a => Ratio a -> Ratio a -> Bool
/= :: Ratio a -> Ratio a -> Bool
Eq -- ^ @since base-2.01-- | Arbitrary-precision rational numbers, represented as a ratio of-- two 'Integer' values. A rational number may be constructed using-- the '%' operator.typeRational =Ratio Integer ratioPrec ,ratioPrec1 ::Int ratioPrec :: Int
ratioPrec =Int
7-- Precedence of ':%' constructorratioPrec1 :: Int
ratioPrec1 =Int
ratioPrec Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
1infinity ,notANumber ::Rational infinity :: Rational
infinity =Integer
1Integer -> Integer -> Rational
forall a. a -> a -> Ratio a
:% Integer
0notANumber :: Rational
notANumber =Integer
0Integer -> Integer -> Rational
forall a. a -> a -> Ratio a
:% Integer
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 #-}(%) ::(Integral a )=>a ->a ->Ratio a -- | Extract the numerator of the ratio in reduced form:-- the numerator and denominator have no common factor and the denominator-- is positive.numerator ::Ratio a ->a -- | Extract the denominator of the ratio in reduced form:-- the numerator and denominator have no common factor and the denominator-- is positive.denominator ::Ratio a ->a -- | 'reduce' is a subsidiary function used only in this module.-- It normalises a ratio by dividing both numerator and denominator by-- their greatest common divisor.reduce ::(Integral a )=>a ->a ->Ratio a {-# SPECIALISEreduce ::Integer ->Integer ->Rational #-}reduce :: forall a. Integral a => a -> a -> Ratio a
reduce a
_a
0=Ratio a
forall a. a
ratioZeroDenominatorError reduce a
x a
y =(a
x a -> a -> a
forall a. Integral a => a -> a -> a
`quot` a
d )a -> a -> Ratio a
forall a. a -> a -> Ratio a
:% (a
y a -> a -> a
forall a. Integral a => a -> a -> a
`quot` a
d )whered :: a
d =a -> a -> a
forall a. Integral a => a -> a -> a
gcd a
x a
y a
x % :: forall a. Integral a => a -> a -> Ratio a
% a
y =a -> a -> Ratio a
forall a. Integral a => a -> a -> Ratio a
reduce (a
x a -> a -> a
forall a. Num a => a -> a -> a
* a -> a
forall a. Num a => a -> a
signum a
y )(a -> a
forall a. Num a => a -> a
abs a
y )numerator :: forall a. Ratio a -> a
numerator (a
x :% a
_)=a
x denominator :: forall a. Ratio a -> a
denominator (a
_:% a
y )=a
y ---------------------------------------------------------------- Standard numeric classes---------------------------------------------------------------- | Real numbers.---- The Haskell report defines no laws for 'Real', however 'Real' instances-- are customarily expected to adhere to the following law:---- [__Coherence with 'fromRational'__]: if the type also implements 'Fractional',-- then 'fromRational' is a left inverse for 'toRational', i.e. @fromRational (toRational i) = i@---- The law does not hold for 'Float', 'Double', 'Foreign.C.Types.CFloat',-- 'Foreign.C.Types.CDouble', etc., because these types contain non-finite values,-- which cannot be roundtripped through 'Rational'.class(Num a ,Ord a )=>Real a where-- | Rational equivalent of its real argument with full precision.toRational ::a ->Rational -- | Integral numbers, supporting integer division.---- The Haskell Report defines no laws for 'Integral'. However, 'Integral'-- instances are customarily expected to define a Euclidean domain and have the-- following properties for the 'div'\/'mod' and 'quot'\/'rem' pairs, given-- suitable Euclidean functions @f@ and @g@:---- * @x@ = @y * quot x y + rem x y@ with @rem x y@ = @fromInteger 0@ or-- @g (rem x y)@ < @g y@-- * @x@ = @y * div x y + mod x y@ with @mod x y@ = @fromInteger 0@ or-- @f (mod x y)@ < @f y@---- An example of a suitable Euclidean function, for 'Integer'\'s instance, is-- 'abs'.---- In addition, 'toInteger` should be total, and 'fromInteger' should be a left-- inverse for it, i.e. @fromInteger (toInteger i) = i@.class(Real a ,Enum a )=>Integral a where-- | Integer division truncated toward zero.---- WARNING: This function is partial (because it throws when 0 is passed as-- the divisor) for all the integer types in @base@.quot ::a ->a ->a -- | Integer remainder, satisfying---- > (x `quot` y)*y + (x `rem` y) == x---- WARNING: This function is partial (because it throws when 0 is passed as-- the divisor) for all the integer types in @base@.rem ::a ->a ->a -- | Integer division truncated toward negative infinity.---- WARNING: This function is partial (because it throws when 0 is passed as-- the divisor) for all the integer types in @base@.div ::a ->a ->a -- | Integer modulus, satisfying---- > (x `div` y)*y + (x `mod` y) == x---- WARNING: This function is partial (because it throws when 0 is passed as-- the divisor) for all the integer types in @base@.mod ::a ->a ->a -- | Simultaneous 'quot' and 'rem'.---- WARNING: This function is partial (because it throws when 0 is passed as-- the divisor) for all the integer types in @base@.quotRem ::a ->a ->(a ,a )-- | simultaneous 'div' and 'mod'.---- WARNING: This function is partial (because it throws when 0 is passed as-- the divisor) for all the integer types in @base@.divMod ::a ->a ->(a ,a )-- | Conversion to 'Integer'.toInteger ::a ->Integer {-# INLINEquot #-}{-# INLINErem #-}{-# INLINEdiv #-}{-# INLINEmod #-}a
n `quot` a
d =a
q where(a
q ,a
_)=a -> a -> (a, a)
forall a. Integral a => a -> a -> (a, a)
quotRem a
n a
d a
n `rem` a
d =a
r where(a
_,a
r )=a -> a -> (a, a)
forall a. Integral a => a -> a -> (a, a)
quotRem a
n a
d a
n `div` a
d =a
q where(a
q ,a
_)=a -> a -> (a, a)
forall a. Integral a => a -> a -> (a, a)
divMod a
n a
d a
n `mod` a
d =a
r where(a
_,a
r )=a -> a -> (a, a)
forall a. Integral a => a -> a -> (a, a)
divMod a
n a
d divMod a
n a
d =ifa -> a
forall a. Num a => a -> a
signum a
r a -> a -> Bool
forall a. Eq a => a -> a -> Bool
== a -> a
forall a. Num a => a -> a
negate (a -> a
forall a. Num a => a -> a
signum a
d )then(a
q a -> a -> a
forall a. Num a => a -> a -> a
- a
1,a
r a -> a -> a
forall a. Num a => a -> a -> a
+ a
d )else(a, a)
qr whereqr :: (a, a)
qr @(a
q ,a
r )=a -> a -> (a, a)
forall a. Integral a => a -> a -> (a, a)
quotRem a
n a
d -- | Fractional numbers, supporting real division.---- The Haskell Report defines no laws for 'Fractional'. However, @('+')@ and-- @('*')@ are customarily expected to define a division ring and have the-- following properties:---- [__'recip' gives the multiplicative inverse__]:-- @x * recip x@ = @recip x * x@ = @fromInteger 1@-- [__Totality of 'toRational'__]: 'toRational' is total-- [__Coherence with 'toRational'__]: if the type also implements 'Real',-- then 'fromRational' is a left inverse for 'toRational', i.e. @fromRational (toRational i) = i@---- Note that it /isn't/ customarily expected that a type instance of-- 'Fractional' implement a field. However, all instances in @base@ do.class(Num a )=>Fractional a where{-# MINIMALfromRational ,(recip |(/))#-}-- | Fractional division.(/) ::a ->a ->a -- | Reciprocal fraction.recip ::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 {-# INLINErecip #-}{-# INLINE(/)#-}recip a
x =a
1a -> a -> a
forall a. Fractional a => a -> a -> a
/ a
x a
x / a
y =a
x a -> a -> a
forall a. Num a => a -> a -> a
* a -> a
forall a. Fractional a => a -> a
recip a
y -- | Extracting components of fractions.class(Real a ,Fractional a )=>RealFrac a where-- | 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 ::(Integral b )=>a ->(b ,a )-- | @'truncate' x@ returns the integer nearest @x@ between zero and @x@truncate ::(Integral b )=>a ->b -- | @'round' x@ returns the nearest integer to @x@;-- the even integer if @x@ is equidistant between two integersround ::(Integral b )=>a ->b -- | @'ceiling' x@ returns the least integer not less than @x@ceiling ::(Integral b )=>a ->b -- | @'floor' x@ returns the greatest integer not greater than @x@floor ::(Integral b )=>a ->b {-# INLINEtruncate #-}truncate a
x =b
m where(b
m ,a
_)=a -> (b, a)
forall b. Integral b => a -> (b, a)
forall a b. (RealFrac a, Integral b) => a -> (b, a)
properFraction a
x round a
x =let(b
n ,a
r )=a -> (b, a)
forall b. Integral b => a -> (b, a)
forall a b. (RealFrac a, Integral b) => a -> (b, a)
properFraction a
x m :: b
m =ifa
r a -> a -> Bool
forall a. Ord a => a -> a -> Bool
< a
0thenb
n b -> b -> b
forall a. Num a => a -> a -> a
- b
1elseb
n b -> b -> b
forall a. Num a => a -> a -> a
+ b
1incasea -> a
forall a. Num a => a -> a
signum (a -> a
forall a. Num a => a -> a
abs a
r a -> a -> a
forall a. Num a => a -> a -> a
- a
0.5)of-1->b
n a
0->ifb -> Bool
forall a. Integral a => a -> Bool
even b
n thenb
n elseb
m a
1->b
m a
_->[Char] -> b
forall a. [Char] -> a
errorWithoutStackTrace [Char]
"round default defn: Bad value"ceiling a
x =ifa
r a -> a -> Bool
forall a. Ord a => a -> a -> Bool
> a
0thenb
n b -> b -> b
forall a. Num a => a -> a -> a
+ b
1elseb
n where(b
n ,a
r )=a -> (b, a)
forall b. Integral b => a -> (b, a)
forall a b. (RealFrac a, Integral b) => a -> (b, a)
properFraction a
x floor a
x =ifa
r a -> a -> Bool
forall a. Ord a => a -> a -> Bool
< a
0thenb
n b -> b -> b
forall a. Num a => a -> a -> a
- b
1elseb
n where(b
n ,a
r )=a -> (b, a)
forall b. Integral b => a -> (b, a)
forall a b. (RealFrac a, Integral b) => a -> (b, a)
properFraction a
x -- These 'numeric' enumerations come straight from the ReportnumericEnumFrom ::(Fractional a )=>a ->[a ]{-# INLINEnumericEnumFrom #-}-- See Note [Inline Enum method helpers] in GHC.Internal.EnumnumericEnumFrom :: forall a. Fractional a => a -> [a]
numericEnumFrom a
n =a -> [a]
go a
0where-- See Note [Numeric Stability of Enumerating Floating Numbers]go :: a -> [a]
go !a
k =let!n' :: a
n' =a
n a -> a -> a
forall a. Num a => a -> a -> a
+ a
k ina
n' a -> [a] -> [a]
forall a. a -> [a] -> [a]
: a -> [a]
go (a
k a -> a -> a
forall a. Num a => a -> a -> a
+ a
1)numericEnumFromThen ::(Fractional a )=>a ->a ->[a ]{-# INLINEnumericEnumFromThen #-}-- See Note [Inline Enum method helpers] in GHC.Internal.EnumnumericEnumFromThen :: forall a. Fractional a => a -> a -> [a]
numericEnumFromThen a
n a
m =a -> [a]
go a
0wherestep :: a
step =a
m a -> a -> a
forall a. Num a => a -> a -> a
- a
n -- See Note [Numeric Stability of Enumerating Floating Numbers]go :: a -> [a]
go !a
k =let!n' :: a
n' =a
n a -> a -> a
forall a. Num a => a -> a -> a
+ a
k a -> a -> a
forall a. Num a => a -> a -> a
* a
step ina
n' a -> [a] -> [a]
forall a. a -> [a] -> [a]
: a -> [a]
go (a
k a -> a -> a
forall a. Num a => a -> a -> a
+ a
1)numericEnumFromTo ::(Ord a ,Fractional a )=>a ->a ->[a ]{-# INLINEnumericEnumFromTo #-}-- See Note [Inline Enum method helpers] in GHC.Internal.EnumnumericEnumFromTo :: forall a. (Ord a, Fractional a) => a -> a -> [a]
numericEnumFromTo a
n a
m =let!to :: a
to =a
m a -> a -> a
forall a. Num a => a -> a -> a
+ a
1a -> a -> a
forall a. Fractional a => a -> a -> a
/ a
2in(a -> Bool) -> [a] -> [a]
forall a. (a -> Bool) -> [a] -> [a]
takeWhile (a -> a -> Bool
forall a. Ord a => a -> a -> Bool
<= a
to )(a -> [a]
forall a. Fractional a => a -> [a]
numericEnumFrom a
n )numericEnumFromThenTo ::(Ord a ,Fractional a )=>a ->a ->a ->[a ]{-# INLINEnumericEnumFromThenTo #-}-- See Note [Inline Enum method helpers] in GHC.Internal.EnumnumericEnumFromThenTo :: forall a. (Ord a, Fractional a) => a -> a -> a -> [a]
numericEnumFromThenTo a
e1 a
e2 !a
e3 =(a -> Bool) -> [a] -> [a]
forall a. (a -> Bool) -> [a] -> [a]
takeWhile a -> Bool
predicate (a -> a -> [a]
forall a. Fractional a => a -> a -> [a]
numericEnumFromThen a
e1 a
e2 )where!mid :: a
mid =(a
e2 a -> a -> a
forall a. Num a => a -> a -> a
- a
e1 )a -> a -> a
forall a. Fractional a => a -> a -> a
/ a
2!predicate :: a -> Bool
predicate |a
e2 a -> a -> Bool
forall a. Ord a => a -> a -> Bool
>= a
e1 =(a -> a -> Bool
forall a. Ord a => a -> a -> Bool
<= a
e3 a -> a -> a
forall a. Num a => a -> a -> a
+ a
mid )|Bool
otherwise =(a -> a -> Bool
forall a. Ord a => a -> a -> Bool
>= a
e3 a -> a -> a
forall a. Num a => a -> a -> a
+ a
mid ){- Note [Numeric Stability of Enumerating Floating Numbers]
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
When enumerate floating numbers, we could add the increment to the last number
at every run (as what we did previously):
 numericEnumFrom n = n `seq` (n : numericEnumFrom (n + 1))
This approach is concise and really fast, only needs an addition operation.
However when a floating number is large enough, for `n`, `n` and `n+1` will
have the same binary representation. For example (all number has type
`Double`):
 9007199254740990 is: 0x433ffffffffffffe
 9007199254740990 + 1 is: 0x433fffffffffffff
 (9007199254740990 + 1) + 1 is: 0x4340000000000000
 ((9007199254740990 + 1) + 1) + 1 is: 0x4340000000000000
When we evaluate ([9007199254740990..9007199254740991] :: Double), we would
never reach the condition in `numericEnumFromTo`
 9007199254740990 + 1 + 1 + ... > 9007199254740991 + 1/2
We would fall into infinite loop (as reported in #15081).
To remedy the situation, we record the number of `1` that needed to be added
to the start number, rather than increasing `1` at every time. This approach
can improvement the numeric stability greatly at the cost of a multiplication.
Furthermore, we use the type of the enumerated number, `Fractional a => a`,
as the type of multiplier. In rare situations, the multiplier could be very
large and will lead to the enumeration to infinite loop, too, which should
be very rare. Consider the following example:
 [1..9007199254740994]
We could fix that by using an Integer as multiplier but we don't do that.
The benchmark on T7954.hs shows that this approach leads to significant
degeneration on performance (33% increase allocation and 300% increase on
elapsed time).
See #15081 and Phab:D4650 for the related discussion about this problem.
-}---------------------------------------------------------------- Instances for Int---------------------------------------------------------------- | @since base-2.0.1instanceReal Int wheretoRational :: Int -> Rational
toRational Int
x =Int -> Integer
forall a. Integral a => a -> Integer
toInteger Int
x Integer -> Integer -> Rational
forall a. a -> a -> Ratio a
:% Integer
1-- | @since base-2.0.1instanceIntegral Int wheretoInteger :: Int -> Integer
toInteger (I# Int#
i )=Int# -> Integer
IS Int#
i {-# INLINEquot #-}-- see Note [INLINE division wrappers] in GHC.Internal.BaseInt
a quot :: Int -> Int -> Int
`quot` Int
b |Int
b Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== Int
0=Int
forall a. a
divZeroError |Int
b Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== (-Int
1)Bool -> Bool -> Bool
&& Int
a Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== Int
forall a. Bounded a => a
minBound =Int
forall a. a
overflowError -- Note [Order of tests]-- in GHC.Internal.Int|Bool
otherwise =Int
a Int -> Int -> Int
`quotInt` Int
b {-# INLINErem #-}-- see Note [INLINE division wrappers] in GHC.Internal.Base!Int
a rem :: Int -> Int -> Int
`rem` Int
b -- See Note [Special case of mod and rem is lazy]|Int
b Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== Int
0=Int
forall a. a
divZeroError |Int
b Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== (-Int
1)=Int
0|Bool
otherwise =Int
a Int -> Int -> Int
`remInt` Int
b {-# INLINEdiv #-}-- see Note [INLINE division wrappers] in GHC.Internal.BaseInt
a div :: Int -> Int -> Int
`div` Int
b |Int
b Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== Int
0=Int
forall a. a
divZeroError |Int
b Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== (-Int
1)Bool -> Bool -> Bool
&& Int
a Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== Int
forall a. Bounded a => a
minBound =Int
forall a. a
overflowError -- Note [Order of tests]-- in GHC.Internal.Int|Bool
otherwise =Int
a Int -> Int -> Int
`divInt` Int
b {-# INLINEmod #-}-- see Note [INLINE division wrappers] in GHC.Internal.Base!Int
a mod :: Int -> Int -> Int
`mod` Int
b -- See Note [Special case of mod and rem is lazy]|Int
b Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== Int
0=Int
forall a. a
divZeroError |Int
b Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== (-Int
1)=Int
0|Bool
otherwise =Int
a Int -> Int -> Int
`modInt` Int
b {-# INLINEquotRem #-}-- see Note [INLINE division wrappers] in GHC.Internal.BaseInt
a quotRem :: Int -> Int -> (Int, Int)
`quotRem` Int
b |Int
b Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== Int
0=(Int, Int)
forall a. a
divZeroError -- Note [Order of tests] in GHC.Internal.Int|Int
b Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== (-Int
1)Bool -> Bool -> Bool
&& Int
a Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== Int
forall a. Bounded a => a
minBound =(Int
forall a. a
overflowError ,Int
0)|Bool
otherwise =Int
a Int -> Int -> (Int, Int)
`quotRemInt` Int
b {-# INLINEdivMod #-}-- see Note [INLINE division wrappers] in GHC.Internal.BaseInt
a divMod :: Int -> Int -> (Int, Int)
`divMod` Int
b |Int
b Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== Int
0=(Int, Int)
forall a. a
divZeroError -- Note [Order of tests] in GHC.Internal.Int|Int
b Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== (-Int
1)Bool -> Bool -> Bool
&& Int
a Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== Int
forall a. Bounded a => a
minBound =(Int
forall a. a
overflowError ,Int
0)|Bool
otherwise =Int
a Int -> Int -> (Int, Int)
`divModInt` Int
b {- Note [Special case of mod and rem is lazy]
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
The `quotRem`/`divMod` CPU instruction fails for minBound `quotRem` -1, but
minBound `rem` -1 is well-defined (0). We therefore special-case for `b == -1`,
but not for `a == minBound` because of Note [Order of tests] in GHC.Int. But
now we have to make sure the function stays strict in a, to guarantee unboxing.
Hence the bang on a, see #18187.
-}---------------------------------------------------------------- Instances for @Word@---------------------------------------------------------------- | @since base-2.01instanceReal Word wheretoRational :: Word -> Rational
toRational Word
x =Word -> Integer
forall a. Integral a => a -> Integer
toInteger Word
x Integer -> Integer -> Rational
forall a. Integral a => a -> a -> Ratio a
% Integer
1-- | @since base-2.01instanceIntegral Word where-- see Note [INLINE division wrappers] in GHC.Internal.Base{-# INLINEquot #-}{-# INLINErem #-}{-# INLINEquotRem #-}{-# INLINEdiv #-}{-# INLINEmod #-}{-# INLINEdivMod #-}quot :: Word -> Word -> Word
quot (W# Word#
x# )y :: Word
y @(W# Word#
y# )|Word
y Word -> Word -> Bool
forall a. Eq a => a -> a -> Bool
/= Word
0=Word# -> Word
W# (Word#
x# Word# -> Word# -> Word#
`quotWord#` Word#
y# )|Bool
otherwise =Word
forall a. a
divZeroError rem :: Word -> Word -> Word
rem (W# Word#
x# )y :: Word
y @(W# Word#
y# )|Word
y Word -> Word -> Bool
forall a. Eq a => a -> a -> Bool
/= Word
0=Word# -> Word
W# (Word#
x# Word# -> Word# -> Word#
`remWord#` Word#
y# )|Bool
otherwise =Word
forall a. a
divZeroError quotRem :: Word -> Word -> (Word, Word)
quotRem (W# Word#
x# )y :: Word
y @(W# Word#
y# )|Word
y Word -> Word -> Bool
forall a. Eq a => a -> a -> Bool
/= Word
0=caseWord#
x# Word# -> Word# -> (# Word#, Word# #)
`quotRemWord#` Word#
y# of(#Word#
q ,Word#
r #)->(Word# -> Word
W# Word#
q ,Word# -> Word
W# Word#
r )|Bool
otherwise =(Word, Word)
forall a. a
divZeroError div :: Word -> Word -> Word
div Word
x Word
y =Word -> Word -> Word
forall a. Integral a => a -> a -> a
quot Word
x Word
y mod :: Word -> Word -> Word
mod Word
x Word
y =Word -> Word -> Word
forall a. Integral a => a -> a -> a
rem Word
x Word
y divMod :: Word -> Word -> (Word, Word)
divMod Word
x Word
y =Word -> Word -> (Word, Word)
forall a. Integral a => a -> a -> (a, a)
quotRem Word
x Word
y toInteger :: Word -> Integer
toInteger (W# Word#
x# )=Word# -> Integer
integerFromWord# Word#
x# ---------------------------------------------------------------- Instances for Integer---------------------------------------------------------------- | @since base-2.0.1instanceReal Integer wheretoRational :: Integer -> Rational
toRational Integer
x =Integer
x Integer -> Integer -> Rational
forall a. a -> a -> Ratio a
:% Integer
1-- | @since base-4.8.0.0instanceReal Natural wheretoRational :: Natural -> Rational
toRational Natural
n =Natural -> Integer
integerFromNatural Natural
n Integer -> Integer -> Rational
forall a. a -> a -> Ratio a
:% Integer
1-- Note [Integer division constant folding]-- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~---- Constant folding of quot, rem, div, mod, divMod and quotRem for Integer-- arguments depends crucially on inlining. Constant folding rules defined in-- GHC.Core.Opt.ConstantFold trigger for integerQuot, integerRem and so on.-- So if calls to quot, rem and so on were not inlined the rules would not fire.---- The rules would also not fire if calls to integerQuot and so on were inlined,-- but this does not happen because they are all marked with NOINLINE pragma.-- | @since base-2.0.1instanceIntegral Integer where-- see Note [INLINE division wrappers] in GHC.Internal.Base{-# INLINEquot #-}{-# INLINErem #-}{-# INLINEquotRem #-}{-# INLINEdiv #-}{-# INLINEmod #-}{-# INLINEdivMod #-}toInteger :: Integer -> Integer
toInteger Integer
n =Integer
n !Integer
_quot :: Integer -> Integer -> Integer
`quot` Integer
0=Integer
forall a. a
divZeroError Integer
n `quot` Integer
d =Integer
n Integer -> Integer -> Integer
`integerQuot` Integer
d !Integer
_rem :: Integer -> Integer -> Integer
`rem` Integer
0=Integer
forall a. a
divZeroError Integer
n `rem` Integer
d =Integer
n Integer -> Integer -> Integer
`integerRem` Integer
d !Integer
_div :: Integer -> Integer -> Integer
`div` Integer
0=Integer
forall a. a
divZeroError Integer
n `div` Integer
d =Integer
n Integer -> Integer -> Integer
`integerDiv` Integer
d !Integer
_mod :: Integer -> Integer -> Integer
`mod` Integer
0=Integer
forall a. a
divZeroError Integer
n `mod` Integer
d =Integer
n Integer -> Integer -> Integer
`integerMod` Integer
d !Integer
_divMod :: Integer -> Integer -> (Integer, Integer)
`divMod` Integer
0=(Integer, Integer)
forall a. a
divZeroError Integer
n `divMod` Integer
d =Integer
n Integer -> Integer -> (Integer, Integer)
`integerDivMod` Integer
d !Integer
_quotRem :: Integer -> Integer -> (Integer, Integer)
`quotRem` Integer
0=(Integer, Integer)
forall a. a
divZeroError Integer
n `quotRem` Integer
d =Integer
n Integer -> Integer -> (Integer, Integer)
`integerQuotRem` Integer
d -- | @since base-4.8.0.0instanceIntegral Natural where-- see Note [INLINE division wrappers] in GHC.Internal.Base{-# INLINEquot #-}{-# INLINErem #-}{-# INLINEquotRem #-}{-# INLINEdiv #-}{-# INLINEmod #-}{-# INLINEdivMod #-}toInteger :: Natural -> Integer
toInteger Natural
x =Natural -> Integer
integerFromNatural Natural
x !Natural
_quot :: Natural -> Natural -> Natural
`quot` Natural
0=Natural
forall a. a
divZeroError Natural
n `quot` Natural
d =Natural
n Natural -> Natural -> Natural
`naturalQuot` Natural
d !Natural
_rem :: Natural -> Natural -> Natural
`rem` Natural
0=Natural
forall a. a
divZeroError Natural
n `rem` Natural
d =Natural
n Natural -> Natural -> Natural
`naturalRem` Natural
d !Natural
_quotRem :: Natural -> Natural -> (Natural, Natural)
`quotRem` Natural
0=(Natural, Natural)
forall a. a
divZeroError Natural
n `quotRem` Natural
d =Natural
n Natural -> Natural -> (Natural, Natural)
`naturalQuotRem` Natural
d div :: Natural -> Natural -> Natural
div Natural
x Natural
y =Natural -> Natural -> Natural
forall a. Integral a => a -> a -> a
quot Natural
x Natural
y mod :: Natural -> Natural -> Natural
mod Natural
x Natural
y =Natural -> Natural -> Natural
forall a. Integral a => a -> a -> a
rem Natural
x Natural
y divMod :: Natural -> Natural -> (Natural, Natural)
divMod Natural
x Natural
y =Natural -> Natural -> (Natural, Natural)
forall a. Integral a => a -> a -> (a, a)
quotRem Natural
x Natural
y ---------------------------------------------------------------- Instances for @Ratio@---------------------------------------------------------------- | @since base-2.0.1instance(Integral a )=>Ord (Ratio a )where{-# SPECIALIZEinstanceOrd Rational #-}(a
x :% a
y )<= :: Ratio a -> Ratio a -> Bool
<= (a
x' :% a
y' )=a
x a -> a -> a
forall a. Num a => a -> a -> a
* a
y' a -> a -> Bool
forall a. Ord a => a -> a -> Bool
<= a
x' a -> a -> a
forall a. Num a => a -> a -> a
* a
y (a
x :% a
y )< :: Ratio a -> Ratio a -> Bool
< (a
x' :% a
y' )=a
x a -> a -> a
forall a. Num a => a -> a -> a
* a
y' a -> a -> Bool
forall a. Ord a => a -> a -> Bool
< a
x' a -> a -> a
forall a. Num a => a -> a -> a
* a
y -- | @since base-2.0.1instance(Integral a )=>Num (Ratio a )where{-# SPECIALIZEinstanceNum Rational #-}(a
x :% a
y )+ :: Ratio a -> Ratio a -> Ratio a
+ (a
x' :% a
y' )=a -> a -> Ratio a
forall a. Integral a => a -> a -> Ratio a
reduce (a
x a -> a -> a
forall a. Num a => a -> a -> a
* a
y' a -> a -> a
forall a. Num a => a -> a -> a
+ a
x' a -> a -> a
forall a. Num a => a -> a -> a
* a
y )(a
y a -> a -> a
forall a. Num a => a -> a -> a
* a
y' )(a
x :% a
y )- :: Ratio a -> Ratio a -> Ratio a
- (a
x' :% a
y' )=a -> a -> Ratio a
forall a. Integral a => a -> a -> Ratio a
reduce (a
x a -> a -> a
forall a. Num a => a -> a -> a
* a
y' a -> a -> a
forall a. Num a => a -> a -> a
- a
x' a -> a -> a
forall a. Num a => a -> a -> a
* a
y )(a
y a -> a -> a
forall a. Num a => a -> a -> a
* a
y' )(a
x :% a
y )* :: Ratio a -> Ratio a -> Ratio a
* (a
x' :% a
y' )=a -> a -> Ratio a
forall a. Integral a => a -> a -> Ratio a
reduce (a
x a -> a -> a
forall a. Num a => a -> a -> a
* a
x' )(a
y a -> a -> a
forall a. Num a => a -> a -> a
* a
y' )negate :: Ratio a -> Ratio a
negate (a
x :% a
y )=(-a
x )a -> a -> Ratio a
forall a. a -> a -> Ratio a
:% a
y abs :: Ratio a -> Ratio a
abs (a
x :% a
y )=a -> a
forall a. Num a => a -> a
abs a
x a -> a -> Ratio a
forall a. a -> a -> Ratio a
:% a
y signum :: Ratio a -> Ratio a
signum (a
x :% a
_)=a -> a
forall a. Num a => a -> a
signum a
x a -> a -> Ratio a
forall a. a -> a -> Ratio a
:% a
1fromInteger :: Integer -> Ratio a
fromInteger Integer
x =Integer -> a
forall a. Num a => Integer -> a
fromInteger Integer
x a -> a -> Ratio a
forall a. a -> a -> Ratio a
:% a
1-- | @since base-2.0.1{-# RULES"fromRational/id"fromRational =id ::Rational ->Rational #-}instance(Integral a )=>Fractional (Ratio a )where{-# SPECIALIZEinstanceFractional Rational #-}(a
x :% a
y )/ :: Ratio a -> Ratio a -> Ratio a
/ (a
x' :% a
y' )=(a
x a -> a -> a
forall a. Num a => a -> a -> a
* a
y' )a -> a -> Ratio a
forall a. Integral a => a -> a -> Ratio a
% (a
y a -> a -> a
forall a. Num a => a -> a -> a
* a
x' )recip :: Ratio a -> Ratio a
recip (a
0:% a
_)=Ratio a
forall a. a
ratioZeroDenominatorError recip (a
x :% a
y )|a
x a -> a -> Bool
forall a. Ord a => a -> a -> Bool
< a
0=a -> a
forall a. Num a => a -> a
negate a
y a -> a -> Ratio a
forall a. a -> a -> Ratio a
:% a -> a
forall a. Num a => a -> a
negate a
x |Bool
otherwise =a
y a -> a -> Ratio a
forall a. a -> a -> Ratio a
:% a
x fromRational :: Rational -> Ratio a
fromRational (Integer
x :% Integer
y )=Integer -> a
forall a. Num a => Integer -> a
fromInteger Integer
x a -> a -> Ratio a
forall a. Integral a => a -> a -> Ratio a
% Integer -> a
forall a. Num a => Integer -> a
fromInteger Integer
y -- | @since base-2.0.1instance(Integral a )=>Real (Ratio a )where{-# SPECIALIZEinstanceReal Rational #-}toRational :: Ratio a -> Rational
toRational (a
x :% a
y )=a -> Integer
forall a. Integral a => a -> Integer
toInteger a
x Integer -> Integer -> Rational
forall a. a -> a -> Ratio a
:% a -> Integer
forall a. Integral a => a -> Integer
toInteger a
y -- | @since base-2.0.1instance(Integral a )=>RealFrac (Ratio a )where{-# SPECIALIZEinstanceRealFrac Rational #-}properFraction :: forall b. Integral b => Ratio a -> (b, Ratio a)
properFraction (a
x :% a
y )=(Integer -> b
forall a. Num a => Integer -> a
fromInteger (a -> Integer
forall a. Integral a => a -> Integer
toInteger a
q ),a
r a -> a -> Ratio a
forall a. a -> a -> Ratio a
:% a
y )where(a
q ,a
r )=a -> a -> (a, a)
forall a. Integral a => a -> a -> (a, a)
quotRem a
x a
y round :: forall b. Integral b => Ratio a -> b
round Ratio a
r =let(b
n ,Ratio a
f )=Ratio a -> (b, Ratio a)
forall b. Integral b => Ratio a -> (b, Ratio a)
forall a b. (RealFrac a, Integral b) => a -> (b, a)
properFraction Ratio a
r x :: b
x =ifRatio a
r Ratio a -> Ratio a -> Bool
forall a. Ord a => a -> a -> Bool
< Ratio a
0then-b
1elseb
1incase(Ratio a -> Ratio a -> Ordering
forall a. Ord a => a -> a -> Ordering
compare (Ratio a -> Ratio a
forall a. Num a => a -> a
abs Ratio a
f )Ratio a
0.5,b -> Bool
forall a. Integral a => a -> Bool
odd b
n )of(Ordering
LT ,Bool
_)->b
n (Ordering
EQ ,Bool
False )->b
n (Ordering
EQ ,Bool
True )->b
n b -> b -> b
forall a. Num a => a -> a -> a
+ b
x (Ordering
GT ,Bool
_)->b
n b -> b -> b
forall a. Num a => a -> a -> a
+ b
x -- | @since base-2.0.1instance(Show a )=>Show (Ratio a )where{-# SPECIALIZEinstanceShow Rational #-}showsPrec :: Int -> Ratio a -> ShowS
showsPrec Int
p (a
x :% a
y )=Bool -> ShowS -> ShowS
showParen (Int
p Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
> Int
ratioPrec )(ShowS -> ShowS) -> ShowS -> ShowS
forall a b. (a -> b) -> a -> b
$ Int -> a -> ShowS
forall a. Show a => Int -> a -> ShowS
showsPrec Int
ratioPrec1 a
x ShowS -> ShowS -> ShowS
forall b c a. (b -> c) -> (a -> b) -> a -> c
. [Char] -> ShowS
showString [Char]
" % "ShowS -> ShowS -> ShowS
forall b c a. (b -> c) -> (a -> b) -> a -> c
. -- H98 report has spaces round the %-- but we removed them [May 04]-- and added them again for consistency with-- Haskell 98 [Sep 08, #1920]Int -> a -> ShowS
forall a. Show a => Int -> a -> ShowS
showsPrec Int
ratioPrec1 a
y -- | @since base-2.0.1instance(Integral a )=>Enum (Ratio a )where{-# SPECIALIZEinstanceEnum Rational #-}succ :: Ratio a -> Ratio a
succ Ratio a
x =Ratio a
x Ratio a -> Ratio a -> Ratio a
forall a. Num a => a -> a -> a
+ Ratio a
1pred :: Ratio a -> Ratio a
pred Ratio a
x =Ratio a
x Ratio a -> Ratio a -> Ratio a
forall a. Num a => a -> a -> a
- Ratio a
1toEnum :: Int -> Ratio a
toEnum Int
n =Int -> a
forall a b. (Integral a, Num b) => a -> b
fromIntegral Int
n a -> a -> Ratio a
forall a. a -> a -> Ratio a
:% a
1fromEnum :: Ratio a -> Int
fromEnum =Integer -> Int
forall a. Num a => Integer -> a
fromInteger (Integer -> Int) -> (Ratio a -> Integer) -> Ratio a -> Int
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Ratio a -> Integer
forall b. Integral b => Ratio a -> b
forall a b. (RealFrac a, Integral b) => a -> b
truncate enumFrom :: Ratio a -> [Ratio a]
enumFrom =Ratio a -> [Ratio a]
forall a. Fractional a => a -> [a]
numericEnumFrom enumFromThen :: Ratio a -> Ratio a -> [Ratio a]
enumFromThen =Ratio a -> Ratio a -> [Ratio a]
forall a. Fractional a => a -> a -> [a]
numericEnumFromThen enumFromTo :: Ratio a -> Ratio a -> [Ratio a]
enumFromTo =Ratio a -> Ratio a -> [Ratio a]
forall a. (Ord a, Fractional a) => a -> a -> [a]
numericEnumFromTo enumFromThenTo :: Ratio a -> Ratio a -> Ratio a -> [Ratio a]
enumFromThenTo =Ratio a -> Ratio a -> Ratio a -> [Ratio a]
forall a. (Ord a, Fractional a) => a -> a -> a -> [a]
numericEnumFromThenTo ---------------------------------------------------------------- Coercions---------------------------------------------------------------- | General coercion from 'Integral' types.---- WARNING: This function performs silent truncation if the result type is not-- at least as big as the argument's type.{-# INLINEfromIntegral #-}-- Inlined to allow built-in rules to match.-- See Note [Optimising conversions between numeric types]-- in GHC.Core.Opt.ConstantFoldfromIntegral ::(Integral a ,Num b )=>a ->b fromIntegral :: forall a b. (Integral a, Num b) => a -> b
fromIntegral =Integer -> b
forall a. Num a => Integer -> a
fromInteger (Integer -> b) -> (a -> Integer) -> a -> b
forall b c a. (b -> c) -> (a -> b) -> a -> c
. a -> Integer
forall a. Integral a => a -> Integer
toInteger -- | General coercion to 'Fractional' types.---- WARNING: This function goes through the 'Rational' type, which does not have values for 'NaN' for example.-- This means it does not round-trip.---- For 'Double' it also behaves differently with or without -O0:---- > Prelude> realToFrac nan -- With -O0-- > -Infinity-- > Prelude> realToFrac nan-- > NaNrealToFrac ::(Real a ,Fractional b )=>a ->b {-# NOINLINE[1]realToFrac #-}-- See Note [Allow time for type-specialisation rules to fire]-- These rule actually appear in other modules, e.g. GHC.Internal.FloatrealToFrac :: forall a b. (Real a, Fractional b) => a -> b
realToFrac =Rational -> b
forall a. Fractional a => Rational -> a
fromRational (Rational -> b) -> (a -> Rational) -> a -> b
forall b c a. (b -> c) -> (a -> b) -> a -> c
. a -> Rational
forall a. Real a => a -> Rational
toRational ---------------------------------------------------------------- Overloaded numeric functions---------------------------------------------------------------- | Converts a possibly-negative 'Real' value to a string.showSigned ::(Real a )=>(a ->ShowS )-- ^ a function that can show unsigned values->Int -- ^ the precedence of the enclosing context->a -- ^ the value to show->ShowS showSigned :: forall a. Real a => (a -> ShowS) -> Int -> a -> ShowS
showSigned a -> ShowS
showPos Int
p a
x |a
x a -> a -> Bool
forall a. Ord a => a -> a -> Bool
< a
0=Bool -> ShowS -> ShowS
showParen (Int
p Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
> Int
6)(Char -> ShowS
showChar Char
'-'ShowS -> ShowS -> ShowS
forall b c a. (b -> c) -> (a -> b) -> a -> c
. a -> ShowS
showPos (-a
x ))|Bool
otherwise =a -> ShowS
showPos a
x even ,odd ::(Integral a )=>a ->Bool even :: forall a. Integral a => a -> Bool
even a
n =a
n a -> a -> a
forall a. Integral a => a -> a -> a
`rem` a
2a -> a -> Bool
forall a. Eq a => a -> a -> Bool
== a
0odd :: forall a. Integral a => a -> Bool
odd =Bool -> Bool
not (Bool -> Bool) -> (a -> Bool) -> a -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. a -> Bool
forall a. Integral a => a -> Bool
even {-# INLINABLEeven #-}{-# INLINABLEodd #-}--------------------------------------------------------- | raise a number to a non-negative integral power{-# INLINE[1](^)#-}-- See Note [Inlining (^)](^) ::(Num a ,Integral b )=>a ->b ->a a
x0 ^ :: forall a b. (Num a, Integral b) => a -> b -> a
^ b
y0 |b
y0 b -> b -> Bool
forall a. Ord a => a -> a -> Bool
< b
0=[Char] -> a
forall a. [Char] -> a
errorWithoutStackTrace [Char]
"Negative exponent"|b
y0 b -> b -> Bool
forall a. Eq a => a -> a -> Bool
== b
0=a
1|Bool
otherwise =a -> b -> a
forall a b. (Num a, Integral b) => a -> b -> a
powImpl a
x0 b
y0 {-# SPECIALISEpowImpl ::Integer ->Integer ->Integer ,Integer ->Int ->Integer ,Int ->Int ->Int #-}{-# INLINABLEpowImpl #-}-- See Note [Inlining (^)]powImpl ::(Num a ,Integral b )=>a ->b ->a -- powImpl : x0 ^ y0 = (x ^ y)powImpl :: forall a b. (Num a, Integral b) => a -> b -> a
powImpl a
x b
y |b -> Bool
forall a. Integral a => a -> Bool
even b
y =a -> b -> a
forall a b. (Num a, Integral b) => a -> b -> a
powImpl (a
x a -> a -> a
forall a. Num a => a -> a -> a
* a
x )(b
y b -> b -> b
forall a. Integral a => a -> a -> a
`quot` b
2)|b
y b -> b -> Bool
forall a. Eq a => a -> a -> Bool
== b
1=a
x |Bool
otherwise =a -> b -> a -> a
forall a b. (Num a, Integral b) => a -> b -> a -> a
powImplAcc (a
x a -> a -> a
forall a. Num a => a -> a -> a
* a
x )(b
y b -> b -> b
forall a. Integral a => a -> a -> a
`quot` b
2)a
x -- See Note [Half of y - 1]{-# SPECIALISEpowImplAcc ::Integer ->Integer ->Integer ->Integer ,Integer ->Int ->Integer ->Integer ,Int ->Int ->Int ->Int #-}{-# INLINABLEpowImplAcc #-}-- See Note [Inlining (^)]powImplAcc ::(Num a ,Integral b )=>a ->b ->a ->a -- powImplAcc : x0 ^ y0 = (x ^ y) * zpowImplAcc :: forall a b. (Num a, Integral b) => a -> b -> a -> a
powImplAcc a
x b
y a
z |b -> Bool
forall a. Integral a => a -> Bool
even b
y =a -> b -> a -> a
forall a b. (Num a, Integral b) => a -> b -> a -> a
powImplAcc (a
x a -> a -> a
forall a. Num a => a -> a -> a
* a
x )(b
y b -> b -> b
forall a. Integral a => a -> a -> a
`quot` b
2)a
z |b
y b -> b -> Bool
forall a. Eq a => a -> a -> Bool
== b
1=a
x a -> a -> a
forall a. Num a => a -> a -> a
* a
z |Bool
otherwise =a -> b -> a -> a
forall a b. (Num a, Integral b) => a -> b -> a -> a
powImplAcc (a
x a -> a -> a
forall a. Num a => a -> a -> a
* a
x )(b
y b -> b -> b
forall a. Integral a => a -> a -> a
`quot` b
2)(a
x a -> a -> a
forall a. Num a => a -> a -> a
* a
z )-- See Note [Half of y - 1]-- | raise a number to an integral power(^^) ::(Fractional a ,Integral b )=>a ->b ->a {-# INLINE[1](^^)#-}-- See Note [Inlining (^)a
x ^^ :: forall a b. (Fractional a, Integral b) => a -> b -> a
^^ b
n =ifb
n b -> b -> Bool
forall a. Ord a => a -> a -> Bool
>= b
0thena
x a -> b -> a
forall a b. (Num a, Integral b) => a -> b -> a
^ b
n elsea -> a
forall a. Fractional a => a -> a
recip (a
x a -> b -> a
forall a b. (Num a, Integral b) => a -> b -> a
^ (b -> b
forall a. Num a => a -> a
negate b
n )){- Note [Half of y - 1]
~~~~~~~~~~~~~~~~~~~~~~~~
Since y is guaranteed to be odd and positive here,
half of y - 1 can be computed as y `quot` 2, optimising subtraction away.
Note [Inlining (^)]
~~~~~~~~~~~~~~~~~~~
We want to achieve the following:
* Noting that (^) is lazy in its first argument, we'd still like to avoid allocating a box for
 the first argument. Example: nofib/imaginary/x2n1, which makes many calls to (^) with
 different first arguments each time.
 Solution: split (^) into a small INLINE wrapper that tests the second arg, which then calls the
 strict (and recursive) auxiliary function `powImpl`.
* Don't inline (^) too early because we want rewrite rules to optimise calls to (^) with
 small exponents. See Note [Powers with small exponent].
 Solution: use INLINE[1] to delay inlining to phase 1, giving the rewrite rules time to fire.
* (^) is overloaded on two different type parameters. We want to specialise.
 Solution: make `powImpl` (and its friend `powImplAcc`) INLINEABLE, so they can be specialised
 at call sites. Also give them some common specialisations right here, to avoid duplicating
 that specialisation in clients.
Specialisation can make a huge difference for repeated calls, because of
constants which would otherwise be calculated repeatedly and unboxing of
arguments.
Why not make (^) strict in `x0` with a bang and make it INLINABLE? Well, because
it is futile: Being strict in the `Complex Double` pair won't be enough to unbox
the `Double`s anyway. Even after deep specisalisation, we will only unbox the
`Double`s when we inline (^), because (^) remains lazy in the `Double` fields.
Given that (^) must always inline to yield good code, we can just as well mark
it as such.
A small note on perf: Currently the fromInteger calls from the desugaring of
literals are not floated because we get
 \d1 d2 x y -> blah
after the gentle round of simplification.
Note [Powers with small exponent]
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
For small exponents, (^) is inefficient compared to manually
expanding the multiplication tree (see #5237).
Here, rules for the most common exponent types are given.
The range of exponents for which rules are given is quite
arbitrary and kept small to not unduly increase the number of rules.
0 and 1 are excluded based on the assumption that nobody would
write x^0 or x^1 in code and the cases where an exponent could
be statically resolved to 0 or 1 are rare.
It might be desirable to have corresponding rules also for
exponents of other types (e. g., Word), but it's doubtful they
would fire, since the exponents of other types tend to get
floated out before the rule has a chance to fire.
Also desirable would be rules for (^^), but I haven't managed
to get those to fire.
Note: Since (*) is not associative for some types (e.g. Double), it is
important that the RHS of these rules produce the same bracketing as
would the actual implementation of (^). A mismatch here led to #19569.
-}-- See Note [Powers with small exponent]{-# RULES"^2/Int"forallx .x ^ (2::Int )=x * x "^3/Int"forallx .x ^ (3::Int )=x * x * x "^4/Int"forallx .x ^ (4::Int )=letu =x * x inu * u "^5/Int"forallx .x ^ (5::Int )=letu =x * x inu * u * x "^2/Integer"forallx .x ^ (2::Integer )=x * x "^3/Integer"forallx .x ^ (3::Integer )=x * x * x "^4/Integer"forallx .x ^ (4::Integer )=letu =x * x inu * u "^5/Integer"forallx .x ^ (5::Integer )=letu =x * x inu * u * x #-}--------------------------------------------------------- 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"(^)=(^%^)#-}(^%^) ::Integral a =>Rational ->a ->Rational (Integer
n :% Integer
d )^%^ :: forall a. Integral a => Rational -> a -> Rational
^%^ a
e |a
e a -> a -> Bool
forall a. Ord a => a -> a -> Bool
< a
0=[Char] -> Rational
forall a. [Char] -> a
errorWithoutStackTrace [Char]
"Negative exponent"|a
e a -> a -> Bool
forall a. Eq a => a -> a -> Bool
== a
0=Integer
1Integer -> Integer -> Rational
forall a. a -> a -> Ratio a
:% Integer
1|Bool
otherwise =(Integer
n Integer -> a -> Integer
forall a b. (Num a, Integral b) => a -> b -> a
^ a
e )Integer -> Integer -> Rational
forall a. a -> a -> Ratio a
:% (Integer
d Integer -> a -> Integer
forall a b. (Num a, Integral b) => a -> b -> a
^ a
e )-- Special version of (^^) for Rational base{-# RULES"(^^)/Rational"(^^)=(^^%^^)#-}(^^%^^) ::Integral a =>Rational ->a ->Rational (Integer
n :% Integer
d )^^%^^ :: forall a. Integral a => Rational -> a -> Rational
^^%^^ a
e |a
e a -> a -> Bool
forall a. Ord a => a -> a -> Bool
> a
0=(Integer
n Integer -> a -> Integer
forall a b. (Num a, Integral b) => a -> b -> a
^ a
e )Integer -> Integer -> Rational
forall a. a -> a -> Ratio a
:% (Integer
d Integer -> a -> Integer
forall a b. (Num a, Integral b) => a -> b -> a
^ a
e )|a
e a -> a -> Bool
forall a. Eq a => a -> a -> Bool
== a
0=Integer
1Integer -> Integer -> Rational
forall a. a -> a -> Ratio a
:% Integer
1|Integer
n Integer -> Integer -> Bool
forall a. Ord a => a -> a -> Bool
> Integer
0=(Integer
d Integer -> a -> Integer
forall a b. (Num a, Integral b) => a -> b -> a
^ (a -> a
forall a. Num a => a -> a
negate a
e ))Integer -> Integer -> Rational
forall a. a -> a -> Ratio a
:% (Integer
n Integer -> a -> Integer
forall a b. (Num a, Integral b) => a -> b -> a
^ (a -> a
forall a. Num a => a -> a
negate a
e ))|Integer
n Integer -> Integer -> Bool
forall a. Eq a => a -> a -> Bool
== Integer
0=Rational
forall a. a
ratioZeroDenominatorError |Bool
otherwise =letnn :: Integer
nn =Integer
d Integer -> a -> Integer
forall a b. (Num a, Integral b) => a -> b -> a
^ (a -> a
forall a. Num a => a -> a
negate a
e )dd :: Integer
dd =(Integer -> Integer
forall a. Num a => a -> a
negate Integer
n )Integer -> a -> Integer
forall a b. (Num a, Integral b) => a -> b -> a
^ (a -> a
forall a. Num a => a -> a
negate a
e )inifa -> Bool
forall a. Integral a => a -> Bool
even a
e then(Integer
nn Integer -> Integer -> Rational
forall a. a -> a -> Ratio a
:% Integer
dd )else(Integer -> Integer
forall a. Num a => a -> a
negate Integer
nn Integer -> Integer -> Rational
forall a. a -> a -> Ratio a
:% Integer
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 ::(Integral a )=>a ->a ->a {-# SPECIALISEgcd ::Int ->Int ->Int #-}{-# SPECIALISEgcd ::Word ->Word ->Word #-}{-# NOINLINE[2]gcd #-}-- See Note [Allow time for type-specialisation rules to fire]gcd :: forall a. Integral a => a -> a -> a
gcd a
x a
y =a -> a -> a
forall a. Integral a => a -> a -> a
gcd' (a -> a
forall a. Num a => a -> a
abs a
x )(a -> a
forall a. Num a => a -> a
abs a
y )wheregcd' :: t -> t -> t
gcd' t
a t
0=t
a gcd' t
a t
b =t -> t -> t
gcd' t
b (t
a t -> t -> t
forall a. Integral a => a -> a -> a
`rem` t
b )-- | @'lcm' x y@ is the smallest positive integer that both @x@ and @y@ divide.lcm ::(Integral a )=>a ->a ->a {-# SPECIALISElcm ::Int ->Int ->Int #-}{-# SPECIALISElcm ::Word ->Word ->Word #-}{-# NOINLINE[2]lcm #-}-- See Note [Allow time for type-specialisation rules to fire]lcm :: forall a. Integral a => a -> a -> a
lcm a
_a
0=a
0lcm a
0a
_=a
0lcm a
x a
y =a -> a
forall a. Num a => a -> a
abs ((a
x a -> a -> a
forall a. Integral a => a -> a -> a
`quot` (a -> a -> a
forall a. Integral a => a -> a -> a
gcd a
x a
y ))a -> a -> a
forall a. Num a => a -> a -> a
* a
y ){-# RULES"gcd/Integer->Integer->Integer"gcd =integerGcd "lcm/Integer->Integer->Integer"lcm =integerLcm "gcd/Natural->Natural->Natural"gcd =naturalGcd "lcm/Natural->Natural->Natural"lcm =naturalLcm #-}{-# RULES"gcd/Int->Int->Int"gcd =gcdInt "gcd/Word->Word->Word"gcd =gcdWord #-}-- INLINE pragma: see Note [Inline Enum method helpers] in GHC.Internal.Enum{-# INLINEintegralEnumFrom #-}integralEnumFrom ::(Integral a ,Bounded a )=>a ->[a ]integralEnumFrom :: forall a. (Integral a, Bounded a) => a -> [a]
integralEnumFrom a
n =(Integer -> a) -> [Integer] -> [a]
forall a b. (a -> b) -> [a] -> [b]
map Integer -> a
forall a. Num a => Integer -> a
fromInteger [a -> Integer
forall a. Integral a => a -> Integer
toInteger a
n ..a -> Integer
forall a. Integral a => a -> Integer
toInteger (a
forall a. Bounded a => a
maxBound a -> a -> a
forall a. a -> a -> a
`asTypeOf` a
n )]-- INLINE pragma: see Note [Inline Enum method helpers] in GHC.Internal.Enum{-# INLINEintegralEnumFromThen #-}integralEnumFromThen ::(Integral a ,Bounded a )=>a ->a ->[a ]integralEnumFromThen :: forall a. (Integral a, Bounded a) => a -> a -> [a]
integralEnumFromThen a
n1 a
n2 |Integer
i_n2 Integer -> Integer -> Bool
forall a. Ord a => a -> a -> Bool
>= Integer
i_n1 =(Integer -> a) -> [Integer] -> [a]
forall a b. (a -> b) -> [a] -> [b]
map Integer -> a
forall a. Num a => Integer -> a
fromInteger [Integer
i_n1 ,Integer
i_n2 ..a -> Integer
forall a. Integral a => a -> Integer
toInteger (a
forall a. Bounded a => a
maxBound a -> a -> a
forall a. a -> a -> a
`asTypeOf` a
n1 )]|Bool
otherwise =(Integer -> a) -> [Integer] -> [a]
forall a b. (a -> b) -> [a] -> [b]
map Integer -> a
forall a. Num a => Integer -> a
fromInteger [Integer
i_n1 ,Integer
i_n2 ..a -> Integer
forall a. Integral a => a -> Integer
toInteger (a
forall a. Bounded a => a
minBound a -> a -> a
forall a. a -> a -> a
`asTypeOf` a
n1 )]wherei_n1 :: Integer
i_n1 =a -> Integer
forall a. Integral a => a -> Integer
toInteger a
n1 i_n2 :: Integer
i_n2 =a -> Integer
forall a. Integral a => a -> Integer
toInteger a
n2 -- INLINE pragma: see Note [Inline Enum method helpers] in GHC.Internal.Enum{-# INLINEintegralEnumFromTo #-}integralEnumFromTo ::Integral a =>a ->a ->[a ]integralEnumFromTo :: forall a. Integral a => a -> a -> [a]
integralEnumFromTo a
n a
m =(Integer -> a) -> [Integer] -> [a]
forall a b. (a -> b) -> [a] -> [b]
map Integer -> a
forall a. Num a => Integer -> a
fromInteger [a -> Integer
forall a. Integral a => a -> Integer
toInteger a
n ..a -> Integer
forall a. Integral a => a -> Integer
toInteger a
m ]-- INLINE pragma: see Note [Inline Enum method helpers] in GHC.Internal.Enum{-# INLINEintegralEnumFromThenTo #-}integralEnumFromThenTo ::Integral a =>a ->a ->a ->[a ]integralEnumFromThenTo :: forall a. Integral a => a -> a -> a -> [a]
integralEnumFromThenTo a
n1 a
n2 a
m =(Integer -> a) -> [Integer] -> [a]
forall a b. (a -> b) -> [a] -> [b]
map Integer -> a
forall a. Num a => Integer -> a
fromInteger [a -> Integer
forall a. Integral a => a -> Integer
toInteger a
n1 ,a -> Integer
forall a. Integral a => a -> Integer
toInteger a
n2 ..a -> Integer
forall a. Integral a => a -> Integer
toInteger a
m ]-- mkRational related codedataFractionalExponentBase =Base2 |Base10 deriving(Int -> FractionalExponentBase -> ShowS
[FractionalExponentBase] -> ShowS
FractionalExponentBase -> [Char]
(Int -> FractionalExponentBase -> ShowS)
-> (FractionalExponentBase -> [Char])
-> ([FractionalExponentBase] -> ShowS)
-> Show FractionalExponentBase
forall a.
(Int -> a -> ShowS) -> (a -> [Char]) -> ([a] -> ShowS) -> Show a
$cshowsPrec :: Int -> FractionalExponentBase -> ShowS
showsPrec :: Int -> FractionalExponentBase -> ShowS
$cshow :: FractionalExponentBase -> [Char]
show :: FractionalExponentBase -> [Char]
$cshowList :: [FractionalExponentBase] -> ShowS
showList :: [FractionalExponentBase] -> ShowS
Show )mkRationalBase2 ::Rational ->Integer ->Rational mkRationalBase2 :: Rational -> Integer -> Rational
mkRationalBase2 Rational
r Integer
e =Rational -> Integer -> FractionalExponentBase -> Rational
mkRationalWithExponentBase Rational
r Integer
e FractionalExponentBase
Base2 mkRationalBase10 ::Rational ->Integer ->Rational mkRationalBase10 :: Rational -> Integer -> Rational
mkRationalBase10 Rational
r Integer
e =Rational -> Integer -> FractionalExponentBase -> Rational
mkRationalWithExponentBase Rational
r Integer
e FractionalExponentBase
Base10 mkRationalWithExponentBase ::Rational ->Integer ->FractionalExponentBase ->Rational mkRationalWithExponentBase :: Rational -> Integer -> FractionalExponentBase -> Rational
mkRationalWithExponentBase Rational
r Integer
e FractionalExponentBase
feb =Rational
r Rational -> Rational -> Rational
forall a. Num a => a -> a -> a
* (Rational
eb Rational -> Integer -> Rational
forall a b. (Fractional a, Integral b) => a -> b -> a
^^ Integer
e )-- See Note [fractional exponent bases] for why only these bases.whereeb :: Rational
eb =caseFractionalExponentBase
feb ofFractionalExponentBase
Base2 ->Rational
2;FractionalExponentBase
Base10 ->Rational
10