Minimal framework in Scala for collections with inheriting return type

Question

Suppose one wants to build a novel generic class, Novel[A]. This class will contain lots of useful methods--perhaps it is a type of collection--and therefore you want to subclass it. But you want the methods to return the type of the subclass, not the original type. In Scala 2.8, what is the minimal amount of work one has to do so that methods of that class will return the relevant subclass, not the original? For example,

class Novel[A] /* What goes here? */ {
  /* Must you have stuff here? */
  def reverse/* What goes here instead of :Novel[A]? */ = //...
  def revrev/*?*/ = reverse.reverse
}
class ShortStory[A] extends Novel[A] /* What goes here? */ {
  override def reverse: /*?*/ = //...
}
val ss = new ShortStory[String]
val ss2 = ss.revrev  // Type had better be ShortStory[String], not Novel[String]

Does this minimal amount change if you want Novel to be covariant?

(The 2.8 collections do this among other things, but they also play with return types in more fancy (and useful) ways--the question is how little framework one can get away with if one only wants this subtypes-always-return-subtypes feature.)

Edit: Assume in the code above that reverse makes a copy. If one does in-place modification and then returns oneself, one can use this.type, but that doesn't work because the copy is not this.

Arjan linked to another question that suggests the following solution:

def reverse: this.type = {
  /*creation of new object*/.asInstanceOf[this.type]
}

which basically lies to the type system in order to get what we want. But this isn't really a solution, because now that we've lied to the type system, the compiler can't help us make sure that we really do get a ShortStory back when we think we do. (For example, we wouldn't have to override reverse in the example above to make the compiler happy, but our types wouldn't be what we wanted.)

Answer 1

Edit: I just realized that Rex had a concrete class Novel in his example, not a trait as I've used below. The trait implementation is a bit too simple to be a solution to Rex's question, therefore. It can be done as well using a concrete class (see below), but the only way I could make that work is by some casting, which makes this not really 'compile time type-safe'. This So this does not qualify as a solution.

Perhaps not the prettiest, but a simple example using abstract member types could be implemented as follows:

trait Novel[A] { 
   type T <: Novel[A] 
   def reverse : T 
   def revrev : T#T = reverse.reverse 
}

class ShortStory[A](var story: String) extends Novel[A] {
 type T = ShortStory[A]
 def reverse : T = new ShortStory[A](story reverse)
 def myMethod: Unit = println("a short story method")
}

scala> val ss1 = new ShortStory[String]("the story so far")
ss1: ShortStory[String] = ShortStory@5debf305

scala> val ssRev = ss1 reverse 
ssRev: ss1.T = ShortStory@5ae9581b

scala> ssRev story
res0: String = raf os yrots eht

scala> val ssRevRev = ss1 revrev
ssRevRev: ss1.T#T = ShortStory@2429de03

scala> ssRevRev story
res1: String = the story so far

scala> ssRevRev myMethod
a short story method

It's certainly minimal, but I doubt whether this would enough to be used as a kind of framework. And of course the types returned not anywhere near as clear as in the Scala collections framework, so perhaps this might be a bit too simple. For the given case, it seems to do the job, however. As remarked above, this does not do the job for the given case, so some other solution is required here.

Yet Another Edit: Something similar can be done using a concrete class as well, though that also not suffices to be type safe:

class Novel[A](var story: String) {
  type T <: Novel[A] 
  def reverse: T = new Novel[A](story reverse).asInstanceOf[T]  
  def revrev : T#T = reverse.reverse
}
class ShortStory[A](var s: String) extends Novel[A](s) {
 type T = ShortStory[A]
 override def reverse : T = new ShortStory(story reverse)
 def myMethod: Unit = println("a short story method")
}

And the code will work as in the trait example. But it suffers from the same problem as Rex mentioned in his edit as well. The override on ShortStory is not necessary to make this compile. However, it will fail at runtime if you don't do this and call the reverse method on a ShortStory instance.

Answer 2

I haven't thought this through fully, but it type checks:

object invariant {
  trait Novel[A] {
    type Repr[X] <: Novel[X]

    def reverse: Repr[A]

    def revrev: Repr[A]#Repr[A]
       = reverse.reverse
  }
  class ShortStory[A] extends Novel[A] {
    type Repr[X] = ShortStory[X]

    def reverse = this
  }

  val ss = new ShortStory[String]
  val ss2: ShortStory[String] = ss.revrev
}

object covariant {
  trait Novel[+A] {
    type Repr[X] <: Novel[_ <: X]

    def reverse: Repr[_ <: A]

    def revrev: Repr[_ <: A]#Repr[_ <: A] = reverse.reverse
  }

  class ShortStory[+A] extends Novel[A] {
    type Repr[X] = ShortStory[X]

    def reverse = this
  }

  val ss = new ShortStory[String]
  val ss2: ShortStory[String] = ss.revrev
}

EDIT

The co-variant version can be much nicer:

object covariant2 {
  trait Novel[+A] {
    type Repr[+X] <: Novel[X]

    def reverse: Repr[A]

    def revrev: Repr[A]#Repr[A] = reverse.reverse
  }

  class ShortStory[+A] extends Novel[A] {
    type Repr[+X] = ShortStory[X]

    def reverse = this
  }

  val ss = new ShortStory[String]
  val ss2: ShortStory[String] = ss.revrev
}