Generic inheritance in Scala

Question

I'm trying to implement a few structures from Okasaki's book in Scala, and in tests try to keep the actual tests in the base class, only using subclasses to provide the instance-under-test.

For example, a test for unbalanced (tree) set looks as follows:

class UnbalancedSetSpec
  extends SetSpec(new UnbalancedSet[Int])
  with IntElements

where

abstract class SetSpec[E, S](val set: Set[E, S]) extends Specification with ScalaCheck {

  implicit def elements: Arbitrary[E]

  // ...

  private def setFrom(es: Seq[E]): S = es.foldRight(set.empty)(set.insert)
}

Now sometimes I want to specialise the child spec, e.g.

class RedBlackSetSpec
  extends SetSpec(new RedBlackSet[Int])
  with IntElements {

  "fromOrdList" should {
    "be balanced" ! prop { (a: List[Int]) =>
      val s = RedBlackSet.fromOrdList(a.sorted)

      set.isValid(s) should beTrue
    }
  }
}

it fails because there's no method isValid on Set[E, S] — it's defined in RedBlackSet[E]. But if I go ahead and change SetSpec[E, S](val set: Set[E, S]) to SetSpec[E, S, SES <: Set[E, S]](val set: SES), this particular problem disappears, but the code still fails to compile:

Error:(7, 11) inferred type arguments [Nothing,Nothing,okasaki.RedBlackSet[Int]] do not conform to class SetSpec's type parameter bounds [E,S,SES <: okasaki.Set[E,S]]
  extends SetSpec(new RedBlackSet[Int])
          ^

Error:(7, 11) inferred type arguments [Nothing,Nothing,okasaki.UnbalancedSet[Int]] do not conform to class SetSpec's type parameter bounds [E,S,SES <: okasaki.Set[E,S]]
  extends SetSpec(new UnbalancedSet[Int])
          ^

The definition of RedBlackSet is as follows:

package okasaki

class RedBlackSet[E](implicit ord: Ordering[E]) extends Set[E, RBTree[E]] {

so I would expect E to be inferred as Int rather than Nothing, and S as RBTree[Int] — but it doesn't happen.

class RedBlackSetSpec
  extends SetSpec[Int, RedBlackSet.RBTree[Int], RedBlackSet[Int]](new RedBlackSet[Int])
  with IntElements {

and

class UnbalancedSetSpec
  extends SetSpec[Int, BinaryTree[Int], UnbalancedSet[Int]](new UnbalancedSet[Int])
  with IntElements

work fine, but look ugly.

I'm struggling to understand why E and S are not inferred here. Any hints?

Answer 1

This is actually a well-known problem with Scala type inference: it can't infer SES "first" and use it to infer E and S. One solution comes to mind:

class RedBlackSetSpec(override val set: RedBlackSet[Int]) extends SetSpec(set) with IntElements {
  def this() = this(new RedBlackSet[Int])
  ...
}

It becomes less ugly if you make set in SetSpec an abstract val instead of a constructor argument, but with a slight tradeoff in cases you don't need to specialize. I think there should be a better one, but this should work.