How to help the Scala 3 compiler infer a path-dependent-type?

Question

Suppose that, whenever type A can represent a less-than-perfectly-precise measurement of a physical value, I'll have an instance of Imprecise[A].

trait Imprecise[A]:
  type Precision
  val ord: Ordering[Precision]
  def precision(a: A): Precision

For example, this Bounds type has a given instance in its companion object:

case class Bounds[N: Numeric](min: N, max: N):
  if summon[Ordering[N]].compare(min, max) > 1 then
    throw new IllegalArgumentException

object Bounds:
  import scala.math.Numeric.Implicits.infixNumericOps
  import scala.math.Ordering.Implicits.infixOrderingOps
  given [N: Numeric]: Imprecise[Bounds[N]] with
    type Precision = N
    val ord = summon[Ordering[N]]
    def precision(rng: Bounds[N]) = rng.max - rng.min

Now my program can start dealing with the physical features that need to be observed:

trait Feature[A:  Imprecise]:
  type Observation = A
  val imprecise = summon[Imprecise[A]]
  type Precision = imprecise.Precision

  def within(bound: Precision) = new RequiredFeature(this, bound)

class RequiredFeature(val feature: Feature[_], val min_precision: feature.Precision)


case class Temperature(chamber_id: Int) extends Feature[Bounds[Double]]
case class Pressure(chamber_id: Int) extends Feature[Bounds[Float]]

But when, at last, I try to make a required feature:

val rf = Temperature(3).within(7.0)

the compiler complains

Found:    (7.0d : Double)
Required: ?1.Precision

where:    ?1 is an unknown value of type exp.Temperature

val rf = Temperature(3).within(7.0)

The code written so far can be made to compile if I forego any path-dependent types and pass the precision around everywhere as a regular generic type parameter. But what if I don't want to do that? Is there some strategy like the Aux pattern that will help the compiler see that this is a valid call to within?

Answer 1

This question is similar to Cannot prove equivalence with a path dependent type

The thing is not in implicits, the thing is in path-dependent types. The simplest example is

trait A:
  type T

val a0 = new A:
  type T = Int

summon[a0.T =:= Int]

class B(val a: A) // a has type A, not A { type T = ... }

val b = B(a0)

// summon[b.a.T =:= Int] // doesn't compile

To make this compile we could use singleton types class B(val a: a0.type) or add a type parameter class B[_T](val a: A { type T = _T }).

trait Feature[A: Imprecise] is desugared into trait Feature[A](using ev: Imprecise[A]) and here you're loosing type refinement, upcasting Imprecise[A] { type Precision = ... } to just Imprecise[A]. Difference in behavior of path-dependent types in variable vs. method parameter is discussed in Same type ascription loses type member information on variable declaration but not on method parameter declaration and using ev: Imprecise[A] in trait Feature[A](using ev: Imprecise[A]) declares a variable.

So you should restore type refinement of Imprecise and add a type parameter to Feature

trait Imprecise[A]:
  type Precision
  val ord: Ordering[Precision]
  def precision(a: A): Precision

object Imprecise:
  type Aux[A, P] = Imprecise[A] with
    type Precision = P

case class Bounds[N: Numeric](min: N, max: N):
  if summon[Ordering[N]].compare(min, max) > 0 then
    throw new IllegalArgumentException

object Bounds:
  import Numeric.Implicits._
  given [N: Numeric]: Imprecise[Bounds[N]] with
    type Precision = N
    val ord = summon[Ordering[N]]
    def precision(rng: Bounds[N]) = rng.max - rng.min

trait Feature[A, P](using Imprecise.Aux[A, P]):
  type Observation = A
  val imprecise = summon[Imprecise[A]]
  type Precision = imprecise.Precision

  def within(bound: Precision) = new RequiredFeature(this, bound)

class RequiredFeature(val feature: Feature[_,_], val min_precision: feature.Precision)

case class Temperature(chamber_id: Int) extends Feature[Bounds[Double], Double]
case class Pressure(chamber_id: Int) extends Feature[Bounds[Float], Float]

val rf = Temperature(3).within(7.0)

or add a type member to Feature

trait Imprecise[A]:
  type Precision
  val ord: Ordering[Precision]
  def precision(a: A): Precision

object Imprecise:
  type Aux[A, P] = Imprecise[A] with
    type Precision = P

case class Bounds[N: Numeric](min: N, max: N):
  if summon[Ordering[N]].compare(min, max) > 0 then
    throw new IllegalArgumentException

object Bounds:
  import Numeric.Implicits._
  given [N: Numeric]: Imprecise[Bounds[N]] with
    type Precision = N
    val ord = summon[Ordering[N]]
    def precision(rng: Bounds[N]) = rng.max - rng.min

trait Feature[A]:
  type P
  val ev: Imprecise.Aux[A, P]
  given Imprecise.Aux[A, P] = ev

  type Observation = A
  val imprecise = summon[Imprecise[A]] // ev
  type Precision = imprecise.Precision // P

  def within(bound: Precision) = new RequiredFeature(this, bound)

class RequiredFeature(val feature: Feature[_], val min_precision: feature.Precision)

case class Temperature[_P](chamber_id: Int)(using _ev: Imprecise.Aux[Bounds[Double], _P]) extends Feature[Bounds[Double]]:
  type P = _P
  val ev = _ev
case class Pressure[_P](chamber_id: Int)(using _ev: Imprecise.Aux[Bounds[Float], _P]) extends Feature[Bounds[Float]]:
  type P = _P
  val ev = _ev

val rf = Temperature(3).within(7.0)

Answer 2

Adding to @DmytroMitin excellent answer, here is a step by step analysis for those with slow minds like mine :)

The explanation is based on this example code:

    class Outer {
        class Inner
        def doSomething(a: Inner): Unit = ()
    }

    val outerRef = new Outer

The first thing we have to note is that the type of the reference outerRef is not Outer but outerRef.type, which is assignable to Outer but not the opposite. That happens even if the type of outerRef were specified explicitly to be Outer (val outerRef: Outer = new Outer).

    summon[outerRef.type <:< Outer]

The second thing we have to note is that a copy of a reference does not have the same type than the original reference.

    val copyOfOuterRef = outerRef

Here the type of the reference copyOfOuterRef is not outerRef.type but copyOfOuterRef.type, which is assignable to Outer but not to outerRef.type.

    summon[copyOfOuterRef.type <:< Outer] // compiles
    
    summon[copyOfOuterRef.type =:= outerRef.type] // does not compile
    summon[copyOfOuterRef.type <:< outerRef.type] // does not compile
    summon[outerRef.type <:< copyOfOuterRef.type] // does not compile

What does all this have to do with path-dependent-types?

The path-dependent-type assignability rules is based on the singleton type of the references involved in the path.

The following line defines a reference whose type is assignable to the path-dependent-type outerRef.Inner.

    val innerRef = new outerRef.Inner

Therefore, it is suitable to be the argument of the outerRef.doSomething method.

    outerRef.doSomething(innerRef) // compiles
    summon[innerRef.type <:< outerRef.Inner] // compiles

But not suitable to be the argument of the copyOfOuterRef.doSomething method.

    copyOfOuterRef.doSomething(innerRef) // does not compile
    summon[innerRef.type <:< copyOfOuterRef.Inner]  // does not compile

because the singleton type of the references involved in the paths is not the same.

summon[copyOfOuterRef.type =:= outerRef.type] // does not compile

To solve that, we have to make the copy of the reference have the same singleton-type than the original reference.

    val copyOfOuterRefWithSameType: outerRef.type = outerRef

Now the singleton type of the references that conform both paths, outerRef.X and copyOfOuterRefWithSameType.X, are the same. Therefore

    copyOfOuterRefWithSameType.doSomething(innerRef) // compiles
    summon[outerRef.type =:= copyOfOuterRefWithSameType.type] // compiles
    summon[outerRef.Inner =:= copyOfOuterRefWithSameType.Inner] // compiles

A more realistic case

Usually, we can't change the type of the second reference (the copy of the first) because the first reference is out of the scope. For example, when the second reference (the copy) is a member a previously defined class.

    class User(val outer: Outer) // defined in some place where the `outerRef` reference is not accesible.

    val outerRef = new Outer
    val user = new User(outerRef)

Here both user.outer and outerRef reference the same instance of Outer but because the path-dependent-type is based on the singleton type of the references involved, the assignability fails.

    val outerRef = new Outer
    val innerRef = new outerRef.Inner

    user.outer.doSomething(innerRef) // does not compile
    summon[innerRef.type <:< user.outer.Inner] // does not compile

because

    summon[user.outer.Inner =:= outerRef.Inner] // does not compile

To solve that we have to make the singleton type of the outer member be equivalent to the type of outerRef, which is the singleton type outerRef.type. We can achieve that parameterizing the member type.

    class UserBis[O <: Outer](val outer: O)

    val outerRef = new Outer
    val innerRef = new outerRef.Inner
    val userBis = new UserBis[outerRef.type](outerRef)
    
    userBis.outer.doSomething(innerRef) // compiles
    summon[userBis.outer.type =:= outerRef.type] // compiles
    summon[userBis.outer.Inner =:= outerRef.Inner] // compiles