Why this Scala code hangs if you specify type-parameter?

Question

Recently, I've played with type-level programming in Scala, and found the following:

trait NextPage[Curr, Next] {
  def next : Next
}

class Foo
class Bar

class X(val year : Int)

object X {
  implicit def xToNextPage[Y](x : X) : NextPage[X, Y] =
    if (x.year == 2010) {
      new X(x.year) with NextPage[X, Bar] {
        def next = new Bar 
      }
    }
    else {
      new X(x.year) with NextPage[X, Foo] {
        def next = new Foo
      }
    }
}

val x = new X(2010)
val y = x.next //BOOM!

The last line freezes the interpreter indefinitely. What is strange, that if you alter just one line of code from this:

implicit def xToNextPage[Y](x : X) : NextPage[X, Y] =

to that

implicit def xToNextPage(x : X) : NextPage[X, _] =

computation will be performed successfully (but resulting type will be lost, of course).

Do you have any idea why this is the case? I believe, that it's connected with type-inference somehow...

Answer 1

Well the cause is that it is in infinite recursion, thanks to implicit conversion. Remove implicit keyword from xToNextPage and it shows an error:

<console>:29: error: type mismatch;
 found   : X with NextPage[X,Bar]
 required: NextPage[X,Y]
             new X(x.year) with NextPage[X, Bar] {

Obviously your function declaration says that you are returning NextPage[X, Y] but you actually return NextPage[X,Any].

It goes in recursion because when marked as implicit because your function return type is of [X, Y]. But because you are returning [X,Any], it again calls the implicit function xToNextPage to try converting it.

Solution: Change declaration to:

trait NextPage[Curr, +Next] {
  def next : Next
}
implicit def xToNextPage[Y](x : X) : NextPage[X, Any]

Answer 2

I'm not sure what you're trying to achieve here. I don't really have any experience with type-level programming in Scala, but this doesn't look like correct type-level programming to me. What exactly are you trying to achieve with the type parameter Y in xToNextPage[Y](x : X)? The only possible value for Next[X, Y] is Next[X, AnyRef], since the least-common-ancestor of Foo and Bar is AnyRef. Getting rid of the Y gives you the only correct answer:

trait NextPage[Curr, Next] {
  def next : Next
}

class Foo
class Bar

class X(val year : Int)

object X {
  implicit def xToNextPage(x : X) =
    if (x.year == 2010) {
      new X(x.year) with NextPage[X, Bar] {
        def next = new Bar 
      }
    }
    else {
      new X(x.year) with NextPage[X, Foo] {
        def next = new Foo
      }
    }
}

val x = new X(2010)
val y = x.next // => y: Object = Bar@6704e2a0

I don't think this really answers your question, but I think it might help a little. I would be interested to see if someone else can come up with a solution that actually infers y: Bar, but I think that's beyond the limitations of the type system.