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

Algebra.IntegralDomain

Contents

Synopsis

# Class

class C a => C a whereSource

`IntegralDomain` corresponds to a commutative ring, where `a mod b` picks a canonical element of the equivalence class of `a` in the ideal generated by `b`. `div` and `mod` satisfy the laws

```                         a * b === b * a
(a `div` b) * b + (a `mod` b) === a
(a+k*b) `mod` b === a `mod` b
0 `mod` b === 0
```

Typical examples of `IntegralDomain` include integers and polynomials over a field. Note that for a field, there is a canonical instance defined by the above rules; e.g.,

``` instance IntegralDomain.C Rational where
divMod a b =
if isZero b
then (undefined,a)
else (a\/b,0)
```

It shall be noted, that `div`, `mod`, `divMod` have a parameter order which is unfortunate for partial application. But it is adapted to mathematical conventions, where the operators are used in infix notation.

Minimal definition: `divMod` or (`div` and `mod`)

Methods

div, mod :: a -> a -> aSource

divMod :: a -> a -> (a, a)Source

Instances

 C Int C Int8 C Int16 C Int32 C Int64 C Integer C Word C Word8 C Word16 C Word32 C Word64 C T (Ord a, C a) => C (T a) (C a, C a) => C (T a) The `C` instance is intensionally built from the `C` structure of the polynomial coefficients. If we would use `Integral.C a` superclass, then the Euclidean algorithm could not determine the greatest common divisor of e.g. `[1,1]` and ``. (C a, C a) => C (T a) C a => C (T a) Integral a => C (T a) C a => C (T a) (Ord a, C a, C a) => C (T a) `divMod` is implemented in terms of `divModStrict`. If it is needed we could also provide a function that accesses the divisor first in a lazy way and then uses a strict divisor for subsequent rounds of the subtraction loop. This way we can handle the cases "dividend smaller than divisor" and "dividend greater than divisor" in a lazy and efficient way. However changing the way of operation within one number is also not nice.

# Derived functions

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

Allows division by zero. If the divisor is zero, then the dividend is returned as remainder.

divides :: (C a, C a) => a -> a -> BoolSource

sameResidueClass :: (C a, C a) => a -> a -> a -> BoolSource

divChecked, safeDiv :: (C a, C a) => a -> a -> aSource

Returns the result of the division, if divisible. Otherwise undefined.

even, odd :: (C a, C a) => a -> BoolSource

divUp :: C a => a -> a -> aSource

`divUp n m` is similar to `div` but it rounds up the quotient, such that `divUp n m * m = roundUp n m`.

roundDown :: C a => a -> a -> aSource

`roundDown n m` rounds `n` down to the next multiple of `m`. That is, `roundDown n m` is the greatest multiple of `m` that is at most `n`. The parameter order is consistent with `div` and friends, but maybe not useful for partial application.

roundUp :: C a => a -> a -> aSource

`roundUp n m` rounds `n` up to the next multiple of `m`. That is, `roundUp n m` is the greatest multiple of `m` that is at most `n`.

# Algorithms

decomposeVarPositional :: (C a, C a) => [a] -> a -> [a]Source

`decomposeVarPositional [b0,b1,b2,...] x` decomposes `x` into a positional representation with mixed bases `x0 + b0*(x1 + b1*(x2 + b2*x3))` E.g. `decomposeVarPositional (repeat 10) 123 == [3,2,1]`

decomposeVarPositionalInf :: C a => [a] -> a -> [a]Source

# Properties

propInverse :: (Eq a, C a, C a) => a -> a -> PropertySource

propMultipleDiv :: (Eq a, C a, C a) => a -> a -> PropertySource

propMultipleMod :: (Eq a, C a, C a) => a -> a -> PropertySource

propProjectAddition :: (Eq a, C a, C a) => a -> a -> a -> PropertySource

propProjectMultiplication :: (Eq a, C a, C a) => a -> a -> a -> PropertySource

propUniqueRepresentative :: (Eq a, C a, C a) => a -> a -> a -> PropertySource

propSameResidueClass :: (Eq a, C a, C a) => a -> a -> a -> PropertySource