What's the difference between Aux pattern and dependent types in Scala3?

Question
1

I want to implement a type safe function that can flatten nested tuple in scala 3.0.2.
The following code is what I got:

trait Flatten[P]:
  type Q <: Tuple
  def flatten(p: P): Q
  
trait LowPriorityFlatten:
  type Aux[P, Q0] = Flatten[P] { type Q = Q0 }
  def make[P, Q0 <: Tuple](f: P => Q0): Aux[P, Q0] = new Flatten[P] {
    type Q = Q0
    def flatten(p: P): Q = f(p)
  }
  
  given [H, P <: Tuple, Q <: Tuple](using ft: Aux[P, Q]): Aux[H *: P, H *: Q] =
    make({ case h *: t => h *: ft.flatten(t)})
    
object Flatten extends LowPriorityFlatten:
  given Aux[EmptyTuple, EmptyTuple] = make(e => e)
  given [H <: Tuple, T <: Tuple, FH <: Tuple, FT <: Tuple](using fh: Aux[H, FH], ft: Aux[T, FT]): Aux[H *: T, Tuple.Concat[FH, FT]] = 
    make({ case h *: t => fh.flatten(h) ++ ft.flatten(t) })
  
  def f1[P <: Tuple, Q <: Tuple](p: P)(using ft: Aux[P, Q]): Q = ft.flatten(p)
  
  def f2[P <: Tuple](p: P)(using ft: Flatten[P]): ft.Q = ft.flatten(p)

And with some test:

scala> val r1 = Flatten.f1((1, (2, 3)))
val r1: Flatten.Aux[(Int, (Int, Int)), (Int, Int, Int)]#Q = (1,2,3)
scala> val r2 = Flatten.f2((1, (2, 3)))
val r2: (Int, Int, Int) = (1,2,3)

scala> val s1: (Int, Int, Int) = r1
val s1: (Int, Int, Int) = (1,2,3)
scala> val s2: (Int, Int, Int) = r2
val s2: (Int, Int, Int) = (1,2,3)

scala> val t1: (Int, Int, Int) = Flatten.f1((1, (2, 3)))
val t1: (Int, Int, Int) = (1,2,3)
scala> val t2: (Int, Int, Int) = Flatten.f2((1, (2, 3)))
-- Error:
1 |val t2: (Int, Int, Int) = Flatten.f2((1, (2, 3)))
  |                                                 ^
  |                                                 no implicit argument of type Flatten.Aux[(Int, (Int, Int)), Q] was found for parameter ft of method f2 in object Flatten
  |
  |                                                 where:    Q is a type variable with constraint <: (Int, Int, Int)
  |                                                 .
  |                                                 I found:
  |
  |                                                     Flatten.given_Aux_*:_*:[Int, ((Int, Int) *: EmptyTuple.type), Q](Flatten.given_Aux_*:_Concat[H, T, FH, FT])
  |
  |                                                 But given instance given_Aux_*:_Concat in object Flatten does not match type LowPriorityFlatten.this.Aux[((Int, Int) *: EmptyTuple.type), Q].

My questions are:

  1. Why the type of r1 (Flatten.Aux[(Int, (Int, Int)), (Int, Int, Int)]#Q) is more redundant than r2;
  2. Why t1 works as expected but t2 fails?

Thanks for any help

1 Like
3

This might be a REPL issue. It seems to work in Scastie

4

I am sorry that I had make a mistake in the question, and I have fixed the question now. Aux pattern vs dependent types

24 |val t1: (Int, Int, Int) = Flatten.f1((1, (2, 3)))
   |                                                 ^
   |no implicit argument of type Flatten.Aux[(Int, (Int, Int)), Q] was found for parameter ft of method f1 in object Flatten
   |
   |where:    Q is a type variable with constraint <: (Int, Int, Int)
   |.
   |I found:
   |
   |    Flatten.given_Aux_*:_*:[Int, ((Int, Int) *: EmptyTuple.type), Q](
   |      Flatten.given_Aux_*:_Concat[H, T, FH, FT]
   |    )
   |
   |But given instance given_Aux_*:_Concat in object Flatten does not match type Flatten.Aux[((Int, Int) *: EmptyTuple.type), Q].
5

Ah, okay, that makes more sense.

So the trouble here is that Q is a type parameter for f1, i.e. an “input”, and since Q is an abstract type member it is invariant, therefore Q must be definitively known in order for given search to succeed. But there is not enough information available to deduce or constrain Q enough. There is not an explicit argument that defines Q nor is it sufficient to have val t1: (Int, Int, Int) = Flatten.f1(...) and infer Q == (Int, Int, Int) because Q could also be any conforming subtype, like (Int, Int, Int) & String, and still satisfy t1 <: (Int, Int, Int).

More generally, the right hand side of an assignment expression only needs to resolve to a subtype of the left hand side of an assignment expression. So val t: T = expr: U only implies U <: T not that U == T.

In contrast, the only “input” type parameter to f2 is P, which is known from the explicit argument, and can be found in the given search, leaving ft.Q as an “output” type determined by the given lookup for P alone.

You can see the difference if you define something like given Aux[EmptyTuple, Tuple1[Int]] that partially overlaps with given Aux[EmptyTuple, EmptyTuple]. With f1 you can specify the type parameters like Flatten.f1[EmptyTuple, EmptyTuple] and Flatten.f1[EmptyTuple, Tuple1[Int]] to disambiguate. But it will always cause an ambiguous implicit error for f2 because you can only write Flatten.f2[EmptyTuple] but there are now two output types, EmptyTuple and (Int) for the same single EmptyTuple input type; you have to summon the given instance explicitly here.

6

It’s interesting that in 2.13 both variants compile: Scastie - An interactive playground for Scala.

One more case that differs Aux and path-dependent type in 3.0 is https://github.com/lampepfl/dotty/issues/8882

7

It was a great help ! Thank you very much for sharing this !