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

Question

Here is a simple example:

  trait Base {

    type Out
    def v: Out
  }

  object Base {

    type Aux[T] = Base { type Out = T }

    class ForH() extends Base {

      type Out = HNil

      override def v: Out = HNil
    }

    object ForH extends ForH
  }

  class TypeClass[B]

  trait TypeClassLevel1 {

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

  object TypeClass extends TypeClassLevel1 {

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

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

  it("No Aux") {

    val v = 2

    TypeClass.summon(v) // works
  }


  it("Aux") {

    val v = new Base.ForH()

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

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

The object Base/ForH clearly has a stable path, this eliminate the possibility of the compiler not being able to resolve type ForH.Out.

What bothers me is not how incapable the compiler is to figure out the fact that ForH <:< Aux[HNil], but how easy it is to patch it up, just by a simple type upcast (last 2 lines). IMHO both features (type lambda & type classes) are important aspect of functional programming, why they can't work together at the same time?

If you are familiar with the compiler design I'll have an extra question: what does it take to improve the type class search algorithm to make it happen? Thanks a lot for your opinion.

UPDATE 1: a specific fix has been proposed but I have another problem trying to generalise it, please see In scala, how to make type class working for Aux pattern? - Part 2 for detail

Answer 1

So the compiler is able to infer ForH <:< Aux[HNil], but (tbh I don't know exactly why) when resolving an implicit when the return type uses a type lambda, it gets confused if you don't use a type bound.

Anyway that's probably not a great explanation, but at least I can make your code compile. Just change t1 to:

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

this works for me in scastie using Scala 2.13.4.

Answer 2

What bothers me is not how incapable the compiler is to figure out the fact that ForH <:< Aux[HNil]

Surely the compiler does see that Base.ForH <:< Base.Aux[HNil]. You can check that

implicitly[Base.ForH <:< Base.Aux[HNil]]

compiles.

IMHO both features (type lambda & type classes) are important aspect of functional programming, why they can't work together at the same time?

Why are you talking about type lambdas? I can't see type lambdas in your question.

By the way, type lambdas is not a part of Scala 2 and ({ type λ[X] = ...F[X]... })#λ for a type lambda is more or less a hack. Actual type lambdas are added to Scala 3.

val v = new Base.ForH() has type Base.ForH (not Base.Aux[HNil] without upcasting via type ascription val v = new Base.ForH(): Base.Aux[HNil] or manual type specification val v: Base.Aux[HNil] = new Base.ForH()). TypeClass.summon(v) shouldn't compile since there is no implicit TypeClass[Base.ForH]. What implicit would you consider as a candidate? TypeClass.t1? But it's not a candidate, you can check that explicitly resolved

TypeClass.summon(v)(TypeClass.t1)

can't compile.

what does it take to improve the type class search algorithm to make it happen?

Implicit search algorithm shouldn't be improved in this specific place. It works properly, as intended.

You can make the type class contravariant

class TypeClass[-B]

Then TypeClass.t1 will be a candidate for TypeClass[Base.ForH] and TypeClass.summon(v) will compile.

In scala 2.13, how to use implicitly[value singleton type]?