Unintuitive meaning of some recursive type aliases

[LPTK]

So currently recursive type aliases are not supposed to be legal in Scala.

There are various workarounds. For examples I’ve seen people use match types to do it:

type NestedSet1[A] = A match
  case Nothing => Nothing // used to turn of the cycle detector...
  case String => Set[NestedSet1[A]]

type S = NestedSet1[String]

// expected:
val s0: S = Set()       ; s0
val s1: S = Set(Set())  ; s1
val s2: S = Set(s0, s1) ; s2

// unexpected:
// val sAny: S = (Set("hello"): Set[Any]) ; sAny // now an error

val unsound: S = s1.head // works

Scastie - An interactive playground for Scala.

One can also probably tie such indirect recursive knots through intersection types/refinements.

@Sporarum

With a bit more digging, I found out this compiles: (but not in scala 2)

type _NestedSet2[_] = Set[_NestedSet2[?]]
type NestedSet2 = _NestedSet2[Nothing]

This looks like a bug. I don’t see why Scala 3 accepts the first recursive type alias definition. And it also accepts a type alias with wildcard type argument, which it shouldn’t.

@Sporarum

This however seems to create Set[Any] instead of the wanted type !
See this scastie

This looks like a couple of other bugs!

1. I think it shouldn’t let you upcast a Set[Any] into an S;
2. It should probably let you type s1.head as an S. In any case there should be no Set[Any] in there. Looks like an avoidance/wildcard bug (cc @smarter).