Relating parameterized types

Question

I have a map where both the keys and values are generic types. Something like this:

Map[Foo[A], Bar[A]]

What I'd like to express is that the type A may be different for each key-value pair in the map, but every key is always parameterized with the same type as the value that it maps to. So a Foo[Int] always maps to a Bar[Int], a Foo[String] always maps to a Bar[String], and so forth.

Does anyone know a way to express this?

EDIT:

Here's an example of the sort of thing I'm trying to do:

trait Parameter // not important what it actually does

class Example {
  val handlers: Map[_ <: Parameter, (_ <: Parameter) => _] = Map()

  def doSomething() {
    for ((value, handler) <- handlers) {
      handler(value)
    }
  }
}

The idea is that a value will always map to a function that can accept it as a parameter, but as the code is written now, the compiler can't know this.

Answer 1

As it turns out, it is possible to define a heterogeneous map in Scala. Here's a rough sketch:

class HMap[A[_], B[_]] extends Iterable[HMap.Mapping[A, B, _]] {
  private val self = mutable.Map[A[_], B[_]]()

  def toMapping[T](a: A[_], b: B[_]): HMap.Mapping[A, B, T] = {
    HMap.Mapping(a.asInstanceOf[A[T]], b.asInstanceOf[B[T]])
  }

  def iterator: Iterator[HMap.Mapping[A, B, _]] =
    new Iterator[HMap.Mapping[A, B, _]] {
      val sub = self.iterator

      def hasNext = sub.hasNext
      def next(): HMap.Mapping[A, B, _] = {
        val (key, value) = sub.next()
        toMapping(key, value)
      }
    }

  def update[T](key: A[T], value: B[T]) = (self(key) = value)
  def get[T](key: A[T]) = self.get(key).asInstanceOf[Option[B[T]]]
  def apply[T](key: A[T]) = self(key).asInstanceOf[B[T]]
}

object HMap {
  case class Mapping[A[_], B[_], T](val key: A[T], val value: B[T])
}

This could be made completely typesafe by internally using a linked list of mappings instead of a map, but this is better for performance.

My original example would look like this:

object Example {
  type Identity[T] = T
  type Handler[T] = (T) => _

  val handlers = new HMap[Identity, Handler]

  def doSomething() {
    for (HMap.Mapping(value, handler) <- handlers) {
      handler(value)
    }
  }
}

This is almost perfect, except I'm not sure how to add bounds.

Answer 2

You're trying to describe a sort of higher-rank polymorphic, heterogeneous map, where each key-value pair in the map can have a different type parameter. As cool as it would be, Scala's type system doesn't allow you to express this statically. I think the best you can do is to define some horrible, unsafe helper methods:

def get [A] (map: Map[Foo[_], Bar[_]], k: Foo[A]) : Bar[A] 
def put [A] (map: Map[Foo[_], Bar[_]], k: Foo[A], v: Bar[A])

You might be able to make it somewhat more safe using Manifests to reify the type parameters of each key-value pair at runtime, but I'm not sure how...