Scala higher type types in implicit def fail with "cannot find implicit value"

Question

I use implicit def to create a recursive HList type to match several types of higher HList types. I am very inspired by this post .

This code works fine:

 sealed trait HList { type Plus[L <: HList] <: HList } class HNil extends HList { type Plus[L <: HList] = L def ::[T](v: T) = HCons(v, this) } case class Appender[L1 <: HList, L2 <: HList, R <: HList](fn: (L1, L2) => R) { def apply(l1: L1, l2: L2) = fn(l1, l2) } object HNil extends HNil object HList { def ++[L1 <: HList, L2 <: HList](l1: L1, l2: L2)(implicit f: Appender[L1, L2, L1#Plus[L2]]): L1#Plus[L2] = f(l1, l2) implicit def nilAppender[L <: HList]: Appender[HNil, L, L] = Appender((v: HNil, l: L) => l) implicit def consAppender[T, L1 <: HList, L2 <: HList, R <: HList](implicit f: Appender[L1, L2, R]): Appender[HCons[T, L1], L2, HCons[T, R]] = { Appender[HCons[T, L1], L2, HCons[T, R]]((l1: HCons[T, L1], l2: L2) => HCons(l1.head, f(l1.tail, l2))) } } case class HCons[T, U <: HList](head: T, tail: U) extends HList { type Plus[L <: HList] = HCons[T, U#Plus[L]] def ::[V](v: V) = HCons(v, this) } import HList._ val hlist1 = 2.0 :: "hi" :: HNil val hlist2 = 1 :: HNil val sum = ++(hlist1, hlist2) println("last element : " : + sum.tail.tail.head) // prints last element : 1" 

Now I don’t know why, but if I try to add the ++ method to HCons , which simply calls the existing HList.++ method, this DOES NOT work:

  case class HCons[T, U <: HList](head: T, tail: U) extends HList { type Plus[L <: HList] = HCons[T, U#Plus[L]] def ::[V](v: V) = HCons(v, this) def ++[L2 <: HList](l2: L2) = HList.++(this,l2) } 

I get this compilation error:

 could not find implicit value for parameter f: Appender[HCons[T,U],L2,HCons[T,U]#Plus[L2]] 

Because HCons is a subtype of HList , like the L1 type defined by HList. ++, I thought everything was in order.

I tried this, but this does not work better:

 implicit def consAppender[T, L1 <: HList, L2 <: HList, L3, R <: HList](implicit f: Appender[L1, L2, R], ev: L3 <:< HCons[T, L1]): Appender[HCons[T, L1], L2, HCons[T, R]] = { Appender[HCons[T, L1], L2, HCons[T, R]]((l1: L3, l2: L2) => HCons(l1.head, f(l1.tail, l2))) } 

What did I miss?

Thanks:)

Answer 1

From this, you can change the definition of the ++ method:

  def ++[L2 <: HList](l2: L2) = HList.++(this,l2) 

:

 def ++[L2 <: HList](l2: L2)(implicit f: Appender[HCons[T,U], L2, Plus[L2]]) = HList.++(this,l2) 

The compiler does not have enough information to select the correct implicit value inside the method definition, but when you pass the application from outside, this example should pass:

 val hlist1 = 2.0 :: "hi" :: HNil val hlist2 = 1 :: HNil println(hlist1++hlist2) 

Update 1: In the ++ method on HCons we call the HList.++ method, which requires an implicit parameter. This parameter must be of type Appender[HCons[T, U], L2, HCons[T, U#Plus[L2]]] . The compiler can populate this implicit parameter from HList.consAppender , but this, in turn, requires another implicit parameter of type Appender[U, L2, U#Plus[L2]] . This is a parameter that the compiler cannot detect by itself. Knowing this, the above code can be simplified to:

 def ++[L2 <: HList](l2: L2)(implicit f: Appender[U, L2, U#Plus[L2]]): Plus[L2] = HList.++(this, l2) 

Update 2: the compiler must fill in implicit parameters on the call site, in our case, inside the HCons.++ method (you can check, for example, using scalac -Xprint:typer ). It can choose from implicits by providing two types of appender:

 Appender[HNil, L, L] Appender[HCons[T, L1], L2, HCons[T, R]] 

The first can be used only if a parameter of type U is equal to HNil , and the other only when U is equal to HCons . But this information is not available inside HCons.++ . He only knows that U <: HList , but does not know which HList implementation is and therefore fails.