numeric-prelude-0.4.2: An experimental alternative hierarchy of numeric type classes

Algebra.RealRing

Synopsis

# Documentation

class (C a, Ord a) => C a where Source

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.

Minimal complete definition

Methods

splitFraction :: C b => a -> (b, a) Source

fraction :: a -> a Source

ceiling, floor :: C b => a -> b Source

truncate :: C b => a -> b Source

round :: C b => a -> b Source

Instances

 C Double C Float C Int C Integer C T C T (C a, C a) => C (T a) (C a, C a) => C (T a) RealFrac a => C (T a) C a => C (T a)

roundSimple :: (C a, C b) => a -> b Source

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.

fastSplitFraction :: (RealFrac a, C a, C b) => (a -> Int) -> (Int -> a) -> a -> (b, a) Source

fixSplitFraction :: (C a, C b, Ord a) => (b, a) -> (b, a) Source

fixFraction :: (C a, Ord a) => a -> a Source

splitFractionInt :: (C a, Ord a) => (a -> Int) -> (Int -> a) -> a -> (Int, a) Source

floorInt :: (C a, Ord a) => (a -> Int) -> (Int -> a) -> a -> Int Source

ceilingInt :: (C a, Ord a) => (a -> Int) -> (Int -> a) -> a -> Int Source

roundInt :: (C a, Ord a) => (a -> Int) -> (Int -> a) -> a -> Int Source

roundSimpleInt :: (C a, C a, Ord a) => (a -> Int) -> (Int -> a) -> a -> Int Source

approxRational :: (C a, C a) => a -> a -> Rational Source

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 -> b Source

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 -> b Source

genericTruncate :: (Ord a, C a, C b) => a -> b Source

genericRound :: (Ord a, C a, C b) => a -> b Source

genericFraction :: (Ord a, C a) => a -> a Source

genericSplitFraction :: (Ord a, C a, C b) => a -> (b, a) Source

genericPosFloor :: (Ord a, C a, C b) => a -> b Source

genericPosCeiling :: (Ord a, C a, C b) => a -> b Source

genericHalfPosFloorDigits :: (Ord a, C a, C b) => a -> ((a, b), [Bool]) Source

genericPosRound :: (Ord a, C a, C b) => a -> b Source

genericPosFraction :: (Ord a, C a) => a -> a Source

genericPosSplitFraction :: (Ord a, C a, C b) => a -> (b, a) Source

decisionPosFraction :: (C a, C a) => a -> a Source

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 -> a Source