Can't add member to Map using dynamic mixin type for the key

Question

The following statement compiles fine and works as expected:

val map : Map[_ >: Int with String, Int] = Map(1 -> 2, "Hello" -> 3)

However, if I try to add to the map:

map + ((3,4))

or

map + (("Bye", 4))

then I get a type mismatch:

found : java.lang.String("Bye")

required : _$1 where type _$1 >: Int with String

If I weaken the type signature to allow Any as the type of the Key, then this all works as expected.

My intuition says that this is to do with the nonvariance of Map's key type, and that _$1 is somehow being fixed as a particular supertype of Int with String, but I'm not particularly happy with this. Can anybody explain what's going on?

Edited to add:

In case you're wondering where this arises, it's the signature that you get if you do something like:

val map = if (true) Map(1 -> 2) else Map("1" -> 2)

Answer 1

You misunderstand Int with String. It is not the Union of Int and String, it is the intersection, and for Int and String it is empty. Not the sets of values that are Int with the set of values that are strings, but the set of values that have the characteristics of Int with the characteristics of String too. There are no such values.

You can use Either[Int, String], and have Map[Left(1) -> 2, Right("Hello") -> 3). Either is not exactly the Union, it is the discriminated union, A + B, rather than A U B. You may grasp the difference in that Either[Int, Int] is not the same thing as Int. It is in fact isomorphic to (Int, Boolean): you have an Int, and you know ont which side it is too. When A and B are disjoints (as Int and String are) A + B and A U B are isomorphic.

Or (not for the faint of heart) you can have a look at a possible encoding of union types by Miles Sabin. (I'm not sure you could actually use that with preexisting class Map, and even less sure than you should even try, but it makes a most interesing reading nevertheless).

---

Edit: Read your question and code way too fast, sorry

Your lower bound Int with String is the same as Nothing, so Map[_ >: Int with String, Int], is the same as Map[_ >: Nothing, Int] and as the Nothing lower bound is implied, this is Map[_, Int]. Your actual Map is a Map[Any, Int]. You could have added a boolean key, it works too, despite the Int with String. A Map[Any, Int] can be typed as Map[_, Int] so your val declaration works. But your typing loses all the information about the type of the key. Not knowing what the type of the key is, you cannot add (nor retrieve) anything from the table.

An UpperBound would have been no better, as then there is no possible key. Even the initial val declaration fails.

---

Edit 2 : regardingif (true) Map(1 -> 2) else Map("1" -> 2)

This is not the same thing as Map(1 -> 2, "1" -> 2). That was simpler, simply a Map[Any, Int], as Any is the greater common supertype of Int and String.

On the other hand, Map(1 -> 2) is a Map[Int, Int], and Map["1", 2] a Map[String, Int]. There is the problem of finding a common supertype for Map[Int, Int] and Map[String, Int], which is not finding a common supertype of Int and String.

Let's experiment. Map is covariant in its second parameter. If you use Int and String as values rather than keys :

if (true) Map(1 -> 2) else Map(1 -> "2")
res1: scala.collection.immutable.Map[Int, Any]

With covariance, it simply takes the common supertype of all type parameters.

With a contravariant type :

class L[-T]
object L{def apply[T](t: T) = new L[T])
class A
class B extends A
class C
if (true) L(new A) else L(new C)
res2: L[A with C]
if (true) L(new A) else L(new B)
res3: L[B]

it takes the intersection A with C. When B is a subtype of A, A with B is just B.

Now with the non-variant parameter of Map when the two types are related

if (true) Map(new A -> 1) else Map(new B -> 1)
res4: scala.collection.immutable.Map[_ >: B <: A, Int]

Such a type is not useless. You may access or add values with keys of type B. But you cannot access values of keys A. As this is what you have in the actual Map (because of the true), tough luck. If you access the keySet, it will be typed Set[A]. You have incomplete information on the type of the keys, and what you can do is limited, but this is a necessary limitation, given the limited knowledge you have on the type of the map. With Int and String, you have minimal information, with a lower bound Any and an upper bound equivalent to Nothing. The Nothing upper bound makes it impossible to call a routine which takes a key as a parameter. You can still retrieve the keySet, with type Set[Any], Any being the lower bound.