How to implement a recursive Scala 3 function that returns a recursive match type?

Question

I fail to implement a function that returns a recursive match type. As an example, I took the tuple Append type from the std lib and tried to implement a simple append function.

// Tuple append match type, copied from std lib
type Append[X <: Tuple, Y] <: Tuple = X match {
  case EmptyTuple => Y *: EmptyTuple
  case x *: xs => x *: Append[xs, Y]
}

// Types work just fine
val x: Append[(String, Int), Long] = ("", 1, 2L)

// My simple function implementation that does not compile
def append[X <: Tuple, Y](x: X, y: Y): Append[X, Y] = x match
  case _: EmptyTuple => y *: EmptyTuple
  case x *: xs => x *: append(xs, y)

[E007] Type Mismatch Error:
  case _: EmptyTuple => y *: EmptyTuple
                        ^^^^^^^^^^^^^^^
             Found:    Y *: EmptyTuple.type
             Required: Append[X, Y]

             where:    X is a type in method append with bounds <: Tuple


             Note: a match type could not be fully reduced:

               trying to reduce  Append[X, Y]
               failed since selector  X
               does not match  case EmptyTuple => Y *: EmptyTuple
               and cannot be shown to be disjoint from it either.
               Therefore, reduction cannot advance to the remaining case

                 case x *: xs => x *: Append[xs, Y]

 longer explanation available when compiling with `-explain`
[E007] Type Mismatch Error:
  case x *: xs => x *: append(xs, y)
                  ^^^^^^^^^^^^^^^^^^
             Found:    Any *: Append[Tuple, Y]
             Required: Append[X, Y]

             where:    X is a type in method append with bounds <: Tuple


             Note: a match type could not be fully reduced:

               trying to reduce  Append[Tuple, Y]
               failed since selector  Tuple
               does not match  case EmptyTuple => Y *: EmptyTuple
               and cannot be shown to be disjoint from it either.
               Therefore, reduction cannot advance to the remaining case

                 case x *: xs => x *: Append[xs, Y]

 longer explanation available when compiling with `-explain`

Scastie

Answer 1

The compiler is very fussy when it comes to returning match types. Your second case needs a small modification to get it to work without the cast (Scastie):

def append[X <: Tuple, Y](x: X, y: Y): Append[X, Y] = x.match {
  case _: EmptyTuple => y *: EmptyTuple
  case (x *: xs): (x *: xs) => x *: append(xs, y)
}

Without the : (x *: xs), the compiler doesn't understand that your function's second case corresponds with the second case of the match type. Perhaps in the future it'll be smarter.

Answer 2

A cast in the append function did the trick. I couldn't manage to inline it, but this is sufficient for now.

// Tuple append match type, copied from std lib
type Append[X <: Tuple, Y] <: Tuple = X match {
  case EmptyTuple => Y *: EmptyTuple
  case x *: xs => x *: Append[xs, Y]
}

// Types work just fine
val x: Append[(String, Int), Long] = ("", 1, 2L)

// Function now compiles and succeeds at runtime
def append[X <: Tuple, Y](x: X, y: Y): Append[X, Y] = x.match {
  case _: EmptyTuple => y *: EmptyTuple
  case x *: xs => x *: append(xs, y)
}.asInstanceOf[Append[X, Y]]

append((1, 2), 3)

Scastie