22

I stayed up way too late last night trying to figure out this Shapeless issue and I'm afraid it's going to eat my evening if I don't get it off my chest, so here goes.

In this minimized version I'm just defining a type class that will recursively convert case classes into heterogeneous lists:

import shapeless._

trait DeepHLister[R <: HList] extends DepFn1[R] { type Out <: HList }

trait LowPriorityDeepHLister {
  type Aux[R <: HList, Out0 <: HList] = DeepHLister[R] { type Out = Out0 }

  implicit def headNotCaseClassDeepHLister[H, T <: HList](implicit
    dht: DeepHLister[T]
  ): Aux[H :: T, H :: dht.Out] = new DeepHLister[H :: T] {
    type Out = H :: dht.Out
    def apply(r: H :: T) = r.head :: dht(r.tail)
  }
}

object DeepHLister extends LowPriorityDeepHLister {
  implicit object hnilDeepHLister extends DeepHLister[HNil] {
    type Out = HNil
    def apply(r: HNil) = HNil
  }

  implicit def headCaseClassDeepHLister[H, R <: HList, T <: HList](implicit
    gen: Generic.Aux[H, R],
    dhh: DeepHLister[R],
    dht: DeepHLister[T]
  ): Aux[H :: T, dhh.Out :: dht.Out] = new DeepHLister[H :: T] {
    type Out = dhh.Out :: dht.Out
    def apply(r: H :: T) = dhh(gen.to(r.head)) :: dht(r.tail)
  }

  def apply[R <: HList](implicit dh: DeepHLister[R]): Aux[R, dh.Out] = dh
}

Let's try it out! First we need some case classes:

case class A(x: Int, y: String)
case class B(x: A, y: A)
case class C(b: B, a: A)
case class D(a: A, b: B)

And then (note that I've cleaned up the type syntax for the sake of this not being a totally unreadable mess):

scala> DeepHLister[A :: HNil]
res0: DeepHLister[A :: HNil]{
  type Out = (Int :: String :: HNil) :: HNil
} = DeepHLister$$anon$2@634bf0bf

scala> DeepHLister[B :: HNil]
res1: DeepHLister[B :: HNil] {
  type Out = (
    (Int :: String :: HNil) :: (Int :: String :: HNil) :: HNil
  ) :: HNil
} = DeepHLister$$anon$2@69d6b3e1

scala> DeepHLister[C :: HNil]
res2: DeepHLister[C :: HNil] {
  type Out = (
    ((Int :: String :: HNil) :: (Int :: String :: HNil) :: HNil) ::
    (Int :: String :: HNil) ::
    HNil
  ) :: HNil
} = DeepHLister$$anon$2@4d062faa

So far so good. But then:

scala> DeepHLister[D :: HNil]
res3: DeepHLister[D :: HNil] {
  type Out = ((Int :: String :: HNil) :: B :: HNil) :: HNil
} = DeepHLister$$anon$2@5b2ab49a

The B didn't get converted. If we turn on -Xlog-implicits this is the last message:

<console>:25: this.DeepHLister.headCaseClassDeepHLister is not a valid implicit value for DeepHLister[shapeless.::[B,shapeless.HNil]] because:
hasMatchingSymbol reported error: diverging implicit expansion for type DeepHLister[this.Repr]
starting with method headNotCaseClassDeepHLister in trait LowPriorityDeepHLister
              DeepHLister[D :: HNil]
                         ^

Which doesn't make sense to me—headCaseClassDeepHLister should be able to generate DeepHLister[B :: HNil] just fine, and it does if you ask it directly.

This happens on both 2.10.4 and 2.11.2, and with both the 2.0.0 release and master. I'm pretty sure this has to be a bug, but I'm not ruling out the possibility that I'm doing something wrong. Has anyone seen anything like this before? Is there something wrong with my logic or some restriction on Generic I'm missing?

Okay, thanks for listening—maybe now I can go read a book or something.

5
  • I have a similar problem with the DeepLister[B :: HNil]. I just copied the code 5 minutes ago, so I will investigate further.
    – EECOLOR
    Oct 12, 2014 at 19:19
  • This would be pretty easy with whitebox macros. Oct 12, 2014 at 21:04
  • 1
    @GuillaumeMassé, Right, for sure, but the goal is to restrict the use of macros to the few fundamental ones provided by Shapeless. Oct 13, 2014 at 2:08
  • Why do you restrict the use of macro if it can simplify your code ? Oct 13, 2014 at 2:10
  • 2
    I try to not use macro's because they make the code more difficult to understand and maintain. They require you to have knowledge of the macro domain, a domain that is quite complex. This domain might become easier to understand with Scala meta.
    – EECOLOR
    Oct 13, 2014 at 8:53

2 Answers 2

8

This now works more or less as written using recent shapeless-2.1.0-SNAPSHOT builds, and a close relative of the sample in this question has been added there as an example.

The problem with the original is that each expansion of a Generic introduces a new HList type into the implicit resolution of the DeepHLister type class instances and, in principle, could produce an HList type that is related to but more complex than some type seen previously during the same resolution. This condition trips the divergence checker and aborts the resolution process.

The exact details of why this happens for D but not for C is lurking in the details of the implementation of Scala's typechecker but, to a rough approximation, the differentiator is that during the resolution for C we see the B (larger) before the A (smaller) so the divergence checker is happy that our types are converging; conversely during the resolution for D we see the A (smaller) before the B (larger) so the divergence checker (conservatively) bails.

The fix for this in shapeless 2.1.0 is the recently enhanced Lazy type constructor and associated implicit macro infrastructure. This allows much more user control over divergence and supports the use of implicit resolution to construct the recursive implicit values which are crucial to the ability to automatically derive type class instances for recursive types. Many examples of this can be found in the shapeless code base, in particular the reworked type class derivation infrastructure and Scrap Your Boilerplate implementation, which no longer require dedicated macro support, but are implemented entirely in terms of the Generic and Lazy primitives. Various applications of these mechanisms can be found in the shapeless examples sub-project.

2
  • Are there changes to this for shapeless 2.3.2? The example doesn’t compile it complains about the return types of the 2 head* implicit... l’m using scale 2.11.11
    – Damian
    Nov 30, 2017 at 16:50
  • If you can reproduce an error with 2.11.11 please report it on the shapeless issue tracker. Dec 1, 2017 at 18:56
7

I took a slightly different approach.

trait CaseClassToHList[X] {
  type Out <: HList
}

trait LowerPriorityCaseClassToHList {
  implicit def caseClass[X](implicit gen: Generic[X]): CaseClassToHList[X] {
    type Out = generic.Repr
  } = null
}

object CaseClassToHList extends LowerPriorityCaseClassToHList {
  type Aux[X, R <: HList] = CaseClassToHList[X] { type Out = R }

  implicit def caseClassWithCaseClasses[X, R <: HList](
    implicit toHList: CaseClassToHList.Aux[X, R],
    nested: DeepHLister[R]): CaseClassToHList[X] {
    type Out = nested.Out
  } = null
}

trait DeepHLister[R <: HList] {
  type Out <: HList
}

object DeepHLister {

  implicit def hnil: DeepHLister[HNil] { type Out = HNil } = null

  implicit def caseClassAtHead[H, T <: HList](
    implicit head: CaseClassToHList[H],
    tail: DeepHLister[T]): DeepHLister[H :: T] {
    type Out = head.Out :: tail.Out
  } = null

  def apply[X <: HList](implicit d: DeepHLister[X]): d.type = null
}

Tested with the following code:

case class A(x: Int, y: String)
case class B(x: A, y: A)
case class C(b: B, a: A)
case class D(a: A, b: B)

object Test {

  val z = DeepHLister[HNil]
  val typedZ: DeepHLister[HNil] {
    type Out = HNil
  } = z

  val a = DeepHLister[A :: HNil]
  val typedA: DeepHLister[A :: HNil] {
    type Out = (Int :: String :: HNil) :: HNil
  } = a

  val b = DeepHLister[B :: HNil]
  val typedB: DeepHLister[B :: HNil] {
    type Out = ((Int :: String :: HNil) :: (Int :: String :: HNil) :: HNil) :: HNil
  } = b

  val c = DeepHLister[C :: HNil]
  val typedC: DeepHLister[C :: HNil] {
    type Out = (((Int :: String :: HNil) :: (Int :: String :: HNil) :: HNil) :: (Int :: String :: HNil) :: HNil) :: HNil 
  } = c

  val d = DeepHLister[D :: HNil]
  val typedD: DeepHLister[D :: HNil] {
    type Out = ((Int :: String :: HNil) :: ((Int :: String :: HNil) :: (Int :: String :: HNil) :: HNil) :: HNil) :: HNil
  } = d
}
1
  • Hey @EECOLOR, thanks—I've been meaning to spend more time looking at this, and didn't realize that the bounty was expiring. When I get some time I'll add another bounty. Oct 17, 2014 at 13:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.