In scala, how to make type class working for Aux pattern? - Part 2

Question

This is a follow up question of: In scala, how to make type class working for Aux pattern?

Considering the following example:

  trait Base {

    type Out
    def v: Out
  }

  object Base {

    type Aux[T] = Base { type Out = T }
    type Lt[T] = Base { type Out <: T }

    class ForH() extends Base {

      final type Out = HNil

      override def v: Out = HNil
    }

    object ForH extends ForH
  }

  trait TypeClasses {

    class TypeClass[B]

    def summon[B](b: B)(implicit ev: TypeClass[B]): TypeClass[B] = ev
  }

  object T1 extends TypeClasses {

    implicit def t1: TypeClass[Base.Aux[HNil]] = new TypeClass[Base.Aux[HNil]]

    implicit def t2: TypeClass[Int] = new TypeClass[Int]
  }

  object T2 extends TypeClasses {

    implicit def t1[T <: Base.Aux[HNil]]: TypeClass[T] = new TypeClass[T]
  }

  object T3 extends TypeClasses {

    implicit def t1[
        H <: HList,
        T <: Base.Lt[H]
    ]: TypeClass[T] = new TypeClass[T] {

      type HH = H
    }
  }

  object T4 extends TypeClasses {

    implicit def t1[
        H <: HList,
        T <: Base.Aux[H]
    ]: TypeClass[T] = new TypeClass[T] {

      type HH = H
    }
  }

  it("No Aux") {

    val v = 2

    T1.summon(v) // works
  }

  it("Aux1") {

    val v = new Base.ForH()

    T1.summon(v) // oops
    T1.summon(Base.ForH) // oops

    val v2 = new Base.ForH(): Base.Aux[HNil]
    T1.summon(v2) // works!
  }

  it("Aux2") {

    val v = new Base.ForH()

    T2.summon(v) // works
    T2.summon(Base.ForH) // works

    val v2 = new Base.ForH(): Base.Aux[HNil]
    T2.summon(v2) // works
  }

  it("Aux3") {

    val v = new Base.ForH()

    T3.summon(v) // oops
    T3.summon(Base.ForH) // oops

    val v2 = new Base.ForH(): Base.Aux[HNil]
    T3.summon(v2) // oops
  }

  it("Aux4") {

    val v = new Base.ForH()

    T4.summon(v) // oops
    T4.summon(Base.ForH) // oops

    val v2 = new Base.ForH(): Base.Aux[HNil]
    T4.summon(v2) // oops
  }

all implementations of TypeClasses contains an implicit scope of their underlying TypeClass, among them, the T1 is the most simple and specific definition for ForH, unfortunately it doesn't work. An improvement was proposed by @Dan Simon (in T2), it uses a type parameter to allow the spark compiler to discover ForH <:< Base.Aux[HNil]

Now imagine that I'd like to extend @Dan Simon's solution, such that the type class applies to all classes like ForH for different kinds of HList (a super trait of HNil). 2 natural extensions are in T3 & T4 respectively.

Unfortunately none of them works. The T4 can be explained by the fact that ForH <:< Aux[HList] is invalid, but T3 can't use this excuse. In addition, there is no way to improve it to compile successfully.

Why the type class summoning algorithm failed this case? And what should be done to make the type class pattern actually works?

FYI both T3 and T4 seem to work fine in Scala 3 (3.0.0-M3). So maybe this one really is just a bug/limitation with Scala 2. — Dan Simon
Wow ... I thought T3 is not supposed to work. What is happening there :-| — tribbloid
If H isn't used in the implicit parameters or in the return type of your implicits, then the compiler has nothing to go on to infer H. — Jasper-M
@Jasper-M (sigh) you are probably right, I browse over the source code of the entire shapeless and so far only found Aux in implicit parameters — tribbloid
@DanSimon, I'll try elaborate: ForH <:< Aux[HNil], and Aux[_] is not covariant, so this statement shouldn't even work in dotty, unless they change the rule of variance definition in dotty — tribbloid

Dmytro Mitin Dmytro Mitin · Accepted Answer · 2021-02-04T19:34:57

Again, T1.summon(v) doesn't compile because T1.t1 is not a candidate, manually resolved T1.summon(v)(T1.t1) doesn't compile.

For T3 and T4 T3.t1[HNil, Base.ForH], T4.t1[HNil, Base.ForH] would be a candidate

T3.summon(v)(T3.t1[HNil, Base.ForH]) // compiles
T4.summon(v)(T4.t1[HNil, Base.ForH]) // compiles

but the trouble is that H is inferred first and it's inferred to be Nothing but t1[Nothing, Base.ForH] doesn't satisfy type bounds.

So the trouble is not with implicit resolution algorithm, it's ok, the trouble is with type inference (and all we know that it's pretty weak in Scala).

You can prevent H to be inferred too fast as Nothing if you modify T3.t1, T4.t1

object T3 extends TypeClasses {    
  implicit def t1[
    H <: HList,
    T <: Base/*.Lt[H]*/
  ](implicit ev: T <:< Base.Lt[H]): TypeClass[T] = new TypeClass[T] {
    type HH = H
  }
}

object T4 extends TypeClasses { 
  implicit def t1[
    H <: HList,
    T <: Base/*.Aux[H]*/
  ](implicit ev: T <:< Base.Aux[H]): TypeClass[T] = new TypeClass[T] {
    type HH = H
  }
}

T3.summon(v) // compiles
T4.summon(v) // compiles

In scala, how to make type class working for Aux pattern? - Part 2

1 Answers