Safe Haskell | Safe-Infered |
---|
- class (C a, Ord a) => C a where
- roundSimple :: (C a, C b) => a -> b
- fastSplitFraction :: (RealFrac a, C a, C b) => (a -> Int) -> (Int -> a) -> a -> (b, a)
- fixSplitFraction :: (C a, C b, Ord a) => (b, a) -> (b, a)
- fixFraction :: (C a, Ord a) => a -> a
- splitFractionInt :: (C a, Ord a) => (a -> Int) -> (Int -> a) -> a -> (Int, a)
- floorInt :: (C a, Ord a) => (a -> Int) -> (Int -> a) -> a -> Int
- ceilingInt :: (C a, Ord a) => (a -> Int) -> (Int -> a) -> a -> Int
- roundInt :: (C a, Ord a) => (a -> Int) -> (Int -> a) -> a -> Int
- roundSimpleInt :: (C a, C a, Ord a) => (a -> Int) -> (Int -> a) -> a -> Int
- approxRational :: (C a, C a) => a -> a -> Rational
- powersOfTwo :: C a => [a]
- pairsOfPowersOfTwo :: (C a, C b) => [(a, b)]
- genericFloor :: (Ord a, C a, C b) => a -> b
- genericCeiling :: (Ord a, C a, C b) => a -> b
- genericTruncate :: (Ord a, C a, C b) => a -> b
- genericRound :: (Ord a, C a, C b) => a -> b
- genericFraction :: (Ord a, C a) => a -> a
- genericSplitFraction :: (Ord a, C a, C b) => a -> (b, a)
- genericPosFloor :: (Ord a, C a, C b) => a -> b
- genericPosCeiling :: (Ord a, C a, C b) => a -> b
- genericHalfPosFloorDigits :: (Ord a, C a, C b) => a -> ((a, b), [Bool])
- genericPosRound :: (Ord a, C a, C b) => a -> b
- genericPosFraction :: (Ord a, C a) => a -> a
- genericPosSplitFraction :: (Ord a, C a, C b) => a -> (b, a)
- decisionPosFraction :: (C a, C a) => a -> a
- decisionPosFractionSqrTime :: (C a, C a) => a -> a
Documentation
class (C a, Ord a) => C a whereSource
Minimal complete definition:
splitFraction
or floor
There are probably more laws, but some laws are
splitFraction x === (fromInteger (floor x), fraction x) fromInteger (floor x) + fraction x === x floor x <= x x < floor x + 1 ceiling x - 1 < x x <= ceiling x 0 <= fraction x fraction x < 1
- ceiling x === floor (-x) truncate x === signum x * floor (abs x) ceiling (toRational x) === ceiling x :: Integer truncate (toRational x) === truncate x :: Integer floor (toRational x) === floor x :: Integer
The new function fraction
doesn't return the integer part of the number.
This also removes a type ambiguity if the integer part is not needed.
Many people will associate rounding with fractional numbers,
and thus they are surprised about the superclass being Ring
not Field
.
The reason is that all of these methods can be defined
exclusively with functions from Ord
and Ring
.
The implementations of genericFloor
and other functions demonstrate that.
They implement power-of-two-algorithms
like the one for finding the number of digits of an Integer
in FixedPoint-fractions module.
They are even reasonably efficient.
I am still uncertain whether it was a good idea
to add instances for Integer
and friends,
since calling floor
or fraction
on an integer may well indicate a bug.
The rounding functions are just the identity function
and fraction
is constant zero.
However, I decided to associate our class with Ring
rather than Field
,
after I found myself using repeated subtraction and testing
rather than just calling fraction
,
just in order to get the constraint (Ring a, Ord a)
that was more general than (RealField a)
.
For the results of the rounding functions
we have chosen the constraint Ring
instead of ToInteger
,
since this is more flexible to use,
but it still signals to the user that only integral numbers can be returned.
This is so, because the plain Ring
class only provides
zero
, one
and operations that allow to reach all natural numbers but not more.
As an aside, let me note the similarities
between splitFraction x
and divMod x 1
(if that were defined).
In particular, it might make sense to unify the rounding modes somehow.
The new methods fraction
and splitFraction
differ from properFraction
semantics.
They always round to floor
.
This means that the fraction is always non-negative and
is always smaller than 1.
This is more useful in practice and
can be generalised to more than real numbers.
Since every T
denominator type
supports divMod
,
every T
can provide fraction
and splitFraction
,
e.g. fractions of polynomials.
However the Ring
constraint for the ''integral'' part of splitFraction
is too weak in order to generate polynomials.
After all, I am uncertain whether this would be useful or not.
Can there be a separate class for
fraction
, splitFraction
, floor
and ceiling
since they do not need reals and their ordering?
We might also add a round method, that rounds 0.5 always up or always down. This is much more efficient in inner loops and is acceptable or even preferable for many applications.
roundSimple :: (C a, C b) => a -> bSource
This function rounds to the closest integer.
For fraction x == 0.5
it rounds away from zero.
This function is not the result of an ingenious mathematical insight,
but is simply a kind of rounding that is the fastest
on IEEE floating point architectures.
fixSplitFraction :: (C a, C b, Ord a) => (b, a) -> (b, a)Source
fixFraction :: (C a, Ord a) => a -> aSource
approxRational :: (C a, C a) => a -> a -> RationalSource
TODO: Should be moved to a continued fraction module.
generic implementation of round functions
powersOfTwo :: C a => [a]Source
pairsOfPowersOfTwo :: (C a, C b) => [(a, b)]Source
genericFloor :: (Ord a, C a, C b) => a -> bSource
The generic rounding functions need a number of operations proportional to the number of binary digits of the integer portion. If operations like multiplication with two and comparison need time proportional to the number of binary digits, then the overall rounding requires quadratic time.
genericCeiling :: (Ord a, C a, C b) => a -> bSource
genericTruncate :: (Ord a, C a, C b) => a -> bSource
genericRound :: (Ord a, C a, C b) => a -> bSource
genericFraction :: (Ord a, C a) => a -> aSource
genericSplitFraction :: (Ord a, C a, C b) => a -> (b, a)Source
genericPosFloor :: (Ord a, C a, C b) => a -> bSource
genericPosCeiling :: (Ord a, C a, C b) => a -> bSource
genericPosRound :: (Ord a, C a, C b) => a -> bSource
genericPosFraction :: (Ord a, C a) => a -> aSource
genericPosSplitFraction :: (Ord a, C a, C b) => a -> (b, a)Source
decisionPosFraction :: (C a, C a) => a -> aSource
Needs linear time with respect to the number of digits.
This and other functions using OrderDecision
like floor
where argument and result are the same
may be moved to a new module.
decisionPosFractionSqrTime :: (C a, C a) => a -> aSource