Module

# Data.EuclideanRing

Package
prelude
Repository
purerl/purescript-prelude

### #EuclideanRingSource

``class (CommutativeRing a) <= EuclideanRing a  where``

The `EuclideanRing` class is for commutative rings that support division. The mathematical structure this class is based on is sometimes also called a Euclidean domain.

Instances must satisfy the following laws in addition to the `Ring` laws:

• Integral domain: `one /= zero`, and if `a` and `b` are both nonzero then so is their product `a * b`
• Euclidean function `degree`:
• Nonnegativity: For all nonzero `a`, `degree a >= 0`
• Quotient/remainder: For all `a` and `b`, where `b` is nonzero, let `q = a / b` and `r = a `mod` b`; then `a = q*b + r`, and also either `r = zero` or `degree r < degree b`
• Submultiplicative euclidean function:
• For all nonzero `a` and `b`, `degree a <= degree (a * b)`

The behaviour of division by `zero` is unconstrained by these laws, meaning that individual instances are free to choose how to behave in this case. Similarly, there are no restrictions on what the result of `degree zero` is; it doesn't make sense to ask for `degree zero` in the same way that it doesn't make sense to divide by `zero`, so again, individual instances may choose how to handle this case.

For any `EuclideanRing` which is also a `Field`, one valid choice for `degree` is simply `const 1`. In fact, unless there's a specific reason not to, `Field` types should normally use this definition of `degree`.

The `EuclideanRing Int` instance is one of the most commonly used `EuclideanRing` instances and deserves a little more discussion. In particular, there are a few different sensible law-abiding implementations to choose from, with slightly different behaviour in the presence of negative dividends or divisors. The most common definitions are "truncating" division, where the result of `a / b` is rounded towards 0, and "Knuthian" or "flooring" division, where the result of `a / b` is rounded towards negative infinity. A slightly less common, but arguably more useful, option is "Euclidean" division, which is defined so as to ensure that `a `mod` b` is always nonnegative. With Euclidean division, `a / b` rounds towards negative infinity if the divisor is positive, and towards positive infinity if the divisor is negative. Note that all three definitions are identical if we restrict our attention to nonnegative dividends and divisors.

In versions 1.x, 2.x, and 3.x of the Prelude, the `EuclideanRing Int` instance used truncating division. As of 4.x, the `EuclideanRing Int` instance uses Euclidean division. Additional functions `quot` and `rem` are supplied if truncating division is desired.

#### Members

• `degree :: a -> Int`
• `div :: a -> a -> a`
• `mod :: a -> a -> a`

#### Instances

• `EuclideanRing Int`
• `EuclideanRing Number`

### #(/)Source

Operator alias for Data.EuclideanRing.div (left-associative / precedence 7)

### #gcdSource

``gcd :: forall a. Eq a => EuclideanRing a => a -> a -> a``

The greatest common divisor of two values.

### #lcmSource

``lcm :: forall a. Eq a => EuclideanRing a => a -> a -> a``

The least common multiple of two values.

## Re-exports from Data.CommutativeRing

### #CommutativeRingSource

``class (Ring a) <= CommutativeRing a ``

The `CommutativeRing` class is for rings where multiplication is commutative.

Instances must satisfy the following law in addition to the `Ring` laws:

• Commutative multiplication: `a * b = b * a`

#### Instances

• `CommutativeRing Int`
• `CommutativeRing Number`
• `CommutativeRing Unit`
• `(CommutativeRing b) => CommutativeRing (a -> b)`
• `(RowToList row list, CommutativeRingRecord list row row) => CommutativeRing (Record row)`

## Re-exports from Data.Ring

### #RingSource

``class (Semiring a) <= Ring a  where``

The `Ring` class is for types that support addition, multiplication, and subtraction operations.

Instances must satisfy the following law in addition to the `Semiring` laws:

• Additive inverse: `a - a = (zero - a) + a = zero`

#### Members

• `sub :: a -> a -> a`

#### Instances

• `Ring Int`
• `Ring Number`
• `Ring Unit`
• `(Ring b) => Ring (a -> b)`
• `(RowToList row list, RingRecord list row row) => Ring (Record row)`

### #(-)Source

Operator alias for Data.Ring.sub (left-associative / precedence 6)

## Re-exports from Data.Semiring

### #SemiringSource

``class Semiring a  where``

The `Semiring` class is for types that support an addition and multiplication operation.

Instances must satisfy the following laws:

• Associativity: `(a + b) + c = a + (b + c)`
• Identity: `zero + a = a + zero = a`
• Commutative: `a + b = b + a`
• Monoid under multiplication:
• Associativity: `(a * b) * c = a * (b * c)`
• Identity: `one * a = a * one = a`
• Left distributivity: `a * (b + c) = (a * b) + (a * c)`
• Right distributivity: `(a + b) * c = (a * c) + (b * c)`
• Annihilation: `zero * a = a * zero = zero`

Note: The `Number` and `Int` types are not fully law abiding members of this class hierarchy due to the potential for arithmetic overflows, and in the case of `Number`, the presence of `NaN` and `Infinity` values. The behaviour is unspecified in these cases.

#### Members

• `add :: a -> a -> a`
• `zero :: a`
• `mul :: a -> a -> a`
• `one :: a`

#### Instances

• `Semiring Int`
• `Semiring Number`
• `(Semiring b) => Semiring (a -> b)`
• `Semiring Unit`
• `(RowToList row list, SemiringRecord list row row) => Semiring (Record row)`

### #(+)Source

Operator alias for Data.Semiring.add (left-associative / precedence 6)

### #(*)Source

Operator alias for Data.Semiring.mul (left-associative / precedence 7)