# Scala: existential types for a Map

5

I want to use a map of varying types on an unknown A:

``````val map: Map[Foo[A], Bar[A]] = ...
...
val foo = new Foo[Qux]
val bar: Bar[Qux] = map(foo)
``````

This doesn't work, because A is an unknown. I have to define it instead as:

``````val map: Map[Foo[_], Bar[_]] = ...
...
val foo = new Foo[Qux]
val bar: Bar[Qux] = map(foo).asInstanceOf[Bar[Qux]]
``````

This works, but the cast is ugly. I'd rather find a better way. I gather the answer is to use existential types with the `forSome` keyword, but I'm confused as to how that works. Should it be:

``````Map[Foo[A], Bar[A]] forSome { type A }
``````

or:

``````Map[Foo[A] forSome { type A }, Bar[A]]
``````

or:

``````Map[Foo[A forSome { type A }], Bar[A]]
``````

8

Actually, none of these work.

``````Map[Foo[A], Bar[A]] forSome { type A }
``````

is a `Map` where all keys are of the same type `Foo[A]` and values of type `Bar[A]` (but the type `A` may be different for different maps of this type); in second and third examples, `A` in `Bar[A]` is completely different from `A` under `forSome`.

This ugly workaround should work:

``````// need type members, so can't use tuples
case class Pair[A, B](a: A, b: B) {
type T1 = A
type T2 = B
}

type PairedMap[P <: Pair[_, _]] = Map[P#T1, P#T2]

type FooBarPair[A] = Pair[Foo[A], Bar[A]]

val map: PairedMap[FooBarPair[_]] = ...
``````
3

I want to use a map of varying types on an unknown A

So, you want a variant of `Map[K,V]` with following interface, correct?

``````trait DependentMap[K[_],V[_]] {
def add[A](key: K[A], value: V[A]): DependentMap[K,V]
def get[A](key: K[A]): Option[V[A]]
}
``````

Whether it is or not might be a bit hard to tell from the type signature, so let's create a few dummy values and see if the type checker accepts what we want it to accept and rejects what we want it to reject.

``````// dummy definitions just to check that the types are correct
case class Foo[+A](a: A)
case class Bar[+A](a: A)
val myMap: DependentMap[Foo,Bar] = null

myMap.add(Foo(   42), Bar(   43)) // typechecks
myMap.add(Foo(   42), Bar("bar")) // type mismatch

val r1: Option[Bar[   Int]] = myMap.get(Foo(   42)) // typechecks
val r2: Option[Bar[String]] = myMap.get(Foo("foo")) // typechecks
val r3: Option[Bar[String]] = myMap.get(Foo(   42)) // type mismatch
``````

So far so good. But look what happens once we start to play with inheritance:

``````val fooInt: Foo[Int] = Foo(42)
val fooAny: Foo[Any] = fooInt
val barStr: Bar[String] = Bar("bar")
val barAny: Bar[Any] = barStr
println(fooInt == fooAny) // true
``````

Since `fooInt` and `fooAny` are the same value, we'd naïvely expect this `get` to succeed. According to the type signature of `get`, it would have to succeed with a value of type `Bar[Int]`, but where would this value come from? The value we put in has the type `Bar[Any]` and also the type `Bar[String]`, but certainly not the type `Bar[Int]`!

Here's another surprising case.

``````val fooListInt: Foo[List[Int]]    = Foo(List[Int]())
val fooListStr: Foo[List[String]] = Foo(List[String]())
println(fooListInt == fooListStr) // true!
``````

This time `fooListInt` and `fooListStr` look like they should be distinct, but in fact they both have the value `Nil`, of type `List[Nothing]`, which is a subtype of both `List[Int]` and `List[String]`. So if we want to mimic the behaviour of `Map[K,V]` on such a key, `get` would again have to succeed, but it can't since we gave it a `Bar[List[Int]]` and it needs to produce a `Bar[List[String]]`.

All this to say, our `DependentMap` should not consider keys to be equal unless the type `A` given to `add` is also equal to the type `A` given to `get`. Here is an implementation which uses type tags to ensure that this is the case.

``````import scala.reflect.runtime.universe._

class DependentMap[K[_],V[_]](
inner: Map[
(TypeTag[_], Any),
Any
] = Map()
) {
key: K[A], value: V[A]
)(
implicit tt: TypeTag[A]
): DependentMap[K,V] = {
val realKey: (TypeTag[_], Any) = (tt, key)
new DependentMap(inner + ((realKey, value)))
}

def get[A](key: K[A])(implicit tt: TypeTag[A]): Option[V[A]] = {
val realKey: (TypeTag[_], Any) = (tt, key)
inner.get(realKey).map(_.asInstanceOf[V[A]])
}
}
``````

And here are a few examples demonstrating that it works as expected.

``````scala> val myMap: DependentMap[Foo,Bar] = new DependentMap

res0: Option[Bar[Int]] = Some(Bar(43))

res1: Option[Bar[String]] = Some(Bar(bar))

error: type mismatch;

res2: Option[Bar[Int]] = None

res3: Option[Bar[Any]] = Some(Bar(bar))

res4: Option[Bar[List[Int]]] = Some(Bar(List(43)))

res5: Option[Bar[List[String]]] = None
``````

This works, but the cast is ugly. I'd rather find a better way.

Then you're probably disappointed that my `get` is implemented using a cast. Let me try to convince you that there is no other way.

Instead of a map which may or may not contain our key, let's consider a much simpler case.

``````def safeCast[A,B](
value: A
)(
implicit tt1: TypeTag[A], tt2: TypeTag[B]
): Option[B] = {
if (tt1 == tt2)
Some(value.asInstanceOf[B])
else
None
}
``````

Given a type tag for A and a type tag for B, if the two type tags are equal, then we know that A and B are the same type, and therefore the typecast is safe. But how could we possibly implement this without a typecast? The equality check returns a mere boolean, not a witness of equality like in some other languages. Therefore there is nothing which statically distinguishes the two branches of the `if` and the compiler cannot possibly know that a cast-free conversion is legal in the "true" branch but illegal in the other.

In the more complicated case of our `DependentMap`, we also have to compare our type tag with the one we stored when we did an `add`, and so we also have to use a cast.

I gather the answer is to use existential types with the `forSome` keyword

I can see why you'd think so. You want a bunch of associations from key to value, where each (key, value) pair has the type `(Foo[A], Bar[A]) forSome {type A}`. And indeed, if you were not concerned with performance, you could store those associations in a list:

``````val myList: List[(Foo[A], Bar[A]) forSome {type A}]
``````

Since the `forSome` is inside the brackets, this allows each entry in the list to use a different A. And since `Foo[A]` and `Bar[A]` are both to the left of the `forSome`, in each entry the `A`s must match.

In the case of Map, however, there is no place to put the `forSome` to obtain the result you want. The problem with Map is that it has two type parameters, which prevents us from from putting them both to the left of the `forSome` without putting the `forSome` outside of the brackets. It wouldn't make sense to do so: since the two type parameters are independent, there is nothing which links one occurrence of the left type parameter to a corresponding occurrence of the right type parameter, and so there is no way to know which `A`s should match. Consider the following counter-example:

``````case class NotMap[K,V](k1: K, k2: K, v1: V, v2: V, v3: V)
``````

There isn't the same number of K values as there are V values, so in particular there is no correspondence between the K values and the V values. If there was some special syntax like `Map[{Foo[A], Bar[A]} forSome {type A}]` which would allow us to specify that for each entry in the Map, the `A`s should match, then it would also be possible to use that syntax to specify the nonsense type `NotMap[{Foo[A], Bar[A]} forSome {type A}]`. Therefore there is no such syntax, and we need to use a type other than `Map`, such as `DependentMap` or `HMap`.

0

``````def map[A]: Map[Foo[A], Bar[A]] = ...
val myMap = map[Qux]
...
val foo = new Foo[Qux]
val bar: Bar[Qux] = myMap(foo)
``````

Or (inspired by Alexey Romanov's answer)

``````type MyMap[A] = Map[Foo[A],Bar[A]]
val map:MyMap[Qux] = ...
...
val foo = new Foo[Qux]
val bar: Bar[Qux] = map(foo)
``````