Appendix to Shapeless#902

shapeless-lazy-issue.md

The repro in shapeless#902 above is very simplified from my real use-case; perhaps I should just do something different upstream to avoid this, but nevertheless that behavior seems unexpected.

More context on my real use-case, fwiw:

• A is actually OHList ("Options HList"), where each element in the underlying HList is wrapped in Option[_], and some relevant functionality is exposed.
• TC is actually a comparator type-class Cmp, which defines logic for determining whether two instances of type T are equal:
  • If they are not equal, it returns a customizable output-type Δ representing the computed diff.

    trait Cmp[T] { type Δ; def apply(l: T, r: T): Option[Δ] }

  • In truth, it is an alias for a more general version, CanEq[L, R], where the two types being compared can be different

ADT of HLists where all elements are wrapped in Option[_]

I am basically making an ADT of:

• OptionsHList[L <: HList] := Empty[L] | NonEmptyOptionsHList[L]
  • an HList where each element is wrapped in Option[_]
  • split into cases where either:
    • all elements are None, or
    • at least one element is Some
• NonEmptyOptionsHList[H :: T] := (Some[H] :: OptionsHList[T]) | (None :: NonEmptyOptionsHList[T])
  • an OptionsHList where at least one element is Some:
    • can begin with a Some, and have any configuration of Nones and Somes in the tail, or
    • can begin with None, in which case at least one element in the tail must be Some
• Empty[H :: T] := None :: Empty[T]

Number of inhabitants

Some rough "number of inhabitants" math, just based on which elements are Some vs None (ignoring how many possible values can inhabit Some for each element-type):

• |OptionsHList[L]| = 2^N (where N is the length of HList L), because:
  • |Empty[L]| = 1 (one possible list of N Nones)
  • |NonEmptyOptionsHList[L]| = 2^N - 1 = 2^(N-1) + (2^(N-1) - 1)
    • 2^(N-1) is the number of possibilities for the first case, Some[H] :: OptionsHList[T]
      • each of the N-1 elements in the tail can be None or Some
    • 2^(N-1) - 1 is the second case, None :: NonEmptyOptionsHList[T]
      • the tail can be any of 2^(N-1) possible OptionsHLists, except for the one Empty instance

The math also works if you take into account the number of inhabitants of each underlying element type, but I'll stop there 😀.

z-version-0.md

Original version of shapeless#902:

scalafiddle

Scala 2.12.8, Shapeless 2.3.3 (also tried from #797 branch)

Source

import shapeless._

// Type that provides functionality in terms of a given HList type
// - Is conceptually `Generic` in terms of the wrapped HList
// - Generic HNil instance is provided
sealed trait A[+L <: HList]
object A {
  implicit val generic: Generic.Aux[A[HNil], HNil] = ???
}

// Type-class mapping an input type to an output type. HNil ⇒ CNil instance is provided
trait TC[In] { type Out }
object TC {
  type Aux[In, Out_] = TC[In] { type Out = Out_ }
  implicit def hnil[L <: HNil]: TC.Aux[L, CNil] = null
}

// If `T` is generic, and its generic repr has a `TC`, provide a `TC` for `T` with the same `Out` type
// Eager and Lazy versions are provided; the Lazy version does not work as expected
object derive {
  implicit def eager_[T, L <: HList](implicit g: Generic.Aux[T, L], tc:      TC[L]) : TC.Aux[T, tc      .Out] = null  // 👌🏻
  implicit def lazy_ [T, L <: HList](implicit g: Generic.Aux[T, L], tc: Lazy[TC[L]]): TC.Aux[T, tc.value.Out] = null  // 🐉
}

object testEager {
  import derive.eager_
  the[TC    [A[HNil]      ]]  // ✅
  the[TC.Aux[A[HNil], CNil]]  // ✅
}
object testLazy {
  import derive.lazy_
  the[TC    [A[HNil]      ]]  // ✅
  the[TC.Aux[A[HNil], CNil]]  // 🚫: could not find implicit value for parameter t: TC.Aux[A[shapeless.HNil],shapeless.CNil]
}

Console

import shapeless._
{ import derive.eager_; the[TC    [A[HNil]      ]] }  // ✅: res0: TC[A[shapeless.HNil]]{type Out = shapeless.CNil} = null
{ import derive.eager_; the[TC.Aux[A[HNil], CNil]] }  // ✅: res1: TC[A[shapeless.HNil]]{type Out = shapeless.CNil} = null
{ import derive.lazy_ ; the[TC    [A[HNil]      ]] }  // ✅: res2: TC[A[shapeless.HNil]]{type Out = shapeless.CNil} = null
{ import derive.lazy_ ; the[TC    [A[HNil]      ]]: TC.Aux[A[HNil], CNil] }  // ✅: res3: TC.Aux[A[shapeless.HNil],shapeless.CNil] = null
{ import derive.lazy_ ; the[TC.Aux[A[HNil], CNil]] }  // 🚫
// <console>:15: error: could not find implicit value for parameter t: TC.Aux[A[shapeless.HNil],shapeless.CNil]
//        { import derive.lazy_; the[TC.Aux[A[HNil], CNil]] }  // 🚫
//                                  ^

Note that the internal Out = shapeless.CNil seems correctly present/inferred in the ✅ cases.

Discussion

• type A wraps an HList type L, and generally gets a custom Generic instance with Repr = L (only the HNil version is provided here, for simplicity)
• type-class TC is a simple type-function from an In to an Out; base-case HNil ⇒ CNil is provided.
• two additional derivations of TC are provided, one Lazy and one not, that derive a TC[T] in terms of its Generic repr.
  • they both allow deriving a TC[A[HNil]]
  • those instances seem to keep awareness of their internal Out = CNil in the console (as expected, based on returning a TC.Aux that specifies the Out type)
  • the Lazy version nevertheless fails to explicitly derive a TC.Aux[A[HNil], CNil] (and downstream derivations fail), which I think is a bug.

My guess is that the custom Generic for A might be interacting poorly with Lazy here.

---

Appendix: motivation / real use-case

Here is a longer write-up of the use-case that landed me in this situation; it's pretty far afield from the issue above. so feel free to ignore.

z-version-1.md

scalafiddle

Scala 2.12.8, Shapeless 2.3.3 (also tried from #797 branch)

Description

Derivations involving shapeless.Lazy don't correctly propagate type-member info in derived type-class instances.

Source

import shapeless.{ the, Lazy }

// shapeless.Lazy interferes with derivations of type-classes with type-members

trait CC  // stand-in for a case-class that we with to derive a typeclass instance `TC` for
trait L   // stand-in for a generic HList Repr of the case-class `CC`
trait O   // output-type for `L` (and ideally `CC`) from the typeclass `TC` below

// Imitation of shapeless.Generic.Aux
// - sole instance binds L as CC's "Repr"
// - theoretically easier to resolve as the "Repr" type-member is instead a type-param
trait G[T, Repr]; object G { implicit val g: G[CC, L] = null }

// Typeclass with one instance mapping `L` to `Out`
trait TC[In] { type Out }
object TC {
  type Aux[In, Out_] = TC[In] { type Out = Out_ }
  implicit val base: TC.Aux[L, O] = null
}

// A derivation of typeclass `TC` for the case-class `CC` in terms of its Repr `L` and an existing TC[L], which reuses the same `Out` type
// THe "eager" version works as expected, but the "lazy" version does not.
object derive {
  implicit def eager_[T](implicit g: G[T, L], tc:      TC[L]) : TC.Aux[T, tc      .Out] = null  // 👌🏻
  implicit def lazy_ [T](implicit g: G[T, L], tc: Lazy[TC[L]]): TC.Aux[T, tc.value.Out] = null  // 🐉
}

object test {
  {
    import derive.eager_
    the[TC    [CC   ]]  // ✅
    the[TC.Aux[CC, O]]  // ✅
  }

  {
    import derive.lazy_
    the[TC    [CC   ]]                   // ✅
    the[TC.Aux[CC, O]]                   // 🚫: Lazy breaks the derivation's awareness of the "output" type, for some reason

    // Further checks:
    the[TC    [CC     ]]: TC.Aux[CC, O]  // ✅
    the[TC    [CC     ]](lazy_)          // ✅
    the[TC.Aux[CC, O]](lazy_)            // 🚫: "error: polymorphic expression cannot be instantiated to expected type; "
    the[TC.Aux[CC, O]](lazy_[CC])        // ✅
  }
}

Console

import shapeless._
{ import derive.eager_; the[TC    [CC   ]]                }  // ✅: res0: TC.Aux[CC,TC.base.Out] = null
{ import derive.eager_; the[TC.Aux[CC, O]]                }  // ✅: res1: TC.Aux[CC,TC.base.Out] = null
{ import derive.lazy_ ; the[TC    [CC   ]]                }  // ✅: res2: TC[CC]{type Out = O} = null
{ import derive.lazy_ ; the[TC    [CC   ]]: TC.Aux[CC, O] }  // ✅: res3: TC.Aux[CC,O] = null
{ import derive.lazy_ ; the[TC.Aux[CC, O]]                }  // 🚫
// <console>:15: error: could not find implicit value for parameter t: TC.Aux[CC,O]
//   { import derive.lazy_ ; the[TC.Aux[CC, O]]           }  // 🚫
//                              ^

The difference between res2/res3 (Lazy summons that don't specify the output type, and therefore work) and res0/res1 ("eager" summons that omit and specify the output type, resp.) are intriguing. The latter seem to keep an awareness of the Aux alias and origin of the output type (TC.base.Out), whereas the former seem to have a subtly different representation.