Contravariance for Ordering, PartialOrdering, and Equiv

[Jeff Olson]

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]

Short answer: it's complicated.

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

-jason

[Jeff Olson]

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]

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?

[Paul Phillips]

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]

On Mon, Aug 15, 2011 at 2:26 PM, Jeff Olson <jdo...@rgmadvisors.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

[Daniel Sobral]

On Tue, Aug 16, 2011 at 12:26, Jeff Olson <jdo...@rgmadvisors.com> 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#scalaz.Order

--
Daniel C. Sobral

I travel to the future all the time.