Map with path-dependent value type?

Question

I know that Scala has path-dependent types, so for example if I have a class within an inner class I can constrain one argument of a method to be an instance of the inner class of the other argument:

class Outer { class Inner( x:Int ) }
val o1 = new Outer
val o2 = new Outer
val i11 = new o1.Inner(11)
val i12 = new o1.Inner(12)
val i21 = new o2.Inner(21)
def f[ A <: Outer ]( a:A )( i:a.Inner ) = (a,i)
f(o1)(i11)  // works
f(o1)(i21)  // type mismatch; i21 is from o2, not o1

And I can create a Map from an Outer to an Inner using a type projection:

var m = Map[Outer,Outer#Inner]()

But that would allow entries like o1 -> i21, and I don't want that to be allowed. Is there any type magic to require that a value be an instance of its key's inner class? That is, I want to say something like

var m = Map[Outer,$1.Inner]()  // this doesn't work, of course

Salivation

The way you phrased the question: "require that the value be an instance of the key's inner class" already describes your var m = Map[Outer,Outer#Inner]() – Wilding

Defining the map with a type projection like that requires that the value be an instance of some Outer's Inner, but not the Outer that was used for they key. – Salivation

def g[A <: Outer] = Map.empty[A, A#Inner] – Wilding

I don't think the type system is going to help you here (unless you go the route of something like Shapeless's HMap), but you can always police what gets added to the map. – Climatology

You'd need a new, more constrained Map type or arbitrary dependent types in Scala. The former you can write as a safe wrapper around the existing Map. You'd basically have it be parametrized only by the key type, with a constraint that the key have some named inner type, and then your accessor methods would have types like def get(k: K): k.Inner. It wouldn't implement the current Scala collection generic map traits. – Detonate

Answer 1

No.

Path dependent types are scoped to an object instance, as in the example you gave:

def f[ A <: Outer ]( a:A )( i:a.Inner ) = (a,i)

Here the path-dependent type relies on the object reference "a", which is in scope for the declaration of the second parameter list.

The map definition looks a bit like:

trait Map[A,+B] {
  def get(key: A): Option[B]
  def + [B1 >: B](kv: (A, B1)): This
}

There is no object of type A in scope here for you to reference when defining B.

As others have hinted, you could define a new similar Map class which fits this requirement:

trait Map2[A <: Outer] {
  def get(key: A): Option[key.Inner]
  def put(key: A)(value: key.Inner): this.type
}

Schroer

Travis and Dan actually answered the question for me via comments almost a year and a half ago, but for future readers it's nice to have an actual answer that explains things more clearly, so I'll accept this as the answer, Rich. – Salivation