Shapeless: recursive calls in typeclass

Question

What is the right way to implement recursive calls inside a shapeless typeclass method?

(An early caveat: I'm learning shapeless, so there may be obvious answers/alternatives I do not yet know. Any help is greatly appreciated!)

I have a typeclass which converts a case class into a nested structure of other objects—similar to and inspired by the ToMapRec example mentioned in this stackoverflow question—except that instead of returning a potentially-recursive Map, it returns a case class composed of potentially recursive members. So instead of converting an instance of MyType:

trait GetsConverted
case class MyType(someData: String, one: GetsConverted, other: GetsConverted) extends GetsConverted
case class MyOtherType(blah: AndSoOn) extends GetsConverted
case class AndSoOn(eventualFinalValue: Int)

into a possibly recursive/nested Map[String,Any](as in the other question), it returns something like an instance of:

case class ReturnType(name: String, data: Option[Any], more: Set[ReturnType])

To create the more member seems to require making a recursive call inside the type class. But calling the conversion method of the type class inside of another method requires threading in the implicit parameters for all types inside that function to the outermost call. So instead of a typeclass conversion like:

implicit def hconsToMapRec0[K, V, A <: HList, B <: HList](implicit
  wit: Witness.Aux[K],
  gen: LabelledGeneric.Aux[V, R],
  tmrH: Lazy[ToMapRec[A]],
  tmrT: Lazy[ToMapRec[B]]
): ReturnType = ???

a depth three method (I'm guessing) would require a function signature something like:

implicit def hconsToMapRec0[K, V, A <: HList, B <: HList, W, C <: HList, D <: HList, X, E <: HList, F <: HList](implicit
  wit: Witness.Aux[K],
  gen0: LabelledGeneric.Aux[V, A],
  tmrH0: Lazy[ToMapRec[A]],
  tmrT0: Lazy[ToMapRec[B]],
  gen1: LabelledGeneric.Aux[W, C],
  tmrH1: Lazy[ToMapRec[C]],
  tmrT1: Lazy[ToMapRec[D]],
  gen2: LabelledGeneric.Aux[X, E],
  tmrH2: Lazy[ToMapRec[E]],
  tmrT2: Lazy[ToMapRec[F]]
): ReturnType = ???

Or possibly worse. In general, this approach would require a method which has its implicit parameters multiplied by as many levels of depth in this recursion. And the number of levels of depth is only known at runtime. So this can't be the way to do that.

This feels analogous to the hard-coded 22-arity methods in the scala collections library. Since the raison d'être for Shapeless is to abstract over arity, this seems like a problem calling for more Shapeless-foo that I've learned so far.

So the question is: how would you write a shapeless typeclass to convert an arbitrary case class structured something like the MyType example above into a recursively defined value like:

ReturnType("MyType", Some("someData"), Set(
  ReturnType("MyOtherType", None, Set(
    ReturnType("AndSoOn", Some(10), Set())
  )), 
  ReturnType("MyOtherType", None, Set(
    ReturnType("AndSoOn", Some(20), Set())
  ))
))

Answer 1

I managed to get something close to your example with the implementation below. Most of it is similar to the answer to this question. The difference is that it converts to the ReturnType and I also added a few cases for the Coproduct case (which is the generic representation of a sealed trait).

So with the following code:

val gen = LabelledGeneric[GetsConverted]
val m = MyType("someData", MyOtherType(AndSoOn(10)), MyOtherType(AndSoOn(20)))
val tmr = ToReturnTypeRec[gen.Repr]
val returnType = tmpr(gen.to(m))

You get the result

ReturnType(MyType,Some(someData),Set(
     ReturnType(MyOtherType,None,Set(
         ReturnType(,Some(20),Set())
     )),
     ReturnType(MyOtherType,None,Set(
         ReturnType(,Some(10),Set())
     ))
))

Here is the implementation:

trait ToReturnTypeRec[L] { def apply(l: L): ReturnType }

trait LowPriorityToReturnTypeRec {
implicit def hconsToReturnTypeRec1[K <: Symbol, V, T <: HList](implicit
    wit: Witness.Aux[K],
    tmrT: ToReturnTypeRec[T]
  ): ToReturnTypeRec[FieldType[K, V] :: T] = new ToReturnTypeRec[FieldType[K, V] :: T] {
    def apply(l: FieldType[K, V] :: T): ReturnType =
      tmrT(l.tail) match {
        case ReturnType(n,d,m) => ReturnType("", Some(l.head), m)
      }
  }
}

object ToReturnTypeRec extends LowPriorityToReturnTypeRec {
  def apply[T](implicit tmr: ToReturnTypeRec[T]) = tmr
  implicit val hnilToReturnTypeRec: ToReturnTypeRec[HNil] = new ToReturnTypeRec[HNil] {
    def apply(l: HNil): ReturnType = ReturnType("", None, Set())
  }

  implicit def hconsToReturnTypeRec0[K <: Symbol, V, T <: HList, R](implicit
    // wit: Witness.Aux[K],
    gen: LabelledGeneric.Aux[V, R],
    tmrH: Lazy[ToReturnTypeRec[R]],
    tmrT: ToReturnTypeRec[T]
  ): ToReturnTypeRec[FieldType[K, V] :: T] = new ToReturnTypeRec[FieldType[K, V] :: T] {
    def apply(l: FieldType[K, V] :: T): ReturnType =
      tmrT(l.tail) match {
        case ReturnType(n,d,m) => ReturnType(n, d, m + tmrH.value(gen.to(l.head)))
      }
  }

  implicit val cnillToReturnTypeRec: ToReturnTypeRec[CNil] = new ToReturnTypeRec[CNil] {
    def apply(c: CNil): ReturnType = ReturnType("Impossible", None, Set())
  }

  implicit def cconsToReturnTypeRec0[K <: Symbol, V <: Product, T <: Coproduct](implicit
    wit: Witness.Aux[K],
    tmrH: Lazy[ToReturnTypeRec[V]],
    tmrT: Lazy[ToReturnTypeRec[T]]
  ): ToReturnTypeRec[FieldType[K,V] :+: T] = new ToReturnTypeRec[FieldType[K, V] :+: T] {
    def apply(c: FieldType[K,V] :+: T): ReturnType = {
      c match {
        case Inl(h) => tmrH.value(h) match {
          case ReturnType(_,d,m) => ReturnType(wit.value.name, d, m)
        }
        case Inr(t) => tmrT.value(t)
      }
    }
  }

  implicit def genericToReturnTypeRec[P, R]( implicit
    gen: LabelledGeneric.Aux[P, R],
    tmr: Lazy[ToReturnTypeRec[R]]
  ): ToReturnTypeRec[P] = new ToReturnTypeRec[P] {
    def apply(p: P): ReturnType = tmr.value(gen.to(p))
  }
}