Dotty: Illegal cyclic type reference or not

[Jasper-M]

This type alias fails to compile with Illegal cyclic type reference.

type Rec[F[_], A] = A | F[Rec[F, A]]

So does this equivalent match type.

type Rec[F[_], A] = A match {
  case _ => A | F[Rec[F, A]]
}

However this still equivalent match type compiles successfully.

type Rec[F[_], A] = A match {
  case Int => Int | F[Rec[F, Int]]
  case _ => A | F[Rec[F, A]]
}

Not only does it compile but it also seems to be perfectly usable.

val ints: Rec[List, Int] = List(1, List(List(2,List(3))))
val strings: Rec[List, String] = List(List("a", "b", List("c")), "d")

[ashwinbhaskar]

type Rec[F[_], A] = A match {
case _ => A | F[Rec[F, A]]
}

is matched as a type alias (here)

type Rec[F[_], A] = A match {
case Int => Int | F[Rec[F, Int]]
case _ => A | F[Rec[F, A]]
}

is matched as a match alias (here)

Should both of these be match aliases?

[LPTK]

I think the first form ought to work. Scala already supports a form of F-bounded polymorphism of similar expressiveness, which is probably undecidable, and the compiler already has a mechanism for bailing out of infinite recursions on the type level as a result. Moreover, match types make it clear we are not so concerned about the possibility of triggering such infinite recursions. So I don't see a reason to restrict the definition of recursive type aliases. But I may be missing something.

[odersky]

I think it should be a cyclic reference error. F-bounds are what the name implies: bounds, not aliases.

[LPTK]

But aren't type aliases morally equivalent to an abstract type with equal bounds?

I notice F-bounds does not work with lower bounds, though:

scala> def f[A <: Option[B], B <: Option[A]] = ()
def f[A <: Option[B], B <: Option[A]] => Unit

scala> def f[A >: Option[B], B >: Option[A]] = ()                           
1 |def f[A >: Option[B], B >: Option[A]] = ()
  |      ^
  |illegal cyclic type reference: lower bound Option[B] of type A refers back to the type itself

I wonder if this is a simple implementation restriction, or if there is a fundamental reason for it.

But Regardless, match types already effectively allow us to define cyclic type aliases, so I don't see why more direct cyclic type definitions should be disallowed.

[OlivierBlanvillain]

I don't think rejecting the match type version of the example would be the solution here since we want to support recursive and non-terminating match types anyways. The question is whether or not we want to relax type aliases to allow this kind of recursion.

In the current state of the compiler, match types and type aliases are represented very differently. Although they can look very similar (like in this example), the compiler is (or should be) extra careful when reducing match types (knowing that they could diverge), but is rather careless when it comes to dealiasing (since no recursion is assumed).

I don't think there is an easy fix here. Representing all type aliases as match types is probably a no go as it would probably be a massive performance regression...

[LPTK]

I don't think there is an easy fix here.

Isn't the easy fix to internally desugar recursive type aliases into match types, instead of reporting an error? It's a trick users will end up manually applying anyway, when faced with the restriction.

In other words, it seems to me that the current restriction is not semantically meaningful, and just forces more needless verbosity on users.

[odersky]

If someone has a concrete fix to propose and wants to work on this, please re-open.