This page is no longer maintained — Please continue to the home page at www.scala-lang.org

Contravariance for Ordering, PartialOrdering, and Equiv

6 replies
Jeff Olson
Joined: 2011-06-29,
User offline. Last seen 42 years 45 weeks ago.
Can I make an impassioned plea to the powers that be to make scala.math.{Ordering, PartialOrdering, Equiv} contravariant in their type parameter? I know, having tried it, that the necessary code changes to the traits themselves are straightforward, if not trivial. However, after reading http://www.scala-lang.org/node/3786, I get the impression that there is some obscure technical obstruction having something to do with contravariant type-inference and F-bounded polymorphism. (I would be most interested if someone could explain it to me in more detail). How serious is this problem? Are there any easy workarounds? Is there a ticket open for this?

That was the plea. Now for some passion: Of course, all these traits are naturally contravariant and having them invariant is nearly as bad as having List[T] be invariant. It is an embarrassing blight on an otherwise beautiful library (I was about to say language). I'm finding more and more of my code riddled with silly boilerplate like

implicit val ordering2: Ordering[Bar] = implicitly[Ordering[Foo]].on(identity)

when I need an ordering on Bar <: Foo and I have an implicit ordering on Foo (in the more annoying cases, Bar is something like SomeLongAnnoyingPrefix#SomeAbstractTypeThatIsReallyAFoo). And, of course, I have to do this for every different Bar that extends Foo. But at least asking for an implicit Ordering[Bar] and only supplying an Ordering[Foo] results in a compile time error. I ran into a more insidious bug last week when I was (unknowingly) asking for an implicit Equiv[Bar] when I had defined an implicit Equiv[Foo]. The code looked something like

def assertEq[T](x: T, y: T)(implicit e: Equiv[T]) = ...

implicit cmp: Equiv[Foo] = ...

assertEq(q.x, p.x)

As far as I was concerned, the type of the expressions q.x and p.x was Foo, and I had defined an implicit Equiv[Foo]. But the compiler figured out that T was some strange compiler generated type that happened to be a Foo, but had slightly more context, and therefore my implicit didn't apply--BUT, the compiler happily supplied my assertEq with the universal (equality based) Equiv[SomeStrangeCompilerType#ThatHappensToBeAFoo], and so my program compiled just fine. It took me a good number of hours to figure out why is wasn't doing what I intended.

In the end my solution was to define my own contravariant Equiv[-T]. I fear I may go the route of defining my own Ordering and PartialOrdering as well if the standard library can't be fixed. Please don't make me do it!

Jason Zaugg
Joined: 2009-05-18,
User offline. Last seen 38 weeks 5 days ago.
Re: Contravariance for Ordering, PartialOrdering, and Equiv

On Mon, Aug 15, 2011 at 10:26 PM, Jeff Olson wrote:
> Can I make an impassioned plea to the powers that be to make
> scala.math.{Ordering, PartialOrdering, Equiv} contravariant in their type
> parameter? I know, having tried it, that the necessary code changes to the
> traits themselves are straightforward, if not trivial. However, after
> reading http://www.scala-lang.org/node/3786, I get the impression that there
> is some obscure technical obstruction having something to do with
> contravariant type-inference and F-bounded polymorphism. (I would be most
> interested if someone could explain it to me in more detail). How serious is
> this problem? Are there any easy workarounds? Is there a ticket open for
> this?
>
> That was the plea. Now for some passion: Of course, all these traits are
> naturally contravariant and having them invariant is nearly as bad as having
> List[T] be invariant. It is an embarrassing blight on an otherwise beautiful
> library (I was about to say language). I'm finding more and more of my code
> riddled with silly boilerplate like
>
> implicit val ordering2: Ordering[Bar] =
> implicitly[Ordering[Foo]].on(identity)
>
> when I need an ordering on Bar <: Foo and I have an implicit ordering on Foo
> (in the more annoying cases, Bar is something like
> SomeLongAnnoyingPrefix#SomeAbstractTypeThatIsReallyAFoo). And, of course, I
> have to do this for every different Bar that extends Foo. But at least
> asking for an implicit Ordering[Bar] and only supplying an Ordering[Foo]
> results in a compile time error. I ran into a more insidious bug last week
> when I was (unknowingly) asking for an implicit Equiv[Bar] when I had
> defined an implicit Equiv[Foo]. The code looked something like
>
> def assertEq[T](x: T, y: T)(implicit e: Equiv[T]) = ...
>
> implicit cmp: Equiv[Foo] = ...
>
> assertEq(q.x, p.x)
>
> As far as I was concerned, the type of the expressions q.x and p.x was Foo,
> and I had defined an implicit Equiv[Foo]. But the compiler figured out that
> T was some strange compiler generated type that happened to be a Foo, but
> had slightly more context, and therefore my implicit didn't apply--BUT, the
> compiler happily supplied my assertEq with the universal (equality based)
> Equiv[SomeStrangeCompilerType#ThatHappensToBeAFoo], and so my program
> compiled just fine. It took me a good number of hours to figure out why is
> wasn't doing what I intended.
>
> In the end my solution was to define my own contravariant Equiv[-T]. I fear
> I may go the route of defining my own Ordering and PartialOrdering as well
> if the standard library can't be fixed. Please don't make me do it!

Short answer: it's complicated.

https://github.com/scala/scala/wiki/Contravariance-and-Specificity

-jason

Jeff Olson
Joined: 2011-06-29,
User offline. Last seen 42 years 45 weeks ago.
Re: Contravariance for Ordering, PartialOrdering, and Equiv
Thanks for the link Jason. If I follow you correctly, it's not really complicated so much as it is a matter of deciding what it means for one implicit to be more specific than another when contravariance is involved. I see this issue now. Making Ordering contravariant allows me to write the folllowing:

class Foo
class Bar extends Foo

implicit val ord: Ordering[Foo] = new Ordering[Foo] { ... }
implicitly[Ordering[Bar]].compare(bar1, bar2)

However, if I want to add a more "specific" ordering for Bar

implicit val ord1: Ordering[Foo] = new Ordering[Foo] { ... }
implicit val ord2: Ordering[Bar] = new Ordering[Bar] { ... }
implicitly[Ordering[Bar]].compare(bar1, bar2)

I might be surprised to find that ord1 was chosen to be more specific that ord2 and was therefore supplied as the implicit (with no warning). I see.

Martin, help!!
Jeff Olson
Joined: 2011-06-29,
User offline. Last seen 42 years 45 weeks ago.
Re: Contravariance for Ordering, PartialOrdering, and Equiv
So to further clarify (mostly to myself), there is nothing preventing us from making Ordering and friends contravariant--indeed, they should be contravariant. This hasn't been done because it exposes a rather nasty issue (bug? feature? gotcha?) in the implicit resolution mechanism. This issue is present in other settings already as the following amusing example illustrates:

implicit def conv1(x: Any): String = "foo"
implicit def conv2(x: Int): String = "bar"

println(implicitly[Int => String].apply(1)) // prints bar as expected

versus:

implicit val conv1: Any => String = { _ => "foo" }
implicit val conv2: Int => String = { _ => "bar" }

println(implicitly[Int => String].apply(1)) // prints foo!!


Okay, I know that https://issues.scala-lang.org/browse/SI-2509 was closed as a won't fix, but it seems to me this issue needs to be addressed in some fashion or another. Are there any other open tickets, or proposals on how to resolve this?
extempore
Joined: 2008-12-17,
User offline. Last seen 35 weeks 3 days ago.
Re: Contravariance for Ordering, PartialOrdering, and Equiv
On 8/16/11 8:26 AM, Jeff Olson wrote:
> Okay, I know that https://issues.scala-lang.org/browse/SI-2509 was
> closed as a won't fix, but it seems to me this issue needs to be
> addressed in some fashion or another. Are there any other open
> tickets, or proposals on how to resolve this?

The gist of the proposal at https://github.com/scala/scala/wiki/Contravariance-and-Specificity is that implicit search should instantiate type parameters with the deepest-in-the-sense-of-subclassing types which are sound, regardless of the variance positions.  That would mean this:

  implicit val conv1: Any => String = { _ => "foo" }
  implicit val conv2: Int => String = { _ => "bar" }

chooses conv2 if possible.

Derek Williams 3
Joined: 2011-08-12,
User offline. Last seen 42 years 45 weeks ago.
Re: Contravariance for Ordering, PartialOrdering, and Equiv
On Mon, Aug 15, 2011 at 2:26 PM, Jeff Olson <jdolson [at] rgmadvisors [dot] com> wrote:
In the end my solution was to define my own contravariant Equiv[-T]. I fear I may go the route of defining my own Ordering and PartialOrdering as well if the standard library can't be fixed. Please don't make me do it!


I was able to come up with a possible workaround. I haven't tested it out enough to determine if there are any unseen issues, but it seems to work:
implicit def contraOrdering[A](implicit ord: Ordering[_ >: A]): Ordering[A] = ord.asInstanceOf[Ordering[A]]

class OrderingOps[A](lhs: A) {   def <[B >: A](rhs: B)(implicit ord: Ordering[B]) = ord.lt(lhs, rhs)   def <=[B >: A](rhs: B)(implicit ord: Ordering[B]) = ord.lteq(lhs, rhs)   def >[B >: A](rhs: B)(implicit ord: Ordering[B]) = ord.gt(lhs, rhs)   def >=[B >: A](rhs: B)(implicit ord: Ordering[B]) = ord.gteq(lhs, rhs)   def equiv[B >: A](rhs: B)(implicit ord: Ordering[B]) = ord.equiv(lhs, rhs)   def max[B >: A](rhs: B)(implicit ord: Ordering[B]): B = ord.max(lhs, rhs)   def min[B >: A](rhs: B)(implicit ord: Ordering[B]): B = ord.min(lhs, rhs) }
implicit def orderingOps[A](value: A) = new OrderingOps(value)

Should be able to do the same with Equiv and PartialOrdering as well. The little bit of testing I have done is here:
https://gist.github.com/1149463
--
Derek Williams
dcsobral
Joined: 2009-04-23,
User offline. Last seen 38 weeks 5 days ago.
Re: Contravariance for Ordering, PartialOrdering, and Equiv

On Tue, Aug 16, 2011 at 12:26, Jeff Olson wrote:
> So to further clarify (mostly to myself), there is nothing preventing us
> from making Ordering and friends contravariant--indeed, they should be
> contravariant. This hasn't been done because it exposes a rather nasty issue
> (bug? feature? gotcha?) in the implicit resolution mechanism.

In fact, Scalaz declares it as contra-variant:

http://scalaz.github.com/scalaz/scalaz-2.9.0-1-6.0.1/doc/index.html#scal...

Copyright © 2012 École Polytechnique Fédérale de Lausanne (EPFL), Lausanne, Switzerland