ConicMonoid: when values are always increasing.

[sritchie]

Copied from @johnynek's issue https://github.com/twitter/algebird/issues/218:

// Gives the contract that a1 + a2 >= a1 and a1 + a2 >= a2
trait ConicMonoid[A] extends Semigroup[A] {
  def ordering: Ordering[A]
}

trait ConicMonoid[A] extends Monoid[A] {
  def ordering: Ordering[A]
}

Name from https://twitter.com/DRMacIver/status/388935423709704192

[tixxit]

So, @denisrosset is currently looking into adding an linearly ordered group, either to algebra or spire. May be worth touching base with him. This actually is sort of ground work for possibly having an OrderedRing, followed by a correct truncated division.

[TomasMikula]

See also this mathoverflow question Standard name for a Monoid/Semigroup with a+b≤a,b? (without an answer).

Also note that this is a different property than the (linearly-)ordered semigroup/monoid/group linked above by @tixxit, so we shouldn't squash them into one typeclass.

[denisrosset]

The main problem with OrderedRing is that you need to define OrderedEuclideanRing, OrderedField and so on as well.

Otherwise, when a method requires an OrderedRing and a Field implicit, the Ring implicit become ambiguous.

But @tixxit is right, I'm trying to find a solution that works with the Scala type system without too much fuss.

[TomasMikula]

This problem with ambiguous implicits comes up often and is a pain. I don't think having a typeclass for each possible combination of properties is feasible, though, because

1. it explodes combinatorially; and
2. it is not modular: from a user's perspective, it is limiting to assume that whenever there is OrderedRing and Field, they come as OrderedField. The OrderedRing and Field could in principle come from two different libraries.

Perhaps subtyping-free encoding of type classes, as explored by @aloiscochard in scato, can bring some hope. Then, neither OrderedRing nor Field are themselves a Ring, but there are implicit conversions to Ring from both of them. If those implicit conversions are properly prioritized, it will avoid ambiguity.

@adelbertc is also exploring this in this blog post.

[denisrosset]

What I'm coming up is "type towers", where each tower contains a list of properties, and all combinations are available. But the towers do not mix.

Thus there would be a Ring/Field tower, with the additional commutative property; and another Order tower, containing as well Signed and the new TruncatedDivision type. I'm building a prototype of this in Spire; the complication is that we want specialization, so we run into compiler bugs.

[denisrosset]

@TomasMikula Anybody benchmarked the scato approach? How does the JVM JIT deal with the many indirection levels (up to four levels of nested vals)?

This seems a bit crazy in a performance-oriented library like Spire. The SAGE library for Python dealt with that problem by implementing some crazy type system on top of Python's to merge instances as needed --- but in a formal way, by basing their types on their category theory definitions. One day, I'd like to explore how this approach could be reproduced in Scala. In the meantime, I think we have to find a middle way.

[TomasMikula]

I'm not aware that anyone benchmarked that, at least with as many as 4 indirections.

I can't even imagine how people would deal with this in Python. They must have basically implemented a separate programming language. Anyway, I would like to understand more about it. Is that solution extensible by users, or does it work only for the "privileged" SAGE code?

[denisrosset]

Have a look: http://doc.sagemath.org/html/en/reference/categories/sage/categories/category.html Indeed, it's a new layer on top of Python. They end up bumping into the limitations of a dynamical language, i.e. by prescribing method signatures using a special encoding. I thought a bit about writing a Scala equivalent, but I fear the type system is not strong enough. Edit: it's extensible by user code, but probably not for an arbitrary existing library -- i.e. unlike the typeclass approach used in Algebra/Spire.

[aloiscochard]

@denisrosset yes I did, here is the benchmarks, you can simply run them: https://github.com/aloiscochard/scato/blob/master/benchmarks/src/main/scala/Instantiations.scala

IMO it is negligible, I would love to hear @non feedback on it, especially in the context of library like algebra.

[denisrosset]

@aloiscochard thanks for the info!