Cats: Possibility of eventually moving to stdlib Equiv/PartialOrdering/Ordering

[ceedubs]

The Eq, PartialOrder, and Order type classes in cats-kernel closely resemble the Equiv, PartialOrdering, and Ordering from the standard library, however there are currently some differences (which I'll discuss below).

In this issue, I'd like to have a discussion on:

• why cats-kernel has its own version of these type classes as opposed to using the ones from the standard library
• what changes we'd want to see in the standard library before choosing to (eventually) switch over to its type classes (or reasons that this would never happen)

goal (of this issue)

I don't intend for this issue to linger around forever. It can be closed when either of the following happens:

• We've accumulated enough information for me to be able to _write a proposal_ to make the necessary changes to the standard library OR
• We've documented the reason why we think that these typeclasses should live separately in Cats

plausibility and timeline

At this point, it's unclear whether or not this change even _could_ feasibly happen, let alone the timeline involved. I haven't yet spoken to any standard library maintainers about this; I wanted to see where Cats maintainers stood first. But if any standard library maintainers happen to be reading this, I'd love to hear your input.

For most of the differences listed below, I've given a brief summary of my thoughts on how much of a compatibility concern it might raise in the standard library.

At this point I suspect that it's too late in the Scala 2.13 lifecycle for these changes to be proposed in the standard library. I wanted to get this out there because I've been thinking about it for quite some time but have never acted on it.

problem

There's no question that Eq, PartialOrder, and Order are extremely similar to Equiv, PartialOrdering, and Ordering. In the past, Cats has made decisions to prefer standard library types (even when they aren't _exactly_ how we would want them to be) to reinventing the wheel. See the Xor to Either transition for an example.

I think that looking the many conversions between Order and Ordering in NonEmptySet and NonEmptyMap are indicative of clunkiness in the current state of this type class duplication. In addition to feeling clunky, they incur a bit (though probably not a lot) of performance/memory overhead.

differences between Cats and standard library

I wasn't involved in the initial creation of Eq/PartialOrder/Order, but I know that there was a conscious decision to not use the type classes from the standard library. Below is a list of some differences that I have observed. They are _roughly_ ordered with what I suspect are the most significant changes at the top.

specialization

The Cats versions of these typeclasses are all @specialized, while the standard library versions are not. While @non would be the expert here (and for several other points below), I suspect that not using specialization for these type-classes makes using them in tight computational loops prohibitively expensive due to all of the allocation overhead of boxing.

I'm guessing that we'd need to see specialization of these type classes in the standard library to consider using them. I don't know how open to this change the standard library authors would be.

PartialOrder: Double vs Option[Int]

In the standard library's PartialOrdering, tryCompare returns an Option[Int], while in Cats' PartialOrder, partialCompare returns a Double. Again, I'd defer to @non, but I would imagine that this is to avoid allocation overhead.

I'm guessing that performance-conscious people using partialCompare would want to see the Double-version added to the PartialOrdering type class, which would be binary-incompatible before Scala 2.12 but seems to be like it wouldn't be a very controversial change after that.

universal Equiv

In the standard library, there is a universal Equiv instance in the Equiv companion object. To me, this seems to repeat the problems of universal equality in Java and undermines the usefulness of type class-based equality.

I think that in order for Cats to use Equiv, this instance would need to be removed. In theory, this is a very breaking change. In practice, I've used Scala for years in many different contexts and I've never seen Equiv used, so I suspect that this wouldn't have a _huge_ impact on the community. One could always provide an import for those who want this in scope.

machinist

Cats uses machinist to provide zero-cost syntax for these type classes, while the standard library does not. I know that this is supposed to provide a measurable performance improvement, but I can't speak to the magnitude or whether people who are performance-conscious could "bolt" machinist on somewhere outside of the standard library. Unfortunately, I think that there are very few people who understand machinist well (see this unanswered Cats comment from a year ago). Hopefully @non can weigh in.

comparator/comparable

In the standard library there are implicit conversions from Comparable and Comparator to Ordering, while in Cats there is only an _explicit_ conversion from Comparable to Order. Some might view these implicit conversions as questionable, but I don't know of a concrete reason that they should be avoided.

Comparison

Cats has a Comparison enum-like type (GreaterThan, Equal, or LessThan) and Order exposes a method that compares to items with a Comparison result. Currently as far as I know an equivalent type doesn't exist in the standard library.

Starting with Scala 2.12, Comparison and the associated methods could be added to the standard library in a backwards-compatible way. Even if they weren't added, I suspect that people wouldn't consider the lack of Comparison to be a dealbreaker.

[LukaJCB]

universal Equiv

Yeah this one is really the only deal-breaker, but boy is it bad 😄 I think we could definitely lobby to get that removed! I even saw one of the Scala team members tweet about how it was a bad idea:

https://twitter.com/jvican/status/1034529059911426048?s=19

[kailuowang]

Related information, there's discussion on moving kernel into Scala std lib or becoming a Scala module, and the proposal is that we continue to own them. That would be a good path to solve this

[johnynek]

In general, I personally think cats-kernel is mature enough to suggest moving virtually all of it into the standard library, and I think we should try to do so.

On Equiv, it is absolutely essential that we remove the default universal equality instance if we are to make any progress in my view.

I bet that is something we could propose for 2.14. I wonder if it is too late to mark that as deprecated in 2.13?

[ceedubs]

I also view cats-kernel as quite mature (with a notable exception being the unanswered questions about machinist that I referenced above).

I do think that there are some parts of kernel that are a bit more opinionated than others. For example, Semigroup.combine takes two strict arguments, as opposed to the equivalent function in haskell/scalaz. There are some useful properties in at least the second argument being lazy (for example an orElse Semigroup for Option that doesn't evaluate the second Option unless it needs to). However, in Cats the decision was made to make both arguments strict for performance reasons. I'm not necessarily opposed to most/all of cats-kernel being brought into the standard library, but I wanted to raise the concern that some pieces of it have plausible alternative designs. Also I'd want to understand more about what would be the gains of doing so. Where is this discussion happening?

[johnynek]

I think the cats position is that if you want laziness you can work with Eval[A].

[ceedubs]

@johnynek since the Eval companion object has implicit def catsSemigroupForEval[A: Semigroup]: Semigroup[Eval[A]], you are kind of playing with fire if you define your own Semigroup[Eval[A]] and expect it to be used. Depending on imports and implicit prioritization I could see someone accidentally summoning the non-lazy Semigroup instance when they don't expect to.

[johnynek]

SIP-35 is my go to answer here.

The cost of making everything lazy when almost nothing leverages it still seems a bad call to me. Also it’s not clear which side should be lazy. Some types would want left or right.

[ceedubs]

@johnynek how would opaque types help with this example (laziness)?

Just to make sure that I'm clear, I agree with the choice that was made for Semigroup.combine in Cats (and it's out of the scope of this issue), for the reasons that it was made. I just want to make sure that people are aware that while Semigroup is about as simple a useful type class as you can find, it still involves at least one choice that can be impactful, so it's a significant consideration when thinking about adding it to the standard library.

[johnynek]

opaque type LazyOption[A] = Eval[Option[A]]

Since it is opaque, you don’t have issues with finding the correct instance.

That’s all I meant. So there is no problem with the instance defined in the Eval companion.

[ceedubs]

@johnynek ah okay I see what you are saying. 👍

[LukaJCB]

cats-kernel in Scala 2.14 would be really amazing, let's lobby for that :+1:

[ceedubs]

As a first step I've submitted https://github.com/scala/scala/pull/7164 to deprecate the universal Equiv instance in the standard library; we'll see what people think.

[alexknvl]

Equiv is not required to satisfy x = y => f(x) = f(y).

However, even some cats' Eq instances do not actually satisfy it, for example the current instance for Double fails this law if passed f(x) = 1/x, x = -0.0, y = +0.0, and indeed that test is disabled in kernel.

It would be great if stdlib instances were actually tested to at least satisfy the equivalence laws (without the indiscernibility of identicals) on types that do not contain floating point types.