Странное поведение при попытке рекурсивно преобразовать классы дел в гетерогенные списки с помощью Shapeless

Question

Прошлой ночью я не спал слишком поздно, пытаясь выяснить эту проблему с бесформенным телом, и я боюсь, что он съест мой вечер, если я не получу его от своей груди, так что вот так.

В этой свернутой версии я просто определяю класс типов, который будет рекурсивно преобразовывать классы дел в гетерогенные списки:

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
}

Давайте попробуем это! Для начала нам нужны классы case:

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)

И затем (обратите внимание, что я очистил синтаксис типа, чтобы не было нечитаемого беспорядка):

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

Все идет нормально. Но потом:

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

B не был преобразован. Если мы включим -Xlog-implicits это последнее сообщение:

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

Что не имеет смысла для меняheadCaseClassDeepHLister должен быть в состоянии генерировать DeepHLister[B :: HNil] просто отлично, и это так, если вы спросите об этом напрямую.

Это происходит как в 2.10.4, так и в 2.11.2, а также с выпуском 2.0.0 и мастером. Я почти уверен, что это ошибка, но я не исключаю, что я делаю что-то не так. Кто-нибудь видел что-нибудь подобное раньше? Что-то не так с моей логикой или ограничением Generic Я скучаю?

Хорошо, спасибо, что выслушали, может быть, теперь я могу пойти почитать книгу или еще что-нибудь.

Answer 1

Теперь это работает более или менее так, как написано с использованием недавних сборок shapeless-2.1.0-SNAPSHOT, и в качестве примера добавлен близкий родственник примера в этом вопросе.

Проблема с оригиналом в том, что каждое расширение Generic вводит новый HList введите в неявное разрешение DeepHLister экземпляры классов типов и, в принципе, могут создавать HList тип, связанный с, но более сложный, чем какой-либо тип, замеченный ранее во время того же разрешения. Это условие отключает проверку расхождения и прерывает процесс разрешения.

Точные детали того, почему это происходит для D но не для C скрывается в деталях реализации проверки типов Scala, но, в грубом приближении, различие заключается в том, что во время разрешения для C мы видим B (больше) до A (меньше), так что средство проверки расхождения радует, что наши типы сходятся; наоборот, во время резолюции для D мы видим A (меньше) до B (больше), так что проверка дивергенции (консервативно) освобождает под залог.

Исправление для этого в бесформенной версии 2.1.0 - недавно улучшенный Lazy конструктор типа и связанная неявная макроинфраструктура. Это дает гораздо больший пользовательский контроль над расхождением и поддерживает использование неявного разрешения для создания рекурсивных неявных значений, которые имеют решающее значение для возможности автоматического получения экземпляров классов типов для рекурсивных типов. Многие примеры этого можно найти в бесформенной кодовой базе, в частности, переработанную инфраструктуру деривации классов типов и реализацию Scrap Your Boilerplate, которые больше не требуют поддержки выделенных макросов, но реализованы полностью с точки зрения Generic а также Lazy примитивы. Различные применения этих механизмов можно найти в подпроекте бесформенных примеров.

Answer 2

Я выбрал немного другой подход.

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
}

Протестировано с помощью следующего кода:

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
}