Algebra.IntegralDomain

Class

class C a => C a where

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)

Minimal complete definition

divMod | div, mod

Methods

div, mod :: a -> a -> a infixl 7 `div`, `mod`

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

Instances

C Int

Methods

div :: Int -> Int -> Int

mod :: Int -> Int -> Int

divMod :: Int -> Int -> (Int, Int)

C Int8

Methods

div :: Int8 -> Int8 -> Int8

mod :: Int8 -> Int8 -> Int8

divMod :: Int8 -> Int8 -> (Int8, Int8)

C Int16

Methods

div :: Int16 -> Int16 -> Int16

mod :: Int16 -> Int16 -> Int16

divMod :: Int16 -> Int16 -> (Int16, Int16)

C Int32

Methods

div :: Int32 -> Int32 -> Int32

mod :: Int32 -> Int32 -> Int32

divMod :: Int32 -> Int32 -> (Int32, Int32)

C Int64

Methods

div :: Int64 -> Int64 -> Int64

mod :: Int64 -> Int64 -> Int64

divMod :: Int64 -> Int64 -> (Int64, Int64)

C Integer

Methods

div :: Integer -> Integer -> Integer

mod :: Integer -> Integer -> Integer

divMod :: Integer -> Integer -> (Integer, Integer)

C Word

Methods

div :: Word -> Word -> Word

mod :: Word -> Word -> Word

divMod :: Word -> Word -> (Word, Word)

C Word8

Methods

div :: Word8 -> Word8 -> Word8

mod :: Word8 -> Word8 -> Word8

divMod :: Word8 -> Word8 -> (Word8, Word8)

C Word16

Methods

div :: Word16 -> Word16 -> Word16

mod :: Word16 -> Word16 -> Word16

divMod :: Word16 -> Word16 -> (Word16, Word16)

C Word32

Methods

div :: Word32 -> Word32 -> Word32

mod :: Word32 -> Word32 -> Word32

divMod :: Word32 -> Word32 -> (Word32, Word32)

C Word64

Methods

div :: Word64 -> Word64 -> Word64

mod :: Word64 -> Word64 -> Word64

divMod :: Word64 -> Word64 -> (Word64, Word64)

C T

Methods

div :: T -> T -> T

mod :: T -> T -> T

divMod :: T -> T -> (T, T)

Integral a => C (T a)

Methods

div :: T a -> T a -> T a

mod :: T a -> T a -> T a

divMod :: T a -> T a -> (T a, 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.

Methods

div :: T a -> T a -> T a

mod :: T a -> T a -> T a

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

(C a, C a) => C (T a)

Methods

div :: T a -> T a -> T a

mod :: T a -> T a -> T a

divMod :: T a -> T a -> (T a, 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 [2].

Methods

div :: T a -> T a -> T a

mod :: T a -> T a -> T a

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

C a => C (T a)

Methods

div :: T a -> T a -> T a

mod :: T a -> T a -> T a

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

C a => C (T a)

Methods

div :: T a -> T a -> T a

mod :: T a -> T a -> T a

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

div, mod :: C a => a -> a -> a infixl 7 `div`, `mod`

div, mod :: C a => a -> a -> a infixl 7 `mod`, `div`

divMod :: C a => a -> a -> (a, a)

Derived functions

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

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

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

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

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

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

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

Deprecated: use divChecked instead

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

even :: (C a, C a) => a -> Bool

odd :: (C a, C a) => a -> Bool

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

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

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

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]

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]

Properties

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

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

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

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

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

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

propZeroRepresentative :: (Eq a, C a, C a) => a -> Property

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