Integrating cats.kernel.Semigroup and friends

[LukaJCB]

Right now, there's AdditiveSemigroup and MultiplicativeSemigroup which are then combined into Semiring. This is all well and good, but unfortunately there's a huge amount of code out there written on the basis of cats.kernel.Semigroup and it's a bit of a shame we can't reuse those.
Especially in Spire where the various numeric types don't have Monoid instances and therefore can't be foldMaped.

Since in the Cats ecosystem numeric types usually come with an Additive Monoid as default, I would personally love to see that convention being expanded in this project, but I also understand there are some good reasons not to do that.
Here is some code I came up with that demonstrates how I'd personally like to have it:

trait Semiring[A] extends CommutativeMonoid[A] {
  def times[A](x: A, y: A): A

  def plus[A](x: A, y: A): A = combine(x, y)
  def zero[A] = empty[A]
}

trait Rig[A] extends Semiring[A] {
  def one[A]: A
}

[johnynek]

I think we can look at merging algebra into cats now that cats has reached 1.0

algebra has been stable for quite some time, and the main mission was a common set of classes between algebird and spire.

I think a cats-algebra module would make a lot of sense and core could eventually depend on it.

[LukaJCB]

I would very much like to see that as well: typelevel/cats#2041

[denisrosset]

Regarding the default monoid/group: the meaning really depends.

Say you have a Map[Monomial, Scalar] that represents a polynomial. You want the additive group there.

However, if you use permutation matrices to represent permutation group elements, you want the multiplicative group notation.

(And you'll want to avoid AnyVal wrappers in numerical/symbolical code to avoid wrapping with Array)
I like the distinction that is currently made. However, we could provide optional implicit conversions.

---

Regarding cats-algebra, I'm all for it. The only distinction between spire and algebra is spire.algebra.Field, which includes gcd/lcm/euclidean ring structure.

[LukaJCB]

Regarding the default monoid/group: the meaning really depends.
Say you have a Map[Monomial, Scalar] that represents a polynomial. You want the additive group there.
However, if you use permutation matrices to represent permutation group elements, you want the multiplicative group notation.

I completely agree with this notion. I'd just like to see consistency in the ecosystem.
Furthermore I'm not a huge fan of the duplication of having e.g. Semigroup, AdditiveSemigroup and MultiplicativeSemigroup.
Algebird also has its own Ring which extends cats.kernel.CommutativeGroup and can therefore be used with most of Cats' existing functionality which makes quite a bit nicer to use IMO.

(And you'll want to avoid AnyVal wrappers in numerical/symbolical code to avoid wrapping with Array)
I like the distinction that is currently made. However, we could provide optional implicit conversions.

Instead of using AnyVal wrappers, we could use something like scala-newtype which we're also going to be [using soon in cats]. (typelevel/cats#1800) and even if the extra dependency is something we don't want we could manually encode them as has already been done successfully multiple times in Cats and cats-effect.

Regarding cats-algebra, I'm all for it. The only distinction between spire and algebra is spire.algebra.Field, which includes gcd/lcm/euclidean ring structure.

Should we just add those ring structures (along with DivisionRing) to algebra? Sounds like a good idea to me :)

[johnynek]

I couldn’t see almost any code that we wanted that is generic on the Field stuff and Field also has the ugly aspect that inverse/div is not total (it can throw).

I think the marginal win of the Field/DivisionRing stuff isn’t worth including (also I don’t know of any interesting instances other than numbers).

[LukaJCB]

I couldn’t see almost any code that we wanted that is generic on the Field stuff and Field also has the ugly aspect that inverse/div is not total (it can throw).

This makes me uncomfortable as well. If scala had predicate/refinement types we could define it as

trait DivisionRing[A] {
  def div(x: A)(y: {A => y != zero}): A
}

but alas we do not, maybe in Scala 4. 😄

---

@johnynek what do you suggest we do about Field then, just stop the hierarchy at CommutativeRing and leave the rest to Spire?

[johnynek]

Yes. That’s precisely what I support. Spire is great and not going anywhere. If you are doing interesting numerical work, you should use it. It is fine if they keep the Field related classes.

[denisrosset]

Would be great to stop the hierarchy in algebra at CommutativeRing, so that we avoid the duplicate Field classes. And the rest of the ring tower is not exactly set in stone (we put UniqueFactorizationDomain outside the tower to let people pick their integer factoring algorithm, for example).

But I'm very adamant against merging Group and AdditiveGroup. Sure, add an implicit conversion, but typeclasses are about laws and syntax, and I've always admired that cats/algebra/spire has distinct method names and operators for e.g. permutation groups vs. addition and multiplication of integers.

[denisrosset]

Note: the precision of the commutative ring tower starts to be important when dealing with polynomials in a generic way. But the polynomial code in Spire is still a bit shaky.

[LukaJCB]

But I'm very adamant against merging Group and AdditiveGroup. Sure, add an implicit conversion, but typeclasses are about laws and syntax, and I've always admired that cats/algebra/spire has distinct method names and operators for e.g. permutation groups vs. addition and multiplication of integers.

How about going the PureScript route then? Remove AdditiveGroup and MultiplicativeGroup and their friends and start the ring hierarchy at Semiring. Then add newtypes to get either mutliplicative or additive Monoid. I think having to duplicate the 6 Semigroup -> CommutativeGroup typeclasses a full 3 times all with the exact same laws is really suboptimal and I think we can do better :)

Edit: For reference the PureScript prelude Semiring: https://pursuit.purescript.org/packages/purescript-prelude/4.1.0/docs/Data.Semiring

[johnynek]

I’m -1 on additive group but I didn’t insist since @non liked it so much.

I don’t like having a different type just to get syntax (which I’m not an enourmous fan of).

Algebird has always done what @LukaJCB suggests and uses types (case classes sadly) to dispatch. This means we get weird stuff like Max(1) + Max(3) == Max(3) but having one trait is a big win.

When writing generic code, I don’t care if I have an additive or multiplicative group. So at those points either and implicit or manual conversion is done. Since I’m most interested in generic programming and not syntax hacks, this seems like a bad trade.

[LukaJCB]

Another argument is that the |+| syntax on cats.kernel.Semigroup (as well as the |-| syntax on cats.kernel.Group) already sort of implies that combine usually refers to addition.

We're probably going to integrate scala.newtype (which will compile down to opaque types in 2.13) into cats-core for the various newtypes defined there as well, so that problem would be solved as well.

When writing generic code, I don’t care if I have an additive or multiplicative group. So at those points either and implicit or manual conversion is done. Since I’m most interested in generic programming and not syntax hacks, this seems like a bad trade.

I agree with this and a function

def foo[A: AdditiveMonoid](...) = ...

is completely the same as

def foo[A: Monoid](...) = ...

or

def foo[A: MultiplicativeMonoid](...) = ...

The laws are the same and they are fundamentally equivalent. IMO, generic code shouldn't care about multiplicative or additive at that level of abstraction.

The fact that we could remove 12 type classes from Algebra without losing any functionality is a pretty strong argument to me personally :)

[denisrosset]

I see the force is strong on this one. Before I present my case, let's acknowledge that there is no optimal solution there, just sets of different trade-offs.

The ambition of Spire is to go beyond arithmetic, and support generic algebraic structures: for example polynomials have more or less structure depending on what the underlying scalar supports. So precision is definitely a requirement.

On the other hand, PureScript made the choice of having a compact prelude, acknowledging platform limitations: for example, none of the Rig, Rng, semiring business, and the EuclideanRing function is limited to 32-bits integers.

I'll now give use cases of the structures that are proposed for elimination. My own experience concerns the use of Scala in quantum information, where the concepts below are central (complex arithmetic in particular).

1. MultiplicativeMonoid instances are used when multiplying monomials in polynomial arithmetic. There are linear algebra operations that do not require more than that, for example the Kronecker product (or tensor product) of matrices, the outer product of vectors. The notation here is explicitly multiplicative. In particular, this genericity comes handy when performing global optimization over polynomials (see Lasserre hierarchy).

2. On the same topic, complex conjugation is a involution on a multiplicative monoid, and there is a rich structure of *-rings, *-algebras, etc..., which concretely describe complex matrix multiplications. However, you want to define that involution on the multiplicative monoid of a ring, not the additive one. This becomes relevant when defining (complex) inner product spaces in linear algebra.

3. Additive groups have a particular relationship with total orders. In particular, the % operation on the JVM has laws based on an additive monoid compatible with a total order ("how many integer times does the right operand fit in the left?"). To express this % operation, which is distinct from Euclidean division Spire defined a TruncatedDivision typeclass. However, it makes sense relative to additive groups, and not others. I'm skipping over laws related to signs and the absolute value.

4. Most of the notation used for monoids/groups in mathematics is multiplicative, not additive. For example, multiplying permutations is commonly understood as semigroup composition (by analogy with the multiplication of permutation matrices), whereas permutation addition is seldom seen (but sometimes corresponds to the direct sum operation).

[johnynek]

@denisrosset can you speak to why the newtype approach does not solve the problems?

Is it just that you don't want to pick a privileged monoid from a ring?