Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Possibility of eventually moving to stdlib Equiv/PartialOrdering/Ordering #2455

Open
ceedubs opened this Issue Sep 1, 2018 · 13 comments

Comments

Projects
None yet
6 participants
@ceedubs
Copy link
Collaborator

ceedubs commented Sep 1, 2018

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

This comment has been minimized.

Copy link
Collaborator

LukaJCB commented Sep 1, 2018

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

This comment has been minimized.

Copy link
Member

kailuowang commented Sep 1, 2018

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

This comment has been minimized.

Copy link
Collaborator

johnynek commented Sep 1, 2018

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

This comment has been minimized.

Copy link
Collaborator Author

ceedubs commented Sep 1, 2018

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

This comment has been minimized.

Copy link
Collaborator

johnynek commented Sep 1, 2018

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

@ceedubs

This comment has been minimized.

Copy link
Collaborator Author

ceedubs commented Sep 2, 2018

@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

This comment has been minimized.

Copy link
Collaborator

johnynek commented Sep 2, 2018

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

This comment has been minimized.

Copy link
Collaborator Author

ceedubs commented Sep 2, 2018

@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

This comment has been minimized.

Copy link
Collaborator

johnynek commented Sep 2, 2018

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

This comment has been minimized.

Copy link
Collaborator Author

ceedubs commented Sep 2, 2018

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

@LukaJCB

This comment has been minimized.

Copy link
Collaborator

LukaJCB commented Sep 2, 2018

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

ceedubs added a commit to ceedubs/scala that referenced this issue Sep 2, 2018

Deprecate implicit universal Equiv instance
One of the benefits of type class-based equality is that the compiler
can enforce that you only check equality on types for which it is
meaningful (as opposed to universal equality such as Java's `equals`
that will allow you to compare any two objects even if it's a
meaningless comparison due to a typo).

Having an implicit universal `Equiv` instance throws away this benefit.
With this instance in scope (and it always is, since it's in the
companion object), the compiler will happily let you compare two `Any`
instances, two `Function1` instances, etc, even though doing so is
probably a mistake. Also, even if you have defined a well-behaved
`Equiv` instance for your type, if you forget to import it, the
universal instance will jump in to take its place without the compiler
warning you.

[Here](https://twitter.com/jvican/status/1034529059911426048?s=19) is a
recent tweet from @jvican on the subject.

This also came up in a
[discussion](typelevel/cats#2455) in the Cats
repo that I started recently about what it would take for Cats to start
using `Equiv`/`PartialOrdering`/`PartialOrder` from the standard library
instead of having its own version of these type classes. I'm a bit
hesitant to link to that conversation here, since it goes well beyond
the scope of this PR, but it is relevant.

If desired, I'll happily change this to a PR to remove this instance
altogether for Scala 2.13, but I wasn't sure whether it was too late to
introduce that change.
@ceedubs

This comment has been minimized.

Copy link
Collaborator Author

ceedubs commented Sep 2, 2018

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

@alexknvl

This comment has been minimized.

Copy link

alexknvl commented Oct 22, 2018

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.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.