Features of different kinds of path-dependent types in scala

Question

Suppose there is a trait:

trait OuterTrait {
  type InnerType
}

Now we can write non-generic function someAlgo:

def pairToString[S, U](x: S, y: U): String = 
  "{" + y.toString + " in " + x.toString + "}"

def pairPrintln[S, U](x: S, y: U) {
  println(pairToString(x, y))
}

def someAlgo(x: OuterTrait)(y: x.InnerType): x.InnerType = {
  pairPrintln(x, y)
  y
}

and series of generic functions:

def someAlgoObjObj[T <: OuterTrait](x: T)(y: x.InnerType): x.InnerType = {
  pairPrintln(x, y)
  y
}

def someAlgoObjType[T <: OuterTrait](x: T)(y: x.InnerType): T#InnerType = {
  pairPrintln(x, y)
  y
}

def someAlgoTypeType[T <: OuterTrait](x: T)(y: T#InnerType): T#InnerType = {
  pairPrintln(x, y)
  y
}

And one more generic function doesn't compile:

def someAlgoTypeObj[T <: OuterTrait](x: T)(y: T#InnerType): x.InnerType = {
  pairPrintln(x, y)
  y
}

It seems that: 1) someAlgo and someAlgoObjObj are the most correct functions; 2) and there is no sense to use generic function in this example at all.

And I would like to clarify some differences between generic functions above. Please, correct me, If I make errors.

So as I understand type T corresponds to static type of x (call it X) or explicit type of generic call (I mean algo[Int] for instance). That's why T#InnerType corresponds to type in declaration of type X. But x.InnerType also corresponds to InnerType of static type of x. Where is the difference?

Further... someAlgoObjType compiles, so it seems that x.InnerType must be subtype of T#InnerType. Then it is OK that someAlgoTypeObj doesn't compile, since we can't make downcast implicitly. Though we can rewrite last one:

def someAlgoTypeObj[T <: OuterTrait](x: T)(y: T#InnerType): x.InnerType = {
  pairPrintln(x, y)
  y.asInstanceOf[x.InnerType]
}

UPD1: I found one difference between someAlgoObjObj and someAlgoTypeType if use them with explicit type parameter. If we write some class extending OuterTrait:

class OuterIntClass extends OuterTrait{
  type InnerType = Int
}
val x: OuterIntClass = new OuterIntClass()
val y: Int = 5

Then:

someAlgoObjObj[OuterTrait](x)(y) // OK

and next call doesn't work:

someAlgoTypeType[OuterTrait](x)(y)

Megalopolis

there is a great blogpost on PDT, you should definitely read it – Timbered

Thank you, it's interesting. But I still have a problem with T#InnerType... – Megalopolis

Answer 1

T#InnerType means "A InnerType belonging in some T" while x.InnerType means "A InnerType belonging in a given x (of type OuterTrait)".

The key here in understanding these is in some T vs in a given x. You can interpret in some as some T but we don't which T instance, meaning that in a two Ts aren't necessarily the same, so, T#InnerType can't be proven to be equal to another T#InnerType.

Let's analyze the signatures:

/* 1 */ def someAlgoObjObj[T <: OuterTrait](x: T)(y: x.InnerType): x.InnerType = ???
/* 2 */ def someAlgoObjType[T <: OuterTrait](x: T)(y: x.InnerType): T#InnerType = ???
/* 3 */ def someAlgoTypeType[T <: OuterTrait](x: T)(y: T#InnerType): T#InnerType = ???

1. Given x and InnerType belonging in this x returns the its InnerType.
2. Given x and InnerType belonging in this x returns InnerType belonging to some T , meaning a some T is not necessarily the same instance as x.
3. Given x and InnerType belonging to some T returns InnerType belonging to some T

Now for the forth one:

def someAlgoTypeObj[T <: OuterTrait](x: T)(y: T#InnerType): x.InnerType = y

The signature reads: given x and InnerType belonging to some T, returns the InnerType belonging to this x. But in the implementation, we try to return y, which belongs to a T that's not necessarily the same as x, hence the compiler complains.

Inspired

But some type T propagates on the whole function signature. So we have some type T and parameter x of this some type T. You say «Given x and InnerType belonging in this x returns InnerType belonging to some T , meaning a some T is not necessarily the same instance as x.» Not the same — may be, but type of x must be subtype of T. – Megalopolis

I mean that when we call some instance of generic function we have the same instance Q of T everywhere in our function. And since x: Q, x.InnerType can't absolutely differ from Q#InnerType. – Megalopolis

You are missing the point. In (x: T)(y: T#InnerType), the Ts here denote different instances - not necessarily different, but the compiler can't make that distinction. The compiler can only rely on information you provide, and in this case since x.InnerType and y can be different it assumes it is fact different. – Inspired

In which way could they be different? It is true for def algo[T <: OuterTrait, S <: OuterTrait](x: T)(y: S#InnerType) — different type parameters. But type parameter T is the same everywhere in the function. Otherwise identical function wouldn't compile: def id[T](x: T): T = x like def id[T, S](x: T): S = x. – Megalopolis

Answer 2

Little note about update.

someAlgoTypeType[OuterTrait](x)(y) 

Failes because your method signature tells that it expects its y parameter to conform to the type T#InnerType and your y.type is Int. To make it work you should change it's type to the following:

class OuterIntClass extends OuterTrait{
  type InnerType = Int
}
val x: OuterIntClass = new OuterIntClass()
val y: x.InnerType = 5

Now y's type satisfies type projection T#InnerType and someAlgoTypeType[OuterTrait](x)(y) compiles

Timbered