scala - recursividad - que es una funcion recursiva en programacion

Comportamiento extraño que intenta convertir clases de casos a listas heterogéneas recursivamente con Shapeless

Question

Me quedé despierto demasiado tarde la noche anterior tratando de resolver este problema de Shapeless y me temo que si no me lo quito de la boca me comeré la noche, así que aquí va.

En esta versión minimizada, solo estoy definiendo una clase de tipo que convertirá recursivamente las clases de casos en listas heterogeneous :

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
}

¡Vamos a probarlo! Primero necesitamos algunas clases de casos:

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)

Y luego (note que he limpiado la sintaxis de tipo por el simple hecho de no ser un lío totalmente ilegible):

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

Hasta ahora tan bueno. Pero entonces:

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

La B no se convirtió. Si -Xlog-implicits este es el último mensaje:

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

Lo que no tiene sentido para headCaseClassDeepHLister : headCaseClassDeepHLister debería poder generar DeepHLister[B :: HNil] bien, y lo hace si lo preguntas directamente.

Esto sucede tanto en la versión 2.10.4 como en la 2.11.2, y con la versión 2.0.0 y la versión maestra. Estoy bastante seguro de que esto tiene que ser un error, pero no estoy descartando la posibilidad de que esté haciendo algo mal. ¿Alguien habia visto algo como esto antes? ¿Hay algún problema con mi lógica o alguna restricción en el Generic me estoy perdiendo?

Bien, gracias por escuchar, tal vez ahora pueda ir a leer un libro o algo.

Answer 1

Esto ahora funciona más o menos según lo escrito usando las recientes compilaciones SNAPSHOT sin forma-2.1.0, y se ha agregado un pariente cercano de la muestra en esta pregunta como example .

El problema con el original es que cada expansión de un Generic introduce un nuevo tipo de HList en la resolución implícita de las instancias de clase de tipo DeepHLister y, en principio, podría producir un tipo de HList relacionado pero más complejo que el que se vio anteriormente. La misma resolución. Esta condición dispara el verificador de divergencias y aborta el proceso de resolución.

Los detalles exactos de por qué sucede esto para D pero no para C se esconden en los detalles de la implementación del tipógrafo de Scala pero, en una aproximación aproximada, el diferenciador es que durante la resolución para C vemos la B (más grande) antes de la A (más pequeño) para que el verificador de divergencias esté contento de que nuestros tipos estén convergiendo; a la inversa, durante la resolución para D , vemos la A (más pequeña) antes de la B (más grande), por lo que el verificador de divergencias (de forma conservadora) salta.

La solución para esto en 2.1.0 sin forma es el constructor de tipo Lazy recientemente mejorado y la infraestructura de macro implícita asociada. Esto permite mucho más control del usuario sobre la divergencia y admite el uso de la resolución implícita para construir los valores implícitos recursivos que son cruciales para la capacidad de derivar automáticamente las instancias de clase de tipo para los tipos recursivos. Se pueden encontrar muchos ejemplos de esto en la base de código sin forma, en particular la infraestructura de derivación de clase de tipo reelaborada y la implementación de Scrap Your Boilerplate, que ya no requieren soporte de macros dedicado, pero se implementan completamente en términos de los primitivos Generic y Lazy . Se pueden encontrar varias aplicaciones de estos mecanismos en el subproyecto de ejemplos sin forma.

Answer 2

Tomé un enfoque ligeramente diferente.

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
}

Probado con el siguiente código:

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
}