geq.scala

object scope {
  // int
  class I

  // list
  sealed trait L[A]
  class N[A] extends L[A]
  class C[A] extends L[A]

  // tree
  class T[A]

  // hlist
  trait HList
  class HNil extends HList
  class :*:[H, T <: HList] extends HList

  // coproduct
  trait Coproduct
  class CNil extends Coproduct
  class :+:[H, T <: Coproduct] extends Coproduct

  // eq
  trait E[A]

  object E {
    implicit val i: E[I] = ???

    implicit def g[A, R](implicit AR: G[A, R], R: GE[R]): E[A] = ???
  }

  // generic
  trait G[A, R]

  object G {
    implicit def l[A]: G[L[A], N[A] :+: C[A] :+: CNil] = ???
    implicit def n[A]: G[N[A], HNil] = ???
    implicit def c[A]: G[C[A], A :*: L[A] :*: HNil] = ???

    implicit def t[A]: G[T[A], A :*: L[T[A]] :*: HNil] = ???
  }

  // geq
  trait GE[R]

  object GE {
    implicit val hnil: GE[HNil] = ???
    implicit def hcons[H: GE, T <: HList: GE]: GE[H :*: T] = ???

    implicit val cnil: GE[CNil] = ???
    implicit def ccons[H: GE, T <: Coproduct: GE]: GE[H :+: T] = ???

    implicit def value[A](implicit A: => E[A]): GE[A] = ???
  }
}

import scope._

// Here, `implicitly[E[T[I]]]` cannot compile due to this error:
//
//   diverging implicit expansion for type => scope.E[scope.T[scope.I]]
//   starting with method value in object GE
//
// And we can solve this problem for adding `implicit def el[A]: E[L[A]] = implicitly`.
//
// Trying to expand `implicitly[E[T[I]]]` by hand shows the reason clearly.

lazy val expansion: E[T[I]] = E.g(
  G.t[I],
  GE.hcons(
    // {{ I:
    GE.value(E.i),
    // }}
    GE.hcons(
      // {{ L[T[I]]:
      GE.value(
        E.g(
          G.l[T[I]],
          GE.ccons(
            // {{ N[T[I]]:
            GE.value(E.g(G.n[T[I]], GE.hnil)),
            // }}
            GE.ccons(
              // {{ C[T[I]]:
              GE.value(
                E.g(
                  G.c[T[I]],
                  GE.hcons(
                    // {{ T[I]:
                    GE.value(expansion),
                    // }}
                    GE.hcons(
                      // {{ L[T[I]]:
                      // This `???` should be expanded to `E[L[T[I]]]` value, but the compiler tried to expand the value
                      // at the above line. So, it causes "diverging implicit expansion".
                      GE.value[L[T[I]]](???),
                      // }}
                      GE.hnil
                    )
                  )
                )
              ),
              // }}
              GE.cnil
            )
          )
        )
      ),
      // }}
      GE.hnil
    )
  )
)