8

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.

Paul Milovanov
  • 706
  • 4
  • 18
  • 1
    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 Apr 28 '10 at 21:21
  • 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 Apr 28 '10 at 22:19
  • 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 Apr 28 '10 at 22:19
  • 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 Apr 28 '10 at 23:32
  • 1
    There's an interesting discussion on http://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 Apr 29 '10 at 05:16
  • For the record, e.g. `type Foo = Either String Foo` doesn't compile in Haskell either with error `Cycle in type synonym declarations`. – Erik Kaplun Mar 19 '14 at 02:07
  • ...P.S. but then again, `newtype T = T (Either String T)` is perfectly allowed in Haskell. – Erik Kaplun Mar 19 '14 at 02:14

2 Answers2

17

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]
ArtemGr
  • 11,684
  • 3
  • 52
  • 85
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).

Erik Kaplun
  • 37,128
  • 15
  • 99
  • 111