NestedRecursionDivergence

build.sbt

scalaVersion := "2.11.2"

libraryDependencies ++= Seq(
  "com.chuusai" %% "shapeless" % "2.1.0-SNAPSHOT" changing()
)

resolvers ++= Seq(
  Resolver.sonatypeRepo("releases"),
  Resolver.sonatypeRepo("snapshots")
)

scalacOptions ++= Seq("-Xlog-implicits")

NestedRecursion.scala

import shapeless._

sealed trait V
case class S(value: String) extends V
case class N(value: Int) extends V

sealed trait L
case class Vs(values: Seq[V]) extends L

object NestedRecursion {
  def main(args: Array[String]) {
    import Show._
    import ShowInstances.auto._
    implicitly[Show[V]]
    implicitly[Show[Seq[V]]]
    val vs: L = Vs(Seq(S("hi"), N(12)))
    vs.show
  }
}

Show.scala

trait Show[A] {
  def show(a: A): String
}

object Show {
  implicit def showString = Show[String] { identity }
  implicit def showInt = Show[Int] { _.toString }
  implicit def showDouble = Show[Double] { _.toString }
  implicit def showTuple[A: Show, B: Show] = Show[(A, B)] {
    case (a, b) => s"(${a.show}, ${b.show})"
  }
  implicit def showSeq[A: Show] = Show[Seq[A]] {
    as => as.map(_.show).mkString("Seq(", ", ", ")")
  }
  implicit class ShowOps[A](a: A)(implicit s: Show[A]) {
    def show: String = s.show(a)
  }
  def apply[A](s: A => String) = new Show[A] {
    def show(a: A): String = s(a)
  }
}

ShowInstances.scala

import shapeless._

trait ShowInstancesImp extends TypeClass[Show] {

  override def emptyProduct: Show[HNil] = Show { _ => "" }

  override def project[A, B](
    instance: Show[B],
    to: (A) => B,
    from: (B) => A): Show[A] =
    Show { a => instance.show(to(a)) }

  override def product[H, T <: HList](
    name: String,
    CH: Show[H],
    CT: Show[T]): Show[::[H, T]] =
    Show {
      case head :: tail =>
        val hs = CH.show(head)
        val ts = CT.show(tail)
        val end = if (ts.isEmpty) "" else s", $ts"
        s"$name: $hs$end"
    }

  override def emptyCoproduct: Show[CNil] =
    Show { _ => throw new Exception("Should never call instance for CNil") }

  override def coproduct[L, R <: Coproduct](
    name: String,
    CL: => Show[L],
    CR: => Show[R]): Show[:+:[L, R]] = Show {
    case Inl(left) => s"$name {${CL.show(left)}}"
    case Inr(right) => CR.show(right)
  }
}

object ShowInstances extends ShowInstancesImp

TypeClass.scala

import scala.language.higherKinds
import shapeless._
import shapeless.record.FieldType

trait TypeClassImpl[C[_]] {
  def emptyProduct: C[HNil]
  def product[H, T <: HList](
    name: String,
    CHead: C[H],
    CTail: C[T]): C[H :: T]
  def emptyCoproduct: C[CNil]
  def coproduct[L, R <: Coproduct](
    name: String,
    CL: => C[L],
    CR: => C[R]): C[L :+: R]
  def project[A, B](
    instance: C[B],
    to: A => B,
    from: B => A): C[A]
}

trait LowPriorityTypeClassConstructors[C[_]] extends TypeClassImpl[C] {

  trait Instance[Arg] extends DepFn0 {
    type Inner
    final type Out = C[Inner]
  }

  type Aux[Arg, In] = Instance[Arg] {
    type Inner = In
  }

  trait ProductInstance[Arg <: HList] extends Instance[Arg] {
    type Inner <: HList
  }

  type ProductAux[Arg <: HList, In <: HList] = ProductInstance[Arg] {
    type Inner = In
  }

  trait CoproductInstance[Arg <: Coproduct] extends Instance[Arg] {
    type Inner <: Coproduct
  }

  type CoproductAux[Arg <: Coproduct, In <: Coproduct] = CoproductInstance[Arg] {
    type Inner = In
  }

  implicit def emptyProductInstance[In <: HNil]: ProductAux[In, HNil] =
    new ProductInstance[In] {
      type Inner = HNil
      def apply() = emptyProduct
    }

  implicit def productInstance[Label <: Symbol, Head, Tail <: HList, TailInner <: HList](
    implicit witness: Witness.Aux[Label],
    cHead: C[Head],
    tailInstance: ProductAux[Tail, TailInner]): ProductAux[FieldType[Label, Head] :: Tail, Head :: TailInner] =
    new ProductInstance[FieldType[Label, Head]:: Tail] {
      type Inner = Head :: TailInner
      def apply() = product(witness.value.name, cHead, tailInstance())
    }

  implicit def emptyCoproductInstance[In <: CNil]: CoproductAux[In, CNil] =
    new CoproductInstance[In] {
      type Inner = CNil
      def apply() = emptyCoproduct
    }

  implicit def coproductInstance[Label <: Symbol, Left, Right <: Coproduct, RightInner <: Coproduct](
    implicit witness: Witness.Aux[Label],
    cLeft: Lazy[C[Left]],
    rightInstance: CoproductAux[Right, RightInner]): CoproductAux[FieldType[Label, Left] :+: Right, Left :+: RightInner] =
    new CoproductInstance[FieldType[Label, Left]:+: Right] {
      type Inner = Left :+: RightInner
      def apply() = coproduct(witness.value.name, cLeft.value, rightInstance())
    }
}

trait LazyGenerics {
  implicit def lazyLabelledGeneric[A](
    implicit lg: LabelledGeneric[A]): Lazy[LabelledGeneric.Aux[A, lg.Repr]] =
    Lazy { lg }
  implicit def lazyBareGeneric[A](
    implicit bg: Generic[A]): Lazy[Generic.Aux[A, bg.Repr]] =
    Lazy { bg }
}

trait TypeClass[C[_]] extends LowPriorityTypeClassConstructors[C] {

  trait FinalInstance[A] {
    def apply(): C[A]
  }

  implicit def genericInstance[A, Repr0, Repr1](
    implicit lg: Lazy[LabelledGeneric.Aux[A, Repr0]],
    bg: Lazy[Generic.Aux[A, Repr1]],
    instance: Aux[Repr0, Repr1]): FinalInstance[A] =
    new FinalInstance[A] {
      def apply() = project(instance(), bg.value.to, bg.value.from)
    }

  object auto extends LazyGenerics {
    implicit def derive[A](implicit instance: Lazy[FinalInstance[A]]): C[A] = instance.value()
  }
}