Why high order implicits are ignored in some cases?

Question

I got a strange compiler error about an implicit that is actually present but could not be found for a reason. So I've build a small test case that reproduces mysterious behaviour.

trait Hide {
  type T
}
object HideString extends Hide {
  override type T = String
}
object HideBool extends Hide {
  override type T = Boolean
}

Simple type used as unambiguous target for implicit conversions.

def id[H <: Hide, C](x : C)(implicit ev : C => H#T) : H#T = ev(x)
def drop[H <: Hide, C](x : C)(implicit ev : C => H#T) : Int = {
  println(ev(x))
  1
}
def idSeq[H <: Hide, C](x : Seq[C])(implicit ev : Seq[C] => Seq[H#T]) : Seq[H#T] = ev(x)
def dropSeq[H <: Hide, C](x : Seq[C])(implicit ev : Seq[C] => Seq[H#T]) : Int = {
  println(ev(x))
  1
}

Methods that rely on implicit conversions. It is basically 2x2 matrix. id methods returns converted type and drop methods use conversion internally and return some constant. Normal methods operates on exact implicitly converted type and Seq methods operates on sequences.

implicit def exString(x : String) : HideString.type#T = x
implicit def highString[F[_]](x : F[String]) : F[HideString.type#T] = x

Above implicit conversions highString is defined with higher-order type.

val s1 = id("sdf")
val s2 = drop("aero")

val r1 = idSeq(Seq("a", "bc"))
val r2 = dropSeq(Seq("i", "IO"))

Trying to actually use conversions brings me an error:

ImplicitResolution.scala:98: error: No implicit view available from Seq[String] => Seq[test.implicits.HighReduction.Hide#T].
  val r2 = dropSeq(Seq("i", "IO"))

That could be summarized in the following matrix:

|        | id   | drop |
|--------+------+------|
| normal | pass | pass |
| seq    | pass | fail |

If I use precisely defined implicit conversion for dropSeq method it is found normally:

implicit def seqBool(x : Seq[Boolean]) : Seq[HideBool.type#T] = x

val a1 = idSeq(Seq(true, false))
val a2 = dropSeq(Seq(false, true))

And furthermore if I explicitly specify implicit argument dropSeq began to work:

val r2i = dropSeq(Seq("i", "IO"))(highString[Seq] _)

And that is the strangest thing. highString implicit fits all requirements. And it is declared as implicit, so it should be found by the compiler. And in case of idSeq it is actually found. So, why it is ignored in the dropSeq case?

Answer 1

In your case the only difference between idSeq and dropSeq is the return type: you have hit some corner case in the Scala compiler which is worth signaling to the Scala community.

That said, your idSeq has wrong signature: H#X doesn't mean the X type for the specified H type, but rather X for any instance of H (not the one that has been resolved by the compiler, see Daniel Sobral explanation here What does the `#` operator mean in Scala?)

What you probably want to do is to establish a relation between H and your result type, which is easier if you introduce type aliases to get a more readable signature:

object Hide {
  type HideAux[X] = Hide { type T = X}
}

You can then re-write your code like this:

  def idSeq[B,H <: HideAux[B], C](x : Seq[C])(implicit ev : Seq[C] => Seq[B]) : Seq[B] = ev(x)
  def dropSeq[B,H <: HideAux[B], C](x : Seq[C])(implicit ev : Seq[C] => Seq[B]) : Int = {
    println(ev(x))
    1
  }

This code compile, and notice also that if you correctly use generic and typeclasses, you won't need two different methods id and idSeq because the dynamic behaviour is going to be provided by typeclass itself.