Algebra.IntegralDomain

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)

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

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

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

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

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.

prop> \n (QC.NonZero m) -> div n m * m == (roundDown n m :: Integer)

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.

prop> \n (QC.NonZero m) -> divUp n m * m == (roundUp n m :: Integer)

prop> \n (QC.Positive m) -> let x = roundDown n m in  n-m < x && x <= (n :: Integer)

prop> \n (QC.NonZero m) -> - roundDown n m == (roundUp (-n) m :: Integer)

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]