Euclidean rings

[Bodigrim]

This is to avoid messy div{E,G}, mod{E,G}, gcd{E,G} (cf. the implementation of Gaussian integers and #121) and unify them with div, mod, gcd for usual Integral types.

class Euclidean a where
  quotRem :: a -> a -> (a, a)
  divMod  :: a -> a -> (a, a)

quot :: Euclidean a => a -> a -> a
quot = ...

rem :: Euclidean a => a -> a -> a
rem = ...

div :: Euclidean a => a -> a -> a
div = ...

mod :: Euclidean a => a -> a -> a
mod = ...

instance Integral a => Euclidean a where 
  ...

instance Euclidean GaussianInteger where
  ...

instance Euclidean EisensteinInteger where
  ...

Then we can replace Integral constraint with Euclidean in Math.NumberTheory.GCD, Math.NumberTheory.Prefactored and Math.NumberTheory.SmoothNumbers, making them both more general and applicable to quadratic fields.

https://en.wikipedia.org/wiki/Euclidean_domain

[rockbmb]

@Bodigrim Sorry, minor nitpick: where there's Eucledian, there should be Euclidian Euclidean.

[rockbmb]

@Bodigrim this is probably outside the scope of this package, but what do you think of the viability of this issue being part of a larger plan of including class inclusions from commutative rings and integral domains all the way to fields?

[Bodigrim]

what do you think of the viability of this issue being part of a larger plan of including class inclusions from commutative rings and integral domains all the way to fields?

It seems every Haskell developer gets this temptation at some moment, fascinated by divine simplicity of Semigroup and Monoid and frustrated by arbitarary choice for Num and Integral.

My opinion is that certainly there are algebraic structures, which fits programming idioms nicely and they are the simplest one. Everything else, starting from rings, has so many different species, that the full hierarchy has little added value for practice. Unless there is a solid reason to distinguish some special structure (e. g., Euclidean ring).

With regards to arithmoi, we may win from distinguishing prime rings and unique factorisation domains also.

[rockbmb]

@Bodigrim Heh, I admit I've done that before, although this time it was because I've noticed arithmoi could benefit from quite a few types of structures. For now, this issue's will do

[b-mehta]

I'm unsure about quotRem in this case - in the general Euclidean case it's clear what divMod means (using the Euclidean function) but since we may not be in an ordered ring it's unclear what quotRem would represent.

[Bodigrim]

Valid point. Up to my understanding even in Gaussian ring there are more than two ways to define division with remainder, truncating to different directions by both axis. So may be it is worth to define only divMod, but I have not thought much about it yet.

[b-mehta]

Yes, I think defining only divMod is the best option. I suspect we can make a canonical choice of which division with remainder to take: In fact if every division is unique then the ring is actually a field or the polynomial ring of a field.

Additionally, Euclidean domains are unique factorisation domains, so it may be possible to extend in that direction also.

[rockbmb]

I agree with defining only divMod, but how will that help in reducing quotRem/quot/rem{G,E} clutter? These functions will still need to be duplicated.

[rockbmb]

@Bodigrim after #121 is merged, I'll work on this as well. Can you please answer ⬆️

[Bodigrim]

On one side I do not think that someone used quotRem* functions a lot. On the other side they are slightly faster than divMod*.

For now let us implement both quotRem and divMod. At least we will be able to provide a backward compatible API for GaussianIntegers. There are enough breaking changes for one release and it is better do not break everything at once :)

The difference may be stated as follows: divMod of Euclidean ring, restricted to a subring, isomorphic to Integer, should match divMod of Integer. And similar for quotRem. Does it sound reasonable?

[rockbmb]

@Bodigrim Makes sense. I'll start working on this.