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 :)

Greed

I didn't try to follow what you're doing, but the : HList in line three is a red flag. HList is pretty much useless as a static type for anything. – Meehan

Thanks, in fact it is overloaded by case classes inheriting from HList – Greed

I've removed it for less confusion but the behavior is the same – Greed

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.

Pinpoint

Update 1 version is not working : could not find implicit value for parameter f: Appender[HCons[T,U],L2,HCons[T,U]#Plus[L2]] – Greed

Not sure where's the problem in that, it works for me (using Scala 2.11.6). We could dig into it deeper, but I'm happy as long as the first version is working for you. – Pinpoint