One of the limitations of a map collection class is that the keys and elements have to be defined uniformly with respect to types. We can't define keys that map to string-like elements or keys that map to int-like elements. That kind of dependent typing is impossible to do in Scala...or is it?
Consider a tuple case class that enforces a correspondence between two types:
case class TypeTuple2[S,T0[S0]](val _1 : T0[S], val _2 : S) {
override def toString = "(" + _1 + ", " + _2 + ")"
}
Here we are using Scala's support for higher-kinded types: T0 is a type that consume type parameters. In the constructor of TypeTuple2, the first _1 value's T0 must consume the same type parameter S that types the second _2 value. Now, consider a string key and int key that derive from the same symbol key:
case class SymbolKey[E](name : String)
trait StringSymbolKey extends SymbolKey[String]
trait IntSymbolKey extends SymbolKey[Int]
object nameKey extends SymbolKey[String]("name") with StringSymbolKey
object ageKey extends SymbolKey[Int]("age") with IntSymbolKey
Nothing fancy, except that we use StringSymbolKey and IntSymbolKey to reify the type parameter at run-time. Now consider a value:
val binding : TypeTuple2[_,SymbolKey]
An existential type (_) is used to indicate that we don't know what the S type parameter of binding is. Using Scala's support for GADTs, we can plugin this into a pattern match and figure out what the type parameter is:
binding match {
case TypeTuple2(key : StringSymbolKey,e) => e : String
case TypeTuple2(key : IntSymbolKey,e) => e : Int
}
No explicit cast is necessary because TypeTuple2 enforces that the E type parameters of key in SymbolKey is the same as the e, while the match of key against StringSymbolKey and IntSymblolKey binds the E type parmeter for SymbolKey.
Now, its just a little bit more work to put this into an enhanced map-like collection:
class DependentTypeMap[K[S0]] {
private val map = new HashMap[K[_],Any]
def apply[S](key : K[S]) : S = get(key).get
def get[S](key : K[S]) : Option[S] = map.get(key).asInstanceOf[Option[S]]
def update[S](key : K[S], element : S) : Unit = map.update(key, element)
def foreach(f : Function[TypeTuple2[_,K], Unit]) : Unit = map.foreach{
case (k,e) => f(TypeTuple2[Any,K](k.asInstanceOf[K[Any]],e))
}
}
We use a couple of unsafe asInstanceOf checks (get, foreach) to get around the fact that dependent data structures can't be expressed efficiently with a hash table. However, these checks don't interfere with the correctness of the data structure: map never leaks out and update enforces the TypeTuple2 invariant. We can also go with a slower asInstanceOf-free implementation that stores the map as a list of TypeTuple2 instances, which convinces me that the asInstanceOf calls are safe :).
Now some code to test the map:
val map = new DependentTypeMap[SymbolKey]
map(nameKey) ="Bob"
map(ageKey) =10
Console.println("NAME: " + (map(nameKey) : String))
Console.println(" AGE: " + (map( ageKey) : Int ))
map.foreach{
case TypeTuple2(key : StringSymbolKey,e) => e : String
case TypeTuple2(key : IntSymbolKey,e) => e : Int
}
Note that the following code leads to type errors:
map(nameKey) = 10
map(ageKey) = "Bob"
As a warning, when you use GADTs like this, you have to be careful to adhere to the standard hashCode/equals contract behavior, otherwise you can get class cast exceptions at run-time that the compiler cannot even warn you about. Consider:
class XXX[T] {
override def equals(that : Any) = true
}
object xxxS extends XXX[String]
object xxxI extends XXX[Int]
val binding : TypeTuple2[_,XXX] = TypeTuple2[Int,XXX](xxxI, 10)
val xxx = binding match {
case TypeTuple2(`xxxS`,e) => e : String
case TypeTuple2(`xxxI`,e) => e.toString
}
Oops! Because of Scala's support for GADTs, adherence to the equals contract is necessary to ensure overall static type safety in Scala.
