Indirect recursive generic type definitions in scala

Question

Direct type recursion just works:

trait TT[T<:TT[T]]

But I can made indirect one with naive approach

trait UU[V <: VV[UU[V]]]
trait VV[U <: UU[VV[U]]]

give me error:

CyclicTraits.scala:23: error: type arguments [UU[V]] do not conform to
    trait VV's type parameter bounds [U <: UU[VV[U]]]
trait UU[V <: VV[UU[V]]]
              ^
CyclicTraits.scala:25: error: type arguments [VV[U]] do not conform to
    trait UU's type parameter bounds [V <: VV[UU[V]]]
trait VV[U <: UU[VV[U]]]
              ^

How should indirect type parameter recursion be expressed properly?

Answer 1

The problem here isn't the recursion—it is actually a matter of the type parameters not conforming to the bounds, as the error message says. Your example works perfectly if you make the parameters covariant:

trait UU[+V <: VV[UU[V]]]
trait VV[+U <: UU[VV[U]]]

In your version (without the covariance), the fact that V is a subtype of VV[UU[V]] tells us nothing about whether or not UU[V] is a subtype of UU[VV[UU[V]]], so we get the conformance error. If the type parameters are covariant, we know that V being a subtype of VV[UU[V]] entails that UU[V] is a subtype of UU[VV[UU[V]]], and everything's fine.