Joe Kearney
Joe Kearney

Reputation: 7547

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:

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

This is where I get stuck:


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:

Upvotes: 7

Views: 829

Answers (2)

huynhjl
huynhjl

Reputation: 41656

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.

Upvotes: 3

Daniel C. Sobral
Daniel C. Sobral

Reputation: 297305

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.

Upvotes: 1

Related Questions