trait EuclidianRing should not be a Ring

[benhutchison]

The docs give it away EuclideanRing implements a Euclidean domain.

However, there's a problem: a Euclidian domain need not be a Ring.

Approximately & intuitively, euclidean domains defines some set of of integral or whole numbers. These might well be the set of natural numbers (0, 1, 2, 3 etc), which don't have closed subtraction operation.

A ring however, must include a subtraction operation; that's what the n in ring signifies (n for 'negation').

Unfortunately, the trait hierarchy in the algebra package is over-constrained: it makes EuclideanRing extend Ring even though the operations it introduces, based around divmod, dividing whole numbers to yield a quotient and a remainder, do not require the negation aspect of rings.

trait EuclideanRing[@sp(Int, Long, Float, Double) A] extends Any with GCDRing[A] { self =>
  def euclideanFunction(a: A): BigInt
  def equot(a: A, b: A): A
  def emod(a: A, b: A): A
  def equotmod(a: A, b: A): (A, A) = (equot(a, b), emod(a, b))
  def gcd(a: A, b: A)(implicit ev: Eq[A]): A =
    EuclideanRing.euclid(a, b)(ev, self)
  def lcm(a: A, b: A)(implicit ev: Eq[A]): A =
    if (isZero(a) || isZero(b)) zero else times(equot(a, gcd(a, b)), b)

The impact is that it's not possible to implement a complete & correct algebra for natural numbers (non-negative integers) using the Cats hierarchy.

[johnynek]

cc @non

We implemented this stuff a very long time ago and may well have made a few mistakes in the encoding.

How should this have been encoded? It seems that extending GCDRing was a mistake in your view, but we don't have GCDRig do we? So I wonder if the hierarchy has greater issues in this regard.

What do you propose as our best course of action?

[benhutchison]

I think the "right" (ideal) representation would extend a EuclidianRig from Rig. AFAICT Euclidian doesn't need negation in its sematics or laws, and there could be a valid instance for natural numbers without subtraction.

I like the way NumHask models algebra, although the names are different. NumHask's Integral ~ Cats EuclidianRing and it extends Distributive, which ~ Cats Rig.

Possibly the "right" (pragmatic) solution is to mark this issue as Won't fix and simply leave it as a signpost for the next generation of library writers. Its likely a breaking change and I'd guess very few people care.

I don't have strong knowledge or views on why GCDRing is separated from EuclidianRing. Is there any known trait that extends GCDRing but not EuclidianRing?

[johnynek]

I wouldn't be surprised if no one has ever used this code. The breakage cross section may be very low here.

That said, an abstraction that is never used it also tautologically not useful. I imagine that you can add a trait to your own code just as well if you intend to use it.

If we had confidence of the improvement adding a new trait costs very little.

[benhutchison]

Well, I think a solution could be to

• new trait GCDRig extending Rig
• new trait EuclidianRig extending GCDRig.
• existing GCDRing would now extend Ring and GCDRig
• existing EuclidianRing would now extend GCDRing and EuclidianRig

Practically this would allow natural numbers to be supported since they can provide a EuclidianRig[Nat]