Scala type matching map
It's been a couple of months so maybe you've moved on, but I had a look through this today. I also may have read too much into your example use case, so apologies if this isn't helpful.

If like in your example we can restrict the scope down to cases where K is covariant, and we can also remove the higher-kindedness of the value type, then we can improve the type safety significantly. So much so that we can escape all of the asInstanceOf calls!

class TypeMatchingMap[K[+_ &lt;: B], B](private val contents: Map[K[B], B]) {
  def +[T &lt;: B](kv: (K[T], T)): TypeMatchingMap[K, B] =
    new TypeMatchingMap[K, B](contents + kv)

  def -[T &lt;: B](k: K[T]): TypeMatchingMap[K, B] =
    new TypeMatchingMap[K, B](contents - k)

  def apply[T &lt;: B : ClassTag](k: K[T]): T =
    contents(k) match {
      case t: T =&gt; t
      case _ =&gt; throw ??? // Insert throwable here
    }

  def get[T &lt;: B : ClassTag](k: K[T]): Option[T] =
    contents.get(k).flatMap {
      case t: T =&gt; Some(t)
      case _ =&gt; None
    }

  def toSeq: Seq[(K[B], B)] = contents.toSeq

  override def toString: String = contents.toString()

  override def equals(obj: Any): Boolean =
    obj match {
      case m: TypeMatchingMap[_, _] =&gt; m.contents == this.contents
      case _ =&gt; false
    }

  override def hashCode(): Int = contents.hashCode()
}

object TypeMatchingMap {
  def empty[K[+_ &lt;: B], B]: TypeMatchingMap[K, B] =
    new TypeMatchingMap[K, B](Map.empty)
}

object TypeMatchingMapTest extends App {
  sealed trait NumBox
  type BoxID[+T &lt;: NumBox] = UUID

  case class FloatBox(n: Float) extends NumBox
  case class DoubleBox(n: Double) extends NumBox
  case class IntBox(n: Int) extends NumBox

  var map: TypeMatchingMap[BoxID, NumBox] = TypeMatchingMap.empty[BoxID, NumBox]

  val id5f: BoxID[FloatBox] = UUID.randomUUID()
  map = map + (id5f -&gt; FloatBox(5f))

  val id6d: BoxID[DoubleBox] = UUID.randomUUID()
  map = map + (id6d -&gt; DoubleBox(6.0))

  val id7i: BoxID[IntBox] = UUID.randomUUID()
  map = map + (id7i -&gt; IntBox(7))

  val f5: FloatBox = map(id5f)
  val d6: DoubleBox = map(id6d)
  val i7: IntBox = map(id7i)

  println(map)
  println(map.toSeq)
}


If you can't make the assumptions I've made above, I'd still recommend changing the signature of - to def -[T &lt;: B](k: K[T]): TypeMatchingMap[K, V, B]. Consider the following:

val map: TypeMatchingMap[K, V, Int] = ???
val k: K[String] = ???
map - k


We know that the last line won't ever do anything useful, so in my mind it would be kinder to prevent it from compiling so as to prevent any client of the API from making a mistake.

Happy to discuss the code more, but didn't want to go into too much detail if you're no longer interested.