infer a common supertype based on a parameter value and function parameter types
Should the following be compiled without needing 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 inferred. Is this just a limitation in the Scala compiler, or is there a type-theoretic reason that this cannot be done? I don't really have a feel yet for what the Scala type inferencer can be expected to handle.
Working through that method:
B >: A by definition this has type PlayList[A] , which is a subtype of PlayList[B] since B >: A and PlayList is covariant in A . node has type B , the parameter type of prefix . f in foldr has the same type (declared B ) as the first parameter to foldr . suffix has the same type as this , so in particular it is a 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 has type B . It appears to be able to do this only if I explicitly specify a type on the invocation of foldr or on the reference to this in that invocation.
Interestingly, if I specify explicit types on the function parameters as (node: B, suffix: PlayList[B]) , a type mismatch error is still generated on the parameter to the method call suffix.prepNode(node) : "found: B, required: A"
I'm using Scala 2.8 RC6. Full 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 through the compilation steps
foldr takes parameters of types (T)((U, T) => T) . We're trying to infer the values of types U and T . foldr and the second parameter to the function - they're the same thing, T . (In partial answer to Daniel.) this: PlayList[A] and suffix: PlayList[B] B >: A , the most specific common super type is PlayList[B] ; therefore we have T == PlayList[B] . Note that we don't need any relationship between U and T to deduce this. This is where I get stuck:
node has type B (that is, U == B ). U == B without inferring it from the type parameter of suffix . (Can the scala compiler do this?) U == B , and we've compiled successfully. So which step went wrong? EDIT 2: In renaming the foldr parameter types above I missed that U == A by definition, it's the type parameter of the PlayList class. I think this is still consistent with the above steps though, since we're calling it on an instance of PlayList[B] .
So at the call site, T == PlayList[B] as the least common super-type of a couple of things, and U == B by definition of foldr on the receiver. That seems concise enough to narrow down to a couple of options:
B PlayList[B] of foldr to type of parameter of prepNode (skeptical) I'm no type expert but here is what happens when I try to infer.
((node, suffix) => suffix.prepNode(node)) returns some unknown type PlayList[T] , where T extends A . It is passed as an argument to foldr which returns the type of the function that was passed to it ( PlayList[T] where T extends A). And this is supposed to be of some type PlayList[B] .
So my guess is that this:PlayList[B] is necessary to indicate that T and B are related.
May be you need to have PlayList be parametric in two types PlayList[+A, B >: A] as you have prepNode and propList that seem to work on the same type that extends A?
Said differently, your original class definition could have been defined like this:
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 doesn't know that T and U are the same.
Edit, you can play around with the -explaintypes option and see what the compiler does depending on type hints you get. Here is the output of explaintypes and removing the :PlayList[B] (with 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. May be a question around when scalac can infer and when it cannot infer would be helpful.
The problem is that foldr does not specify B >: A , so, as far as foldr is concerned, there is no relationship between it's own A and B types. As far as foldr is concerned, suffix and node are completely unrelated -- even though you happen to have passed related parameters to it.
上一篇: SIMD / SSE新手：简单的图像过滤