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)

Tumescent

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.

Homage

You're right that I'm looking for the compiler to see that these should be the same, in some sense, for this invocation, but in general T and U are not the same: consider the case where I call these two methods separately. B in that declaration is only the name of the type bound used within that method scope. In this case, my understanding is that PlayList[B] is a common supertype of this and suffix, and should therefore be inferred to be the type of both. That is, the formal type parameter B of prepNode should have the same value in this invocation as the actual type parameter B of prepList. – Tumescent

Then may be my suggestion is not the right one. Still, it seems that having to specify this: PlayList[B] makes sense to me. – Homage

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.

Astonishing

I'm not sure I follow. In general we don't want that constraint on the declaration of foldr (certainly there are other valid uses where B has no relation to A) and I don't see that we need it in this case to resolve the types. I've updated the question with an attempt to reason this through... – Tumescent