Derive a common supertype based on parameter values ​​and parameter parameters

Question

Should the following compile without requiring an explicit type definition on this ?

 def prepList[B >: A](prefix: PlayList[B]) : PlayList[B] = prefix.foldr(this: PlayList[B])((node, suffix) => suffix.prepNode(node)) 

It seems to me that the type should be able to infer. Is this just a limitation in the Scala compiler, or is there a theoretical and theoretical reason that this cannot be done? In fact, I still do not feel what can be used to input Scala.

Work through this method:

• B >: A by definition
• this is of type PlayList[A] , which is a subtype of PlayList[B] , since B >: A and PlayList is covariant in A
• node is of type B , the type of the prefix parameter.
• The second parameter for the function parameter f in foldr is of the same type (declared by B ) as the first parameter to foldr .
• Thus, suffix is of the same type as this , so in particular it is PlayList[A] . Since B >: A , suffix.prepNode() takes a B

I would like the compiler to see that suffix.prepNode(node) is legal, where node is of type B Apparently, this is only possible if I explicitly specify the type when calling foldr or a reference to this in this call.

Interestingly, if I specify explicit types in the function parameters as (node: B, suffix: PlayList[B]) , a type mismatch error is still generated for the method to call the suffix.prepNode(node) : "found: B, required: A"

I am using Scala 2.8 RC6. A complete example below, the line in question is line 8.

 sealed abstract class PlayList[+A] { import PlayList._ def foldr[B](b: B)(f: (A, B) => B): B def prepNode[B >: A](b: B): PlayList[B] = nel(b, this) def prepList[B >: A](prefix: PlayList[B]): PlayList[B] = // need to specify type here explicitly prefix.foldr(this: PlayList[B])((node, suffix) => suffix.prepNode(node)) override def toString = foldr("")((node, string) => node + "::" + string) } object PlayList { def nil[A]: PlayList[A] = Nil def nel[A](head: A, tail: PlayList[A]): PlayList[A] = Nel(head, tail) def nel[A](as: A*): PlayList[A] = as.foldRight(nil[A])((a, l) => l.prepNode(a)) } case object Nil extends PlayList[Nothing] { def foldr[B](b: B)(f: (Nothing, B) => B) = b } case class Nel[+A](head: A, tail: PlayList[A]) extends PlayList[A] { def foldr[B](b: B)(f: (A, B) => B) = f(head, tail.foldr(b)(f)) } 

---

EDIT: second attempt to reason using compilation steps

• Renaming for clarity, foldr accepts type parameters (T)((U, T) => T) . We are trying to infer values ​​of types U and T
• There is a connection between the first parameter of foldr and the second parameter of the function - this is the same, T (In a partial answer to Daniel.)
• The types of objects we pass as these parameters are this: PlayList[A] and suffix: PlayList[B]
• So, since B >: A , the most characteristic common type of super is PlayList[B] ; therefore, we have T == PlayList[B] . Note that we do not need any connection between U and T to deduce this.

This is where I am stuck:

• From the compilation error message, the inferencer explicitly thinks that node is of type B (i.e., U == B ).
• I do not see how it turns out that U == B does not derive it from a parameter of type suffix . (Can the Scala compiler do this?)
• If this output step occurs, then it follows that U == B , and we compiled successfully. So what step went wrong?

---

EDIT 2: When renaming the foldr parameter types above, I skipped that U == A by definition, this is a parameter of the type of the PlayList class. I think this is still consistent with the steps above because we are calling it on an instance of PlayList[B] .

So, on the call site T == PlayList[B] as the least common supertype of a couple of things and U == B by definition of foldr on the receiver. This seems concise enough to narrow down to a few options:

• the compiler cannot resolve these several types and compute the upper bound B
• error getting from PlayList[B] of foldr return type to prepNode parameter prepNode (skeptical)

Answer 1

I'm not an expert on type, but here's what happens when I try to make a conclusion.

((node, suffix) => suffix.prepNode(node)) returns an unknown type of PlayList[T] , where T extends A. It is passed as an argument to foldr, which returns the type of function that was passed to it ( PlayList[T] , where T extends A). And it should be some kind of PlayList[B] .

Therefore, I assume that this:PlayList[B] must indicate that T and B are related.

Perhaps you need the PlayList to be parametric in the two types of PlayList[+A, B >: A] , since you have prepNode and propList that seem to work on the same type that extends A?

In other words, your initial class definition could be defined as follows:

 def prepNode[T >: A](b: T): PlayList[T] def prepList[U >: A](prefix: PlayList[U]): PlayList[U] 

But you used B in both cases, and the compiler does not know that T and U are the same.

---

Change, you can play around with the -explaintypes option and see what the compiler does depending on the type of hint. The following is the output of the explanations and deletion :PlayList[B] (using 2.8.0.RC1):

 $ scalac -explaintypes -d classes Infer.scala found : node.type (with underlying type B) required: A prefix.foldr(this)((node, suffix) => suffix.prepNode(node)) ^ node.type <: A? node.type <: Nothing? B <: Nothing? <notype> <: Nothing? false Any <: Nothing? <notype> <: Nothing? false false false false B <: A? B <: Nothing? <notype> <: Nothing? false Any <: Nothing? <notype> <: Nothing? false false false Any <: A? Any <: Nothing? <notype> <: Nothing? false false false false false 

Hope this helps shed some light. The question may arise when the skalak can conclude, and when he cannot conclude, it would be useful.

Answer 2

The problem is that foldr does not indicate B >: A , therefore, as for foldr , there is no relation between its own types A and B As for foldr , suffix and node completely unrelated, even if you passed related parameters to it.