Typeclass derivation for inner classes

[nhweston]

Compiler version

3.1.2

Minimized code

class Outer { class Inner }
trait Typeclass[A]
given [O <: Outer with Singleton](using v: ValueOf[O]): Typeclass[v.value.Inner] with { }
val outer = new Outer
val instance = implicitly[Typeclass[outer.Inner]]

Output

[error] 5 |val instance = implicitly[Typeclass[outer.Inner]]
[error]   |                                                 ^
[error]   |no implicit argument of type Typeclass[outer.Inner] was found for parameter e of method implicitly in object Predef
[error] one error found

Expectation

Compilation to succeed with the RHS of instance expanding to the result of applying the given on the third line.

[odersky]

Can you provide the exact term that should be inferred? I.e.

implicitly[Typeclass[outer.Inner]](<using <term goes here>)

[nhweston]

implicitly[Typeclass[outer.Inner]](using given_Typeclass_Inner(using new ValueOf(outer)))

[odersky]

Have you verified that this compiles without errors?

[nhweston]

If I expand the using clauses, I get this error:

[error] 5 |val instance = implicitly[Typeclass[outer.Inner]](using given_Typeclass_Inner(using new ValueOf(outer)))
[error]   |                                                        ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
[error]   |                          Found:    given_Typeclass_Inner[(outer : Outer)]
[error]   |                          Required: Typeclass[outer.Inner]

I suppose the problem is the compiler cannot unify outer.type with (new ValueOf(outer)).value.type?

[odersky]

If I try

val _: outer.type = new ValueOf(outer).value

it typechecks, so the compiler is able to unify the two.

I believe the problem is elsewhere. If I use a concrete name g for the given and print the with Xprint:typer, I see:

given class g[O >: Nothing <: Outer & Singleton](using v: ValueOf[O])
       extends
     Object(), Typeclass[g.this.v.value.Inner]

So the parent of the class depends on the class parameter value v. Scala cannot currently thread information about values through class parameters. Otherwise put, Scala has dependent methods, but not dependent classes. I think that's the root of the problem here. Dependent classes are currently a research subject. /cc @mbovel to have a look at the issue when we make advances on that subject.

[nhweston]

Interesting!

For context, I asked a question about typeclass derivation for inner classes on StackOverflow, and someone tried this approach and suggested I create an issue here.

[mbovel]

The question here is "how to define a given instance for an inner class in a different file?".

Definition in the same file

Note that the definition of the given being in a different file is what makes this question hard. Otherwise, we could just define the instance inside the outer class:

trait Typeclass[A]
class Outer {
  class Inner
  given Typeclass[Inner] with {}
}

val outer = new Outer
val instance = implicitly[Typeclass[outer.Inner]]

It's also possible to avoid the given instance being used automatically by wrapping it in an object:

trait Typeclass[A]
class Outer {
  class Inner
  object Givens {
    given Typeclass[Inner] with {}
  }
}

val outer = new Outer
import outer.Givens.given
val instance = implicitly[Typeclass[outer.Inner]]

The problem: Implicit search with paths

To be able to define the instance given instance in a different file, what we want is conceptually something like:

forall o: Outer, // pseudo code
  given Typeclass[o.Inner] with { }

As the OP noted, the closest we can get with valid Scala is:

given g(using o: Outer): Typeclass[o.Inner] with { }

But this is would require a given Outer, which is not what we want, hence the tentative to instead generate it with ValueOf.

However, even in the simplified case with a given Outer, implicit search would already fail to use g:

class Outer { class Inner }
trait Typeclass[A]
given g(using o: Outer): Typeclass[o.Inner] with { }
val outer = new Outer
given Outer = outer
val instance = implicitly[Typeclass[outer.Inner]]

// val instance:  <error no implicit values were found that match type Typeclass[outer.Inner]> =
//      implicitly[Typeclass[outer.Inner]](
//        /* missing */summon[Typeclass[outer.Inner]])

Is this the case that implicit search cannot reason about paths at all? How could it find an instance that has p.T where p is a parameter? If it can't, then we have a dead-end here already.

Note that replacing o.Inner with a free type parameter I enables g to be considered:

class Outer { class Inner }
trait Typeclass[A]
given g[I](using o: Outer): Typeclass[I] with { }
given outer: Outer = new Outer
val instance = implicitly[Typeclass[outer.Inner]]
// Compiles successfully

Which pushed me to try a handful of crazy tricks to constraint I later, such as:

class Outer { class Inner }
trait Typeclass[A]
given g[I, O <: Outer & Singleton](using v: ValueOf[O], w: v.value.Inner =:= I): Typeclass[I] with { }
given outer: Outer = new Outer
val instance = implicitly[Typeclass[outer.Inner]]
val instanceExplicit: Typeclass[outer.Inner] = g[outer.Inner, outer.type]

// no implicit argument of type Playground.Typeclass[Playground.outer.Inner] was found for parameter x of method summon in object Predef.
// I found:
//
//    Playground.g[Playground.outer.Inner, O](/* missing */summon[ValueOf[O]], ???)
//
// But no implicit values were found that match type ValueOf[O].

But this also doesn't work. It would be hard for the compiler to come up with the correct value for O (outer.type).

Could tracked help?

To answer @odersky's comment, given the essence of the problem, I don't think that the recent support for dependent classes through tracked could help here.

It particular, this doesn't work:

import language.experimental.modularity

class Outer { class Inner }
trait Typeclass[A]
given g[O <: Outer & Singleton](using tracked val v: ValueOf[O]): Typeclass[v.value.Inner] with { }
val outer = new Outer
val instance = implicitly[Typeclass[outer.Inner]]

Because, as described above, g is not even considered.

Workaround

A possible workaround is to manually hoist the inner class to a top-level class, and to define the given instance in terms of the hoisted class:

class InnerHoisted[O <: Outer](val outer: O) {}

class Outer {
  type Inner = InnerHoisted[this.type]
  def Inner: Inner = InnerHoisted(this)
  def show = "my outer"
}

trait Typeclass[A] {
  def show(a: A): String
}

given [O <: Outer]: Typeclass[InnerHoisted[O]] with {
  def show(a: InnerHoisted[O]): String = "outer is " + a.outer.show
}

val outer = new Outer
val instance = implicitly[Typeclass[outer.Inner]]