Scala: existential types for a Map

Question

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

Answer 1

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[_]] = ...

Answer 2

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("foo"), Bar("bar")) // 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
myMap.add(fooAny, barAny).get(fooInt) // Bar("bar")?

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!
myMap.add(fooListInt, Bar(List(42))).get(fooListStr) // Bar(List(42))?

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()
) {
  def add[A](
    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


scala> myMap.add(Foo(42), Bar(43)).get(Foo(42))
res0: Option[Bar[Int]] = Some(Bar(43))

scala> myMap.add(Foo("foo"), Bar("bar")).get(Foo("foo"))
res1: Option[Bar[String]] = Some(Bar(bar))


scala> myMap.add(Foo(42), Bar("bar")).get(Foo(42))
error: type mismatch;

scala> myMap.add[Any](Foo(42), Bar("bar")).get(Foo(42))
res2: Option[Bar[Int]] = None

scala> myMap.add[Any](Foo(42), Bar("bar")).get[Any](Foo(42))
res3: Option[Bar[Any]] = Some(Bar(bar))


scala> myMap.add(Foo(List[Int]()), Bar(List(43))).get(Foo(List[Int]()))
res4: Option[Bar[List[Int]]] = Some(Bar(List(43)))

scala> myMap.add(Foo(List[Int]()), Bar(List(43))).get(Foo(List[String]()))
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 As 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 As 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 As 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.

Answer 3

What about something like

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)