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

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

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

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].``````

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.

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

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