How to overload generic method with different evidence without ambiguity?

Question

I have a customized compare methods that takes two parameters. One of them are expected to be implicitly convertible to another:

object Test extends App {
  def compare[T1, T2](a: T1, b: T2)(implicit ev: T1 => T2) = compareImpl[T2](ev(a), b)
  def compare[T1, T2](a: T1, b: T2)(implicit ev: T2 => T1) = compareImpl[T1](a, ev(b))

  def compareImpl[T](a: T, b: T) = a == b

  case class Foo(s: String)
  case class Bar(s: String)

  implicit def foo2bar(f: Foo): Bar = Bar(f.s)

  println(compare(Foo("hello"), Bar("hello")))

}

However this snippet gives me error:

error: ambiguous reference to overloaded definition,
       both method compare in object Test of type [T1, T2](a: T1, b: T2)(implicit ev: T2 => T1)Boolean
       and  method compare in object Test of type [T1, T2](a: T1, b: T2)(implicit ev: T1 => T2)Boolean
       match argument types (Test.Foo,Test.Bar) and expected result type Any
         implicit def foo2bar(f: Foo): Bar = Bar(f.s)

If I remove the second compare, it works, but then if I do compare(Bar("hello), Foo("hello")) it won't compile.

How can I have these two versions without ambiguity?

Coddle

The problem is that, after type erasure, both methods are strictly the same. BTW, even without erasure, the call site may be ambiguos what if a I compare(1, "1") And there are both Int => String & String => Int. IMHO, too much magic is problematic here. – Hartz

Answer 1

Solution without macros (it's based on type classes)

  def compare[T1, T2](a: T1, b: T2)(implicit cmp: Compare[T1, T2]) = (compareImpl[cmp.T] _).tupled(cmp(a, b))
  def compareImpl[T](a: T, b: T) = a == b

  trait Compare[T1, T2] {
    type T
    type Out = (T, T)
    def apply(a: T1, b: T2): Out
  }

  object Compare {
    type Aux[T1, T2, T0] = Compare[T1, T2] { type T = T0 }
    def instance[T1, T2, T0](f: (T1, T2) => (T0, T0)): Aux[T1, T2, T0] = new Compare[T1, T2] {
      override type T = T0
      override def apply(a: T1, b: T2): Out = f(a, b)
    }

    implicit def directCompare[T1, T2](implicit ev: T1 => T2): Aux[T1, T2, T2] = instance((a, b) => (ev(a), b))
    implicit def reverseCompare[T1, T2](implicit ev: T2 => T1): Aux[T1, T2, T1] = instance((a, b) => (a, ev(b)))
  }

  case class Foo(s: String)
  case class Bar(s: String)

  implicit def foo2bar(f: Foo): Bar = Bar(f.s)

  println(compare(Foo("hello"), Bar("hello"))) // true

Or you can even prioritize direct and reverse directions if you want

  def compare[T1, T2](a: T1, b: T2)(implicit cmp: Compare[T1, T2]) = (compareImpl[cmp.T] _).tupled(cmp(a, b))
  def compareImpl[T](a: T, b: T) = a == b

  trait Compare[T1, T2] {
    type T
    type Out = (T, T)
    def apply(a: T1, b: T2): Out
  }

  trait LowPriorityCompare {
    type Aux[T1, T2, T0] = Compare[T1, T2] { type T = T0 }
    def instance[T1, T2, T0](f: (T1, T2) => (T0, T0)): Aux[T1, T2, T0] = new Compare[T1, T2] {
      override type T = T0
      override def apply(a: T1, b: T2): Out = f(a, b)
    }

    implicit def reverseCompare[T1, T2](implicit ev: T2 => T1): Aux[T1, T2, T1] = instance((a, b) => (a, ev(b)))
  }

  object Compare extends LowPriorityCompare {
    implicit def directCompare[T1, T2](implicit ev: T1 => T2): Aux[T1, T2, T2] = instance((a, b) => (ev(a), b))
  }

  case class Foo(s: String)
  case class Bar(s: String)

  implicit def foo2bar(f: Foo): Bar = Bar(f.s)
  implicit def bar2foo(f: Bar): Foo = Foo(f.s)

  println(compare(Foo("hello"), Bar("hello"))) // true

Oligarchy

Nice solution! One question - when the compiler looks up implicit Aux, it can match directCompare or reverseCompare since they have the same type erasure. How does it not create ambiguity? – Coddle

@texasbruce Implicits are resolved during typer phase and type erasure occurs during erasure phase typelevel.org/scala/docs/phases.html So during implicit resolution no types are erased yet. Type erasure is just irrelevant for implicit resolution. – Oligarchy

Answer 2

I ended up using macro because currently Scala does not have type lambda and it does generic type erasure, so no such thing will be supported out of the box.

Macro definition:

import scala.reflect.runtime.universe._
import scala.reflect.macros.blackbox.Context
import scala.language.experimental.macros
import scala.language.implicitConversions

def compare[T1, T2](a: T1, b: T2): Boolean = macro compareImpl[T1,T2]

def compareImpl[T1: c.WeakTypeTag, T2: c.WeakTypeTag](c: Context)(a: c.Expr[T1], b: c.Expr[T2]): c.Expr[Boolean] = {
  import c.universe._
  // Search for T1=>T2 first. If not found, search T2=>T1
  val f1 = c.inferImplicitValue(c.weakTypeOf[T1 => T2])
  if (f1.isEmpty) {
      val f2 = c.inferImplicitValue(c.weakTypeOf[T2 => T1])
      if(f2.isEmpty) {
          c.abort(c.enclosingPosition, s"Cannot find ${weakTypeOf[T1]}=> ${weakTypeOf[T2]}")
      }
      else {
          c.Expr(q"$f2.apply($b) == $a")
      }
  }
  else {
      c.Expr(q"$f1.apply($a) == $b")
  }
}

Test:

case class Foo(s: String)
case class Bar(s: String)

implicit def foo2bar(f: Foo): Bar = Bar(f.s)

println(compare(Foo("hello"), Bar("hello")))
println(compare(Bar("hello"), Foo("hello")))

Coddle

Answer 3

The problem here is because both of your compare functions are having exactly the same type parameter which is ambiguous for Scala compiler to figure out which one to use.

For example when you do a compare of compare[Foo, Bar] it is not clear for Scala compiler whether it should use the compare function with (implicit ev: T1 => T2) or the second one with (implicit ev: T2 => T1) , because both of Foo and Bar could be placed as T1 or T2.

In fact this is the reason when you remove one of the compare functions, it works. Because there is no overloaded version of compare function and Foo and Bar can be placed as T1 and T2 in your one and only compare function.

Here is an answer to another Stackoverflow question which is somehow related to your problem and it describes the problem in details:

https://mcmap.net/q/95583/-ambiguous-reference-to-overloaded-definition-one-vs-two-parameters

Crimmer

It is actually clear because there is only Foo=>Bar and no Bar=>Foo. The compiler is not able to distinguish them properly. It should be ambiguous only if the conversion evidence is bidirectional. – Coddle

Yes, this is clear for us but not the Scala compiler. And this is the reason when you remove one of compare functions it will actually works. The fact that made it ambiguous to Scala compiler is that both (implicit ev: T1 => T2) and (implicit ev: T2 => T1) can be point to the same foo2bar function which is ambiguous for Scala compiler. – Crimmer