infer a common supertype based on a parameter value and function parameter types

Question

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.
• second parameter to function parameter f in foldr has the same type (declared B) as the first parameter to foldr.
• Thus 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

• Renaming for clarity, foldr takes parameters of types (T)((U, T) => T). We're trying to infer the values of types U and T.
• There is a relationship between the first parameter to foldr and the second parameter to the function - they're the same thing, T. (In partial answer to Daniel.)
• The types of the objects we're passing as those parameters are this: PlayList[A] and suffix: PlayList[B]
• So, since 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:

• From the compile error message, the inferencer clearly thinks that node has type B (that is, U == B).
• I can't see how it gets to the conclusion that U == B without inferring it from the type parameter of suffix. (Can the scala compiler do this?)
• If that step of inference is what happens, then it follows that 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:

• the compiler can't resolve those multiple types and compute the upper bound of B
• bug in getting from return type PlayList[B] of foldr to type of parameter of prepNode (skeptical)

Answer 1

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.

Answer 2

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.