... | ... | @@ -184,31 +184,48 @@ Issues: |
|
|
(or *unit*). Any such *y* is called an *associate* of *x*.
|
|
|
For integral types (but not others), this is similar to `signum` and
|
|
|
`abs`, but the general idea makes sense for any integral domain.
|
|
|
- These could be combined in a class of Euclidean domains, or there could be
|
|
|
an intermediate class of integral domains. In the latter case division
|
|
|
would not be available for defining defaults.
|
|
|
- In algebra, each field is trivially a Euclidean domain, with the remainder
|
|
|
always zero. However this would break backwards compatibility, as well as
|
|
|
the programming languages convention of distinguishing integer division.
|
|
|
|
|
|
|
|
|
Proposal:
|
|
|
|
|
|
- Add a Euclidean domain class, with canonical factorization satisfying
|
|
|
|
|
|
```wiki
|
|
|
stdAssociate x * stdUnit x = x
|
|
|
stdUnit (x*y) = stdUnit x * stdUnit y
|
|
|
stdUnit x * (one `div` stdUnit x) = x
|
|
|
x*y = one => stdUnit x = x
|
|
|
```
|
|
|
|
|
|
and either `divMod` or `quotRem`.
|
|
|
- (Could be further split by placing canonical factorization in an integral
|
|
|
domain class, but division would not be available for default definitions,
|
|
|
and would also need to supply the reciprocal of `stdUnit x`.)
|
|
|
|
|
|
|
|
|
Proposed new class:
|
|
|
|
|
|
```wiki
|
|
|
class Ring a => EuclideanDomain a where
|
|
|
div, mod :: a -> a -> a
|
|
|
divMod :: a -> a -> (a,a)
|
|
|
|
|
|
stdAssociate :: a -> a
|
|
|
stdUnit :: a -> a
|
|
|
normalize :: a -> (a, a)
|
|
|
|
|
|
div, mod :: a -> a -> a
|
|
|
divMod :: a -> a -> (a,a)
|
|
|
|
|
|
-- Minimal complete definition:
|
|
|
-- (divMod or (div and mod)) and stdUnit
|
|
|
-- (stdUnit or normalize) and (divMod or (div and mod))
|
|
|
stdAssociate x = x `div` stdUnit x
|
|
|
stdUnit x = snd (normalize x)
|
|
|
normalize x = (stdAssociate x, stdUnit x)
|
|
|
|
|
|
n `divMod` d = (n `div` d, n `mod` d)
|
|
|
n `div` d = q where (q,r) = divMod n d
|
|
|
n `mod` d = r where (q,r) = divMod n d
|
|
|
|
|
|
stdAssociate x = x `div` stdUnit x
|
|
|
```
|
|
|
|
|
|
|
... | ... | |