Scala: working around the "illegal cyclic reference"

Question

I'm trying to implement a HashMap-based tree that'd support O(1) subtree lookup for a given root key. To that goal, I'm trying to do the following:

scala> type Q = HashMap[Char, Q]
<console>:6: error: illegal cyclic reference involving type Q
       type Q = HashMap[Char, Q]
                          ^

So the question is, is there a way for me to do something of the sort without resorting to the ugly HashMap[Char, Any] with subsequent casting of values to HashMap[Char, Any]?

Now, I also see that I can use something like the following to avoid the cyclic-reference error, and it might even be cleaner -- but it'd be nice to find out how to correctly do it the first way, just for the educational value.

import collections.mutable.HashMap

class LTree {
  val children = new HashMap[Char, LTree]
}

Thanks a bunch.

Answer 1

I probably don't "get" the question, but what about

class L {
  type Q = java.util.HashMap[Char, this.type]
}

or

class Q extends java.util.HashMap[Char, Q]

Answer 2

For types you can't extend, such as Either, you can also use a trivial wrapper:

class MyEither(get: Either[String, MyEither])

or, a recursive tree with Either (something that led me to this thread):

// represents (validation) errors for a tree structure of nested dictionaries
type FieldName = String
type Error = String

type Errors = List[(FieldName, FieldError)]
case class FieldError(val get: Either[Error, Errors])

which is the type-legal version of this pseudo-code:

type Error = String
type Errors = List[(FieldName, Either[Error, Errors])]

Then, all your Left(...) and Right(...) calls would become FieldError(Left(...)) and FieldError(Right(...)) respectively, such that e.g. FieldError(Right(x)).get == Right(x).