Scala: working around the "illegal cyclic reference"

7
votes

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.

2
scalatreetypes
Can you clarify what sort of structure you want to define? A tree whose arcs are labeled with a Char and whose nodes bear no information at all at all? If so, your LTree is about as minimal as it gets, though as written you can only create empty trees since children is immutable as is the HashMap itself and the constructor takes no arguments. - Randall Schulz
Thanks for the comment Randall. I've just tweaked the above listing to indicate (as it is in my source code) that the HashMap used is mutable. The use case is indeed a directed graph with char-labeled edges and nodes not bearing any information. This is in fact a rudimentary DFA with leaf-nodes implicitly considered final states. At any rate, the above is not that relevant to the question of scala syntax -- I guess the small snippet that I've given is one workaround, I was just curious if there's a way to do it even more succinctly, as suggested in the first listing. - Paul Milovanov
Practically speaking though, of course, the second way with LTree is more appropriate as I can toss in fields and member functions inside it for various tree ops. - Paul Milovanov
One thing we have to concede is that Scala, while generally much more succinct than Java, is still usually beat by Haskell. I should also have pointed out that Scala's type declarations only name aliases for already existing types, they don't invent new ones. In this, Scala's type is like Haskell's type, not its newtype. - Randall Schulz
There's an interesting discussion on neopythonic.blogspot.com/2008/11/scala.html about virtues and deficiencies of Scala. And among some comments that I agree with there's one from Alex Payne: In Haskell's 18 years on the programming language scene, it's been in the perpetual role of the underused theoretical ideal alternative. I can't count how many times I've seen "perhaps Haskell?" since researching languages became a hobby of mine. I'm seeing more and more programmers getting real work with Scala, not musing about its theoretical possibilities. I find that pragmatism encouraging. - Paul Milovanov

2 Answers

17
votes

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]
1
votes

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).