Add Order2 And Friends TypeClasses

[isomarcte]

This commit adds the following type classes.

• Order2
• Order1
• PartialOrder2
• PartialOrder1
• Hash2
• Hash1
• Eq2
• Eq1

These typeclasses lift their base classes through unary and binary type constructors. See https://hackage.haskell.org/package/base-4.15.0.0/docs/Data-Functor-Classes.html#t:Ord2 .

A full documentation writeup is provided in order1.md. Here is a brief overview.

These typeclasses can make defining instances for types which are either unary or binary type constructors much more succinct. This is because there is no longer a need to provide lower priority instances for PartialOrder and Eq. For example, an instance of Order1 for some type F[_] can provide a PartialOrder[F[A]] given some PartialOrder[A] even if A doesn't have an Order instance. See the order1.md for some examples using Option. See the provided instance for Either for a concrete example.

In addition to removing the need for lower priority instances using the higher kinded variants of these classes can make the expression of some constraints much more succinct. For example, consider this data type definition.

final case class Person[F[_]](
  name: F[String],
  age: F[Int],
  height: F[Double]
)

In the absence of Eq1, if one wished to provide an Eq instance for Person[F] then they would need to use the following definition.

def eqInstanceForPerson[F[_]](implicit A: Eq[F[String]], B: Eq[F[Int]], C: Eq[F[Double]]): Eq[Person[F]] =
  Eq.instance{
    case (x, y) =>
      x.name === y.name &&
      x.age === y.age &&
      x.height === y.height
  }

That is, they would need to demand an Eq[F[A]] for each distinct A in the data type.

With Eq1 one can now write this.

implicit def eqInstanceForPerson[F[_]: Eq1]: Eq[Person[F]] =
  Eq.instance{
    case (x, y) =>
      x.name === y.name &&
      x.age === y.age &&
      x.height === y.height
  }

Now you only need to demand an Eq1 instance for F[_].

An instance of Order2 and Hash2 was added for Either and the other Order, PartialOrder, Eq, and Hash instances were deprecated. This serves as a convenient example.

Misc Other Changes

Bumped version to 2.8.0-SNAPSHOT due to the new symbols. (I know, I just missed the 2.7.0 release :( )

Future Work

If this PR is accepted, then I intend to also add the following.

• Additional combinators and methods to all the classes, analogous to the combinators and methods on the base classes.
• Add instances for the other cats/stdlib types. This should permit a non-trivial reduction in code size when the deprecated instances are removed in 3.0.0.

Weird Things

In order to be able to derive an Order instance from an Order1 instance, a low priority implicit was required in the companion object scope of Order (and similarly for the other classes). This means that these new classes needed to be in kernel, not core.

This has had the following consequences.

• Some of the instances in core require type projection that would normally be done with kind-projector. Because kind-projectors is not currently available in kernel, I had to write the projection in the more awkward base Scala syntax.
• In order to be able to derive all the instances we would expect, an instance of Order1 (and friends) is needed for cats.Id. However, cats.Id is defined in the package object in core, not kernel. However, we were able define instances for cats.Id by just using a type projection. Initially, I didn't think that was going to work, but to my surprise the compiler figured it out.

[isomarcte]

I'm looking into the build failure, but I don't think it is related to this PR.

[joroKr21]

I'm not sure this solves the low priority instance because Order1 <:< Eq1 and Hash1 <:< Eq1 but neither Hash1 <:< Order1 nor Order1 <:< Hash1 (same as the *-kinded versions really). So that means that if we have F with both Hash1 and Order1 instances and we want to get Eq (through Eq1) then we still have to prioritize them.

[johnynek]

I am not sure we should add these types. I think we should see a strong case for adding something, not an example or two. It's not that they don't make sense, but the question is: do the use cases justify adding this surface area to cats? I so far don't see that. Keep in mind: there are many libraries outside of cats (cats-effect, cats-collections, cats-time, and many more). Not everything needs to be upstreamed to cats.

Even if we do add it, they should not be added to kernel. What is and is not in kernel is up for debate, but the motivation for kernel was to share classes that were very broadly used. So kernel shares with algebra which also shares with spire and algebird. Another observation is that none of the typeclasses themselves are on type-constructors in kernel, and are just on types (I think that's still true). If we want these, they should be in cats since I don't see the demand coming to have these types in those other projects.

[isomarcte]

@joroKr21 I'm not certain I follow what you mean.

Given this trivial type.

final case class Wrapper[A](value: A)

object Wrapper {
  implicit val instance: Order1[Wrapper] with Hash1[Wrapper] =
    new Order1[Wrapper] with Hash1[Wrapper] {
      override def liftCompare[A, B](compare: (A, B) => Int, x: Wrapper[A], y: Wrapper[B]): Int =
        compare(x.value, y.value)

      override def liftHash[A](hash: A => Int, x: Wrapper[A]): Int =
        hash(x.value)
    }
}

I am able to derive Eq[Wrapper[A]] (for any A with a Eq[A] instance) just fine.

scala> Eq[Wrapper[Int]]
val res2: cats.kernel.Eq[cats.kernel.Wrapper[Int]] = cats.kernel.EqLowPriorityInstances0$$anon$112@49269478

If you define the instances for Order1 and Hash1 separately, then yes, you would need to use implicit priority to resolve the conflict. This is the case for Order and Hash too and is why many projects now define their instances as Order[A] with Hash[A].

[joroKr21]

Ah I see what you mean now - yes that would work. I must admit I almost never used this trick in application code so it didn't immediately pop in my mind.

[isomarcte]

@johnynek

I am not sure we should add these types. I think we should see a strong case for adding something, not an example or two.

For my part, I think the potential code reduction is strong motivation. For most types which cats provides Order for now which are of the form F[_] or F[_, _] we should be able to drop 3-4 instances/declarations by using the higher kinded classes. That adds up to quite a lot of lines of code. I'd be happy to crunch those numbers if it is helpful.

I also think removing the need to rely on implicit priority for these instances could help to make their encoding a bit more accessible, though that is admittedly a subjective measure.

I do personally find the higher kinded data use case quite compelling. Admittedly, I don't see encodings like Person[F[_]] very often, but I somewhat wonder if that is just because lacking classes like Order1 using them is very cumbersome. I have a higher kinded data type I'm working with right now which has about 8 different fields and the instances are a syntax nightmare ;)

Even if we do add it, they should not be added to kernel.

I started out with these in core, but I quickly realized that if these aren't defined in a scope where we can add the low priority instances on Order (and friends) to derive an Order[F[A]] from an Order1[F] and a Order[A], then the utility of these drops quite a bit.

This could of course be worked around to a degree with some orphaned implicits, but we also lose the ability to drop the aforementioned code in kernel and the ergonomics become much less appealing.

I agree, we should be very conservative about what goes in kernel. However in this case the utility and ergonomics of these classes drops quite a bit if they are anywhere other than kernel.

[johnynek]

@isomarcte

For my part, I think the potential code reduction is strong motivation. For most types which cats provides Order for now which are of the form F[] or F[, _] we should be able to drop 3-4 instances/declarations by using the higher kinded classes. That adds up to quite a lot of lines of code. I'd be happy to crunch those numbers if it is helpful.

Thanks! that would be helpful. I don't see the savings since it feels like we are just replacing implicit def orderForOption[A: Order]: Order[Option[A]] = ... with implicit val order1ForOption: Order1[Option] ...

Secondly, I can't even imagine why we would want heterogeneous inner types: compare: (A, B) => Boolean. I can't think of a use case, and it frustrates what laws should be true for that function (e.g. we normally want eqv(a1, a2) == eqv(a2, a1) and eqv(a1, a2) && eqv(a2, a3) implies eqv1(a1, a3) but when we have two different types none of those laws are expressible what what I can see so far.

[isomarcte]

@johnynek

Secondly, I can't even imagine why we would want heterogeneous inner types: compare: (A, B) => Boolean. I can't think of a use case, and it frustrates what laws should be true for that function (e.g. we normally want eqv(a1, a2) == eqv(a2, a1) and eqv(a1, a2) && eqv(a2, a3) implies eqv1(a1, a3) but when we have two different types none of those laws are expressible what what I can see so far.

Indeed, I was on the fence about this too, however there is prior art here: https://hackage.haskell.org/package/base-4.16.0.0/docs/Data-Functor-Classes.html#t:Eq1 (In particular see the doc for liftEq).

As for laws, I was also on the fence about this. Should we have laws for these classes directly, or should we say that they are lawful in the context of the Eq[F[A]] instances they generate? In other words, is there any property we wish to check for Eq1[F], which isn't already fully covered by the Eq[F[A]] generated for some A with a lawful Eq[A] instance? I've a feeling there isn't, but I've not fully convinced myself either ;).

Thanks! that would be helpful. I don't see the savings since it feels like we are just replacing implicit def orderForOption[A: Order]: Order[Option[A]] = ... with implicit val order1ForOption: Order1[Option] ...

I'll get you some concrete numbers shortly, but it should be noted we aren't just replacing orderForOption with order1ForOption. order1ForOption replaces, orderForOption, partialOrderForOption, hashForOption, and eqForOption, each of which currently must be defined separately so that we don't overly constrain the instances (which is not true with Order1[Option] with Hash1[Option], see the order1.md writeup).

[isomarcte]

@johnynek

Here is that back of the napkin math I promised you.

If we removed the deprecated instances for Either (Order[Either[A, B]], PartialOrder[Either[A, B]], Hash[Either[A, B]], Eq[Either[A, B]]), then we end up with a net reduction in code of 87 lines.

Our Order2[Either] with Hash2[Either] instance clocked in at 23 lines. So 87 - 23 = 64 lines of code. Some instances will probably save less code, some more, so let's guess that the using the higher kinded classes will on average save us 50 lines of code per type.

Now find types of the form F[_] and F[_, _] which could have their instances replaced.

• List
• Vector
• Tuple2
• SortedMap
• SortedSet
• Option
• Either
• Chain
• NonEmptyList
• NonEmptyVector
• NonEmptyChain
• NonEmptySet
• OptionT
• EitherT
• Validated
• ValidatedT
• IdT
• Const

That's 18 types that I could reasonably find. There are a few other types which might have some more minor improvements, such as Binested, but let's ignore those for now.

That all adds up to a savings of about 18*50 = 900 lines of code.

[johnynek]

@isomarcte

Thanks for that summary. You didn't include the lines in this PR right? (about 900 lines, which interestingly matches the savings), but also we can't remove the old values due to binary compatibility guarantees. So, won't the end product have 900 + 900 extra lines?

[isomarcte]

Thanks for that summary. You didn't include the lines in this PR right? (about 900 lines, which interestingly matches the savings)

@johnynek that's true, but 247 of those lines are my order1.md documentation.

but also we can't remove the old values due to binary compatibility guarantees.

I'm suggesting this is a savings for cats 3.0.0 when we can remove them.

[smarter]

Alternatively, I imagine cats 3.0.0 could use https://docs.scala-lang.org/scala3/reference/contextual/derivation.html which might also save people from writing all these instances :grin:

[zarthross]

@smarter While Using contextual derivation might also reduce lines of code, it doesn't solve the other problems Order1 solves.

[smarter]

Which other problems? The documentation mentions avoiding the need for multiple implicit scopes but I don't think that's actually needed as mentioned in https://github.com/typelevel/cats/pull/4061#discussion_r760482994

[isomarcte]

@smarter the problems these classes solve are,

• Having to define multiple instances (which is still true, without regard to scope).
• Being able to express constraints more directly, e.g. one constraint def foo[F[_]: Eq1] rather than N constraints, def foo[F[_]](implicit: A: Eq[F[A]], B: Eq[F[B]], ..., N: Eq[F[N]])

[johnynek]

I'm super -1 on "well haskell has it this way" as an argument. Scala is not Haskell and different design constraints come into play. For instance, in haskell, typeclass instances are not values you program with (generally, maybe there are some tricks, but it is not idiomatic).

So, if we were to include something like Eq1 I would want it to be something like:

trait Eq1[F[_]] {
  def eqFor[A](implicit eqA: Eq[A]): Eq[F[A]]
}

which is doing three things:

1. it is removing the heterogeneous typing (no A and B, just A).
2. it is using Eq[A] rather than (A, A) => Boolean
3. it is currying the next two args into returing an Eq[F[A]]

That said, I'm still not seeing the win over deriving which we will have access to in cats 3.

[armanbilge]

The F[_]: Eq1 thing looks nice to me actually. It would be helpful with e.g. defining laws, where you have to request Eq[F[A]] for all the As you might need ahead of time. So then when you need to add another law with another A you are in a bincompat mess. e.g. see https://github.com/typelevel/cats-effect/pull/2553/files#diff-74d29c570e321bfd23f2dd9d3462a133aec2105be230d0a9b72ed712f7d391daR157

Update: nevermind, after skimming through #599.

[mpilquist]

https://github.com/typelevel/cats/issues/599

[mpilquist]

Aside: we could add deriving support to cats 2 in binary compatible way, or we could rely on kittens for derivation. Even in the latter case, we’d get support for Scala 3 derives syntax at the cost of an import. I’d prefer to bake it in to cats directly personally.

[isomarcte]

@johnynek

I'm super -1 on "well haskell has it this way" as an argument.

I didn't intend to communicate we should just "do it the Haskell way". Mostly, with respect to Haskell, I thought having continuity in naming would be good. People who come to Scala and already know about this type of FP tend to come from a background in Haskell, Purescript, or Elm. I've found, both for myself and others, having continuity of naming is helpful in finding your way around and discussing constructs. That said, if it's a deal breaker, I really have only a slight preference in the naming.

With respect to your proposed Eq1 encoding, I'm uncertain if it would have all the same nice properties we get with this encoding, but I'm not sure, I'd have to play with it a bit.

[isomarcte]

@armanbilge

Update: nevermind, after skimming through #599.

Just to clarify, are you saying it doesn't seem useful or just that the bincompat stuff is different than you had thought?

[isomarcte]

@mpilquist

Aside: we could add deriving support to cats 2 in binary compatible way, or we could rely on kittens for derivation. Even in the latter case, we’d get support for Scala 3 derives syntax at the cost of an import. I’d prefer to bake it in to cats directly personally.

I totally agree. The code reduction that this affords us in the definition of instances is only a part of the gain here. I'm primarily interested in being able to constrain certain types.

[armanbilge]

tl;dr it's not useful for laws/discipline. The problem is that requiring Eq1[F] instead of Eq[F[A]] for laws can be overly restricting particularly when you are defining laws for an unusual F and you need to fudge it a bit for tests.

E.g. How would you define Eq1[* => R]? Whereas you can fudge an Eq[A => R] by requesting an Arbitrary[A] and checking for some randomly generated A.

The bincompat thing is a nightmare, but manageable. But providing an Eq1 when you can't is impossible.

[mpilquist]

Note we originally had Eq1 -- named EqK -- but we removed it in #599 after we realized it was causing issues with expressiveness of laws.

[isomarcte]

I agree that if this was merged, it shouldn't be used in laws to replace any Eq[F[A]] constructs. This PR already replaces the Eq instances for Either, but I intentionally left the laws and tests unchanged.

[armanbilge]

Yes, sorry, it was not a criticism :) just that my use-case idea evaporated unfortunately.

[armanbilge]

However, one lesson there might be that Eq1 is useful for implementations but maybe not a good idea to use as a constraint (not sure, maybe it's just a laws thing). Assuming that the implementation problem can be solved by derivation, it could be dangerous to have Eq1 available as a constraint.

[isomarcte]

However, one lesson there might be that Eq1 is useful for implementations but maybe not a good idea to use as a constraint (not sure, maybe it's just a laws thing). Assuming that the implementation problem can be solved by derivation, it could be dangerous to have Eq1 available as a constraint.

🤔 I'm trying to think of a situation where this would be an issue, outside generating Eq[F[A]] instances via sampling for testing laws, but I'm struggling to come up with any.

[isomarcte]

I'm making this a draft for now. There appears to be some bug in the Scala 3 compiler which is causing the build to fail. It is fixed on the latest RC, but until cats is ready to release on that this is not likely to be able to be merged whatever we decide on the merits of these classes in general.

[armanbilge]

@isomarcte now that Cats is on 3.1 seems like we could revive this. Any new thoughts about the proposal? IIRC there was not much consensus to move forward with it.