Covariant "lookup" for contravariant typeclasses

[Blaisorblade]

@paulp's has often brought this up. From memory, he'd have wanted Ordering[X] to be preferred to Ordering[Any] in implicit lookup, even though Ordering is contravariant, because Ordering[X] is still "more specific" for X. I remember that I agreed with @paulp and disagreed with Martin,

This seems bigger in scope than anything we've considered up to now, but we might want to consider it anyway.

[Blaisorblade]

Again, see #14 for compatibility.

[non]

If we determined that this was possible within our compatibility guidelines I'd support it 💯

[paulp]

FYI the best rule I came up with is: implicit search first tries for an exact match, then follows the variance arrow the minimum possible distance. This rule would change how covariant types are selected as well, but it has the desirable quality of using the same rules for both directions.

[milessabin]

What @non said.

[Blaisorblade]

If we determined that this was possible within our compatibility guidelines I'd support it

This is certainly source-incompatible; given the result of #14, do we want -Zcontravariant-lookup (or similar), maybe as part of the default -Z flag?

[paulp]

I found the ticket. https://issues.scala-lang.org/browse/SI-7768

[paulp]

Here's some code I found lying around which accomplished nothing.

trait Ord[-T]

class OverloadSelection {
  // The return types vary to overcome "same type after erasure".
  def f(x: Ord[Iterable[Int]]): Int    = 1
  def f(x: Ord[     Seq[Int]]): Byte   = 2
  def f(x: Ord[    List[Int]]): Short  = 3

  println("Static overloading selection: " + List(
    f(new Ord[Iterable[Int]] { }),
    f(new Ord[     Seq[Int]] { }),
    f(new Ord[    List[Int]] { })
  ).mkString("  "))
}

class ImplicitSelection {
  implicit val Ord1: Ord[Iterable[Int]] = new Ord[Iterable[Int]] { override def toString = "1" }
  implicit val Ord2: Ord[     Seq[Int]] = new Ord[     Seq[Int]] { override def toString = "2" }
  implicit val Ord3: Ord[    List[Int]] = new Ord[    List[Int]] { override def toString = "3" }

  println("    Implicit value selection: " + List(
    implicitly[Ord[Iterable[Int]]],
    implicitly[Ord[     Seq[Int]]],
    implicitly[Ord[    List[Int]]]
  ).mkString("  "))
}

object Test {
  def main(args: Array[String]): Unit = {
    println("""
      |If there are several eligible arguments which match the
      |implicit parameter’s type, a most specific one will be
      |chosen using the rules of static overloading resolution.
      |  -- SLS 7.2, "Implicit Parameters"
      |""".stripMargin
    )
    new OverloadSelection
    new ImplicitSelection
  }
}

Here's a nice modernized example of how it burns to treat "Any" as the MOST SPECIFIC TYPE!

import java.util.function.Function;

public class C<A> {
    public <B> C<B> map (Function<? super A,B> f) { return null; }
    public <B> C<B> mapInv (Function<A,B> f) { return null; }
}

/****

% scala -Xexperimental -classpath .

scala> val c = new C[String]()
c: C[String] = C@14514713

scala> c mapInv (_.length)
res0: C[Int] = null

scala> c map (_.length)
<console>:9: error: missing parameter type for expanded function ((x$1) => x$1.length)
              c map (_.length)
                     ^
<console>:9: error: type mismatch;
 found   : java.util.function.Function[Any,Nothing] with Serializable
 required: java.util.function.Function[_ >: String, B]
Note: Nothing <: B (and java.util.function.Function[Any,Nothing] with Serializable <: java.util.function.Function[Any,Nothing]), but Java-defined trait Function is invariant in type R.
You may wish to investigate a wildcard type such as `_ <: B`. (SLS 3.2.10)
              c map (_.length)
                       ^

****/

[milessabin]

To resurrect this issue, please rework it as an issue/PR against Lightbend Scala (ie. scala/scala).