An anecdote... 😏

[benhutchison]

Whoops, somehow using an emoji created the issue prematurely.

Anyway, an anecdote..

In an unpublished project, I have opaque types that model non-negative Integers, Doubles and Decimals.

Initially, I added bespoke operations as extension methods to each, but that got boring fast. So I switched to using Algebra; define surface-syntax in terms of the typeclasses in Typelevel algebra and Spire, and then implement those TCs for my non-negative types. Has proved quite practical, and feels like a much more solid base to go forward upon.

However. It turned out to be far from obvious what algebras to implement for non-negative integral and rational data types. I got as far as Semifield which gave me everything but subtraction. Solving subtraction led me down a fascinating wikipedia rabbit hole and ultimately to the discovery of Monus.

But then I hit another doubt. What algebraic structure models non-negative rationals, in entirety? M-Semiring doesnt include division. Semifield doesn't include monus-subtraction. Is there such thing as a "M-Semifield"? 🤔 💭

Surely the combined mathematical GDP of the world has been able to give name to the algebra of such a ubiquitous class of numbers as the non-negative rationals/reals..? surely..?

And it was in the spirit of doubtful inquiry that I accidentally googled your project, number 2 after wikipedia. "Arman Bilge woz here!"

And sure enough, it does seem like the weight type W in your Resampler is intended to be a non-negative rational.

And that felt like an anecdote worth sharing... :)

[benhutchison]

Actually, can I ask you about your take on Monus?

You extend PartialOrder which is consistent with wikipedia etc. However, IIUC, a partial ordering means that this Monus cannot be a Metric, because if two elements a & b are incomparable, we cant use eg max(monus(a, b), monus(b, a)) to find a distance between them.

We can sensibly define distance between pair of non-negative numbers. In your view, is there a case for an OrderedMonus typeclass, ie Monus+Order, that could also implement eg Spire's MetricSpace[N, N]?

[armanbilge]

However, IIUC, a partial ordering means that this Monus cannot be a Metric

Sorry to split hairs: it means that a Monus is not necessarily a Metric, but it does not mean it cannot be a Metric.

In your view, is there a case for an OrderedMonus typeclass, ie Monus+Order

I need to load this stuff back into my brain. But at a glance, this seems reasonable: after all, there are examples of Monus with total Order.

[benhutchison]

Another question, if I may.

Your Monus chooses a "has a" over trait inheritance "is a":

trait Monus[A]:

  def monus(x: A, y: A): A

  def additiveCommutativeMonoid: AdditiveCommutativeMonoid[A]
  def naturalOrder: PartialOrder[A]

Typelevel Algebra generally prefers the inheritance approach (as do I, I think) eg Field, but it is not 100% consistent see eg Signed

Is there a design heuristic here that you follow and can express, or is this simply a case of different practices colliding and a lack of consensus?

[armanbilge]

Is there a design heuristic here that you follow and can express, or is this simply a case of different practices colliding and a lack of consensus?

Yes, actually there is a blog post on this exact topic. It's also briefly explained in the comment on Signed.

https://typelevel.org/blog/2016/09/30/subtype-typeclasses.html

The tl;dr is that the inheritance encoding only works for a "blessed" linear hierarchy, because otherwise you may easily end up with more than one implicit instance satisfying the same constraint, leading to ambiguity.

[benhutchison]

Right. I do recall this issue now, although back of mind as I haven't been bitten recently.

So, using the Resampler signature as a concrete example to align on the problem:

 def targetWeight[F[_]: Monad, W: Monus: Order](computeTarget: Eagle[W] => F[W])(using
      W: Semifield[W],
      cat: Categorical[F, NonEmptyList[W], Long],
      unif: DiscreteUniform[F, Long],
  ): Resampler[F, W]

If Monus inherited AdditiveCommutativeMonoid, it would become ambiguous WRT Semifield if a method called within the body needed eg AdditiveCommutativeMonoid[W], since they both extend it. Diamond problem again. 😬

It's awkward. I watched @adelbertc's talk, the dotty issue, lots of problem, not much solution there..

I have a proposed solution that I believe is workable (may require a time-machine 😝). To sketch it, let me make up some terms: bare vs bundled typeclasses (TC)

Monus is an example of a bare TC:

• Doesnt inherit from other TCs, declares dependencies as members instead
• Interface defines new operations only, in terms of the field
• Bare TCs wont cause ambiguity
• Design challenges is that clients using bare TCs need to express lots of fine-grained constraints, eg W: Monus: Order: Semifield above.

OTOH Field is an example of a bundled TC:

• Inherits from all its dependencies and extends their Interface
• Bundles are often convenient for clients because they "bundle up" constraints, eg a hypothetical W: OrderedMSemifield
• Bundled TCs can cause ambiguity when 2+ bundles share a common ancestor

Proposed design heuristic:

• All TCs must be defined bare form.
• The bare TCs can be optionally bundled for convenience. Bundles should be declared for "commonly needed" combinations - this is a judgement call involving taste & style.
• There is a naming convention for distinguishing bare vs bundle TCs
• Clients can always safely depend upon [0-1] bundle TCs plus any number of bare TCs. Of course, sometimes, 2+ bundle TCs from non-overlapping domains will be fine.

I know the existing corpus of Scala/Typelevel TCs are not declared in bare form, but I still feel it is important to have a view on what one ought to do.. 🧭

[benhutchison]

Implementing the above conventions would see bundle instances and bare instances sharing the same implicit scope.

I become concerned that this would be ambiguous and thus an error, but empirically it doesn't seem to be the case.

[benhutchison]

There is an attempt to address this problem in Scala 3.6/2.7:

https://www.scala-lang.org/2024/08/19/given-priority-change-3.7.html

Will be interesting to see how it works in practice on larger typeclass-heavy Scala codebases :)

[armanbilge]

(Moved to a discussion on this repo, where Monus is defined as well as an implementation LogDouble.)

M-Semiring doesnt include division. Semifield doesn't include monus-subtraction. Is there such thing as a "M-Semifield"?

I actually haven't heard of the "M-Semiring", can you link me anything about that?

[benhutchison]

I picked it up here and ran with it... 😝