Scala recursive type alias error

Question

I have a couple of functions whose only parameter requirement is that it has some sort of collection that is also growable (i.e. it could be a Queue, List, PriorityQueue, etc.), so I attempted to create the following type alias:

type Frontier = Growable[Node] with TraversableLike[Node, Frontier]

to use with function definitions like so:

def apply(frontier: Frontier) = ???

but the type alias returns the error "Illegal cyclic reference involving type Frontier." Is there any way to get around the illegal cyclic reference to use the type alias or something similar to it?

One solution is to use the following:

def apply[F <: Growable[Node] with TraversableLike[Node, F]](f: F) = ???

but this seems to add unnecessary verbosity when the function definition is doing seemingly the exact same thing as the type alias. The type is also used in other places, so a type alias would greatly increase readability.

Answer 1

From section 4.3 of the spec:

The scope rules for definitions (§4) and type parameters (§4.6) make it possible that a type name appears in its own bound or in its right-hand side. However, it is a static error if a type alias refers recursively to the defined type constructor itself.

So no, there's no way to do this directly, but you can accomplish much the same thing with a type parameter on the type alias:

type Frontier[F <: Frontier[F]] = Growable[Int] with TraversableLike[Int, F]

Now you just write your apply like this:

def apply[F < Frontier[F]](frontier: F) = ???

Still a more little verbose than your hypothetical first version, but shorter than writing the whole thing out.

You could also just use the wildcard shorthand for an existential type:

type Frontier = Growable[Node] with TraversableLike[Node, _]

Now your first apply will work as it is. You're just saying that there has to be some type that fits that slot, but you don't care what it is.

In this case specifically, though, is there a reason you're not using Traversable[Node] instead? It would accomplish practically the same thing, and isn't parameterized on its representation type.