Missing type upper bound for `Tuple.Fold`

[nicolasstucki]

Compiler version

3.1.0

Code

The current definition for Tuple.Fold is

  type Fold[Tup <: Tuple, Z, F[_, _]] = ...

It should know that the result will be a subtype of Z or F. It looks like we should be able to add this bound but it does not work.

  type Fold[Tup <: Tuple, Z, F[_, _]] <: (Z | F[_, _]) = ...

Failing example

type Reverse[X <: Tuple] <: Tuple = Fold[X, EmptyTuple, [A <: Tuple, Y] =>> Y *: A]
// [error]                        ^
// [error]                        cannot combine bound and alias

Expectation

Should be able to add these kinds of bounds

[Decel]

We can do a small workaround here to avoid cannot combine bound and alias error, and use match types:

type Reverse[X <: Tuple] <: Tuple = X match
  case _ => Fold[X, EmptyTuple, [A <: Tuple, Y] =>> Y *: A]
  
  
-- [E007] Type Mismatch Error----------------------------------------------
2 |  case _ => Tuple.Fold[X, EmptyTuple, [A <: Tuple, Y] =>> Y *: A]
  |            ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  |Found:    Tuple.Fold[X, EmptyTuple, [A <: Tuple, Y] =>> Y *: A]
  |Required: Tuple

The problem is, Tuple.Fold is subtype of Any, so we can't really use it for Reverse, since it should guarantee subtype of Tuple.

I think it's a bit of a case where we really can't ever infer from [A <: Tuple, Y] =>> Y *: A that the result of Fold[X, EmptyTuple, [A <: Tuple, Y] =>> Y *: A] will be guaranteed to be a subtype of Tuple. It simply boils down to unsoundness.

So if we want something like Tuple.Reverse we could try

type Reverse[X <: Tuple] <: Tuple = X match
  case EmptyTuple => EmptyTuple
  case h *: t =>  Tuple.Append[Reverse[t], h]

In that case, everything works great.

The issue is, that we cannot write something akin to

type A <: List[Any] = List[Int]

Because the type of alias may depend on other types, which may lead to unsoundness.

[sjrd]

Combining @nicolasstucki's proposed signature

type Fold[Tup <: Tuple, Z, F[_, _]] <: (Z | F[_, _]) = ...

with @Decel's trick for Reverse

type Reverse[X <: Tuple] <: Tuple = X match
  case _ => Fold[X, EmptyTuple, [A <: Tuple, Y] =>> Y *: A]

should make it work. In fact, X is not needed there and could be instead

-type Reverse[X <: Tuple] <: Tuple = X match
+type Reverse[X <: Tuple] <: Tuple = Any match
   case _ => Fold[X, EmptyTuple, [A <: Tuple, Y] =>> Y *: A]

Alternatively, with the updated signature for Fold, Reverse could also be defined without a bound. As a type alias, it will transitively get the bound from Fold automatically:

-type Reverse[X <: Tuple] <: Tuple = Fold[X, EmptyTuple, [A <: Tuple, Y] =>> Y *: A]
+type Reverse[X <: Tuple] = Fold[X, EmptyTuple, [A <: Tuple, Y] =>> Y *: A]

[dwijnand]

I found that F[_, _] isn't allowed, but having a named upper bound works:

type Fold[Tup <: Tuple, R, Z <: R, F[_, _ <: Tuple] <: R] <: R = Tup match
  case EmptyTuple => Z
  case h *: t => F[h, Fold[t, R, Z, F]]

type Reverse[X <: Tuple] = Fold[X, Tuple, EmptyTuple, [H, T <: Tuple] =>> H *: T]

[sjrd]

Ah, unfortunately that would not be a backward TASTy compatible change. :(

[dwijnand]

Neither would adding any bound to the match type though - I would think?!

[sjrd]

It already has a bound, which is <: Any. You can make that bound strictly smaller, I think, without breaking TASTy compatibility. At least I don't see how it could pose a problem.

Edit: it's similar to making the result type of final term function a strict subtype of what it was before.

[dwijnand]

I think even a subtype isn't compatible, if you consider the use of that result type in a method like foldLeft. But is that only source incompatibility?

[sjrd]

That's only source incompatibility, yes.