Scala higher kinded types in implicit def fails with "could not find implicit value"

Question

I'm using implicit def to build a recursive HList type, to match several kind of higher kinded types of HList. I'm heavily inspired by this post.

This code is working perfectly :

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 a ++ method on HCons, which simply calls existing HList.++ method, this is NOT working :

 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]]

As HCons is a subtype of HList, like the L1 type defined by HList.++, I was thinking it was OK.

I've tried this but that's not working 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

You should change your ++ method definition from this:

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

to this:

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

The compiler doesn't have enough information to select the right implicit value inside the method definition, but when you pass the appender from the 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 could fill this implicit parameter from HList.consAppender, but this in turn requires another implicit parameter of type Appender[U, L2, U#Plus[L2]]. This is the parameter that the compiler cannot discover itself. Knowing this, the code above 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 at the call site, in our case inside HCons.++ method (can be verified, e.g., with scalac -Xprint:typer). It can choose from implicits providing two appender types:

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

The first one can be used only if type parameter U is HNil, the other only when U is HCons. But this information is not available inside HCons.++. It only knows that U <: HList but doesn't know which implementation of HList it is and therefore fails.