type systems - What does the `#` operator mean in Scala?

Question

I see this code in this blog: Type-Level Programming in Scala:

// define the abstract types and bounds
trait Recurse {
  type Next <: Recurse
  // this is the recursive function definition
  type X[R <: Recurse] <: Int
}
// implementation
trait RecurseA extends Recurse {
  type Next = RecurseA
  // this is the implementation
  type X[R <: Recurse] = R#X[R#Next]
}
object Recurse {
  // infinite loop
  type C = RecurseA#X[RecurseA]
}

There is an operator # in the code R#X[R#Next] which I've never seen. Since it's difficult to search it(ignored by search engines), who can tell me what does it mean?

Answer 1

To explain it, we first have to explain nested classes in Scala. Consider this simple example:

class A {
  class B

  def f(b: B) = println("Got my B!")
}

Now let's try something with it:

scala> val a1 = new A
a1: A = A@2fa8ecf4

scala> val a2 = new A
a2: A = A@4bed4c8

scala> a2.f(new a1.B)
<console>:11: error: type mismatch;
 found   : a1.B
 required: a2.B
              a2.f(new a1.B)
                   ^

When you declare a class inside another class in Scala, you are saying that each instance of that class has such a subclass. In other words, there's no A.B class, but there are a1.B and a2.B classes, and they are different classes, as the error message is telling us above.

If you did not understand that, look up path dependent types.

Now, # makes it possible for you to refer to such nested classes without restricting it to a particular instance. In other words, there's no A.B, but there's A#B, which means a B nested class of any instance of A.

We can see this in work by changing the code above:

class A {
  class B

  def f(b: B) = println("Got my B!")
  def g(b: A#B) = println("Got a B.")
}

And trying it out:

scala> val a1 = new A
a1: A = A@1497b7b1

scala> val a2 = new A
a2: A = A@2607c28c

scala> a2.f(new a1.B)
<console>:11: error: type mismatch;
 found   : a1.B
 required: a2.B
              a2.f(new a1.B)
                   ^

scala> a2.g(new a1.B)
Got a B.