Consider Semiring definition

[non]

So @luc-j-bourhis (from #spire-math) did some research into the literature around various Ring-like structures and produced this gist:

https://gist.github.com/luc-j-bourhis/ffd0cccf4f83b1b8a133

He is discussing Spire but we are currently using the same definitions.

It's an interesting read but the only really major finding is that he thinks we should change Semiring. Currently our Semiring is a monoid for + and a semigroup for *. He thinks both should be semigroups.

What do you all think? It's an easy change to make if it seems good. I feel like @tixxit and I had a reason to prefer the current definition but honestly I can't really remember it.

[johnynek]

So the proposal here is:

1. Semiring drops AdditiveMonoid and instead picks up AdditiveSemigroup (do we have that?)
2. Add Hemiring with is like the old Semiring + CommutativeAdditiveMonoid
3. Make Rig CommutativeAdditiveMonoid (currently we don't have that, right?) The proposal seems split on that. First it says that commutative + is most common, but then it says that a reference claims weakening to just AdditiveSemigroup it is more useful. Algebird got by mostly on Semigroup and Monoid, so I'm inclined to go with the weaker ones. Yet, I don't know of many (any?) examples that would be excluded by making the stronger requirement.

My thinking is that we should have at least one example in mind to motivate a choice. Secondly, I don't think everything ever considered needs to be added.

So, I can see two separate issues here:

1. weaken Semiring and Rig (monoid + goes to semigroup +).
2. add Hemiring.

I think adding Hemiring is fine I guess (rings are already really complicated), but I don't know of an example that needs it. For the weakening, I'm fine with it because if you want to make your own, unnamed thing, you could do Rig[T] with CommutativeAdditiveMonoid[T] or something, right?

[non]

So, we currently do have commutative versions of all additive/multiplicative structures (they are in Additive.scala and Multiplicative.scala respectively). As far as I know @luc-j-bourhis was just arguing for your point (1) to weaken Semiring[A]. I'm not sure if he necessarily wanted to add Hemiring[A].

I think your points are good. I'm honestly not sure if Hemiring[A] is needed, and I totally agree that we don't need to support all possibly additive/mulitplicative combinations. I also agree that [A: Semiring: CommutativeAdditiveMonoid] or similar is an adequate way to support an optional monoid for semirings.

As you say I'm not sure this is hugely important one way or the other, but if we want to make these changes, now is the best time.

I'd like to hear @tixxit's opinion, as well as @luc-j-bourhis' to make sure we are understanding him correctly. (Of course, anyone else who wants to weigh-in is welcome too.)

[tixxit]

So, I was the one who originally added zero into Spire's Semiring. The main reason was that I found several places where I wanted a Semiring with a 0 and none where I didn't have a 0, so it was frustrating that it was missing. I think this is because zeros often arise naturally (eg. empty Map or List) or can be added artificially (eg. None/Some). If we weaken Semiring, I would probably want a Semiring with a 0 and would prefer if we gave it a name, since I think it'll get far more use than just Semiring (for concrete instances). I could say [A: Semiring: AdditiveMonoid], but we could do this for most of our structures, including Rig, Rng, etc. so I don't really like that :\

[tixxit]

My informal guide with Spire was that I didn't want to add type classes if we didn't have a concrete use case for the type class, where only it would do. So, what concrete cases are we supporting with a Semiring without 0? I definitely don't mind weakening Semiring, but would prefer we have a good use case.

[luc-j-bourhis]

@tixxit: how did you want to define addition and multiplication for Map and List?

[tixxit]

I think we have an example in algebra-std, with MapRng (pointwise).

[tixxit]

We can also look at how Semiring is used in the Polynomial implementations and Complex and Quarternion, where it is convenient to have a 0, but not acceptable to further restrict the type class to Rig or Rng. A Semiring with 0 is quite useful currently, because it generalizes both Rig and Rng, and not so much because we have types that are only Semirings. If we loosen Semiring, then it'll still be useful in the types I mentioned, but we'd also need the variant with 0 often.

[tixxit]

If everyone agrees that we add Hemiring and drop 0 from Semiring, I'm happy. Currently our Semiring is not commutative, would the new Hemiring have commutative addition? This would make Rig's addition commutative too, as @johnynek mentioned.

[non]

Talking more to @luc-j-bourhis on IRC, here is what I propose we do:

1. Fix Semiring[A]'s documentation (and possibly mention that it also corresponds to the definition of a hemiring) but leave the 0 alone, since almost all structures we can think of use it.
2. Add commutativity to + for all ring-like structures (this would change Semiring[A] and Rig[A]).

What do you all think? I can't think of anything we are working with that needs non-commutative addition. The most exotic semirings I've worked with (Kleene algebras and star semirings) both require commutativity.

[tixxit]

:+1: on both.

[non]

I think this is pretty in line with Oscar's suggestion so I'll push a PR and link it to this issue.