Funny observation about (recursive) structural types in Scala

Question

I needed some recursive structural type in some piece of code using with traits and the structural type as type parameter constraint. It worked fine, but later I learned Scala does not support recursive structural types.

So can someone explain me why this works fine:

scala> trait Test[M[A] <: { def map[B](f: A => B) : M[B] } ] {}
defined trait Test

and this not:

scala> def test[M[A] <: { def map[B](f: A => B) : M[B] } ] = null
<console>:5: error: illegal cyclic reference involving type M
       def test[M[A] <: { def map[B](f: A => B) : M[B] } ] = null

Tychonn

Answer 1

I think this is a glitch in the compiler. The following code exhibits the same behavior as your initial code:

trait Test[M[A] <: { def map: M[A] } ] {}
def test[M[A] <: { def map: M[A] } ] = null

It results in a compile time error: 'illegal cyclic reference'.

And the following code does not (i.e. it compiles fine):

type S[M] = { def map: M }

trait Test[M[A] <: S[M[A]] ] {}
def test[M[A] <: S[M[A]] ] = null

The only difference is that structural typing is applied via a type alias S here.

Scheldt

actually I like the solution using type aliases and that it even works for function definitions. But your first example behaves exactly like mine, saying the Test-trait compiles fine. But if it works using type aliases, it definitely should work without using them too?!? – Tychonn

Yes I think there is some inconsistency here: it should either work with type aliases and without or it shouldn't work at all. That's why I think this is a glitch in the compiler. – Scheldt

Do you have a bug tracker number? – Ossian

Answer 2

The first code snippet also throws error in Scala 2.7.7final:

scala> trait Test[M[A] <: { def map[B](f: A => B) : M[B] } ] {}
<console>:4: error: illegal cyclic reference involving type M
       trait Test[M[A] <: { def map[B](f: A => B) : M[B] } ] {}
                                                    ^

Which version of Scala do you use?

Rewire