Trouble with encapsulating "recursive types" in Scala

Question

Sorry, I have hard times figuring out a relevant title for my problem.

I want to model the following behavior: I designed a "language" with expressions that encapsulate standard Scala types. Expressions can be either variables or sequences of expressions. In the following, A can be a standard Scala type (namely Boolean, Int, Double). I also want to implement a method to replace expressions by other in expressions (particularly in sequences). I tried some code which I cannot manage to compile. I placed quotation marks when I do not really know what type to put but all the this is probably messy. I have special trouble with the Sequence thing, due to its recursive nature.

sealed trait Expression[A] {
  def replace[B](a: Expression[B], b: Expression[B]): Expression[?]
}

trait Variable[A] extends Expression[A] {
  def replace[B](a: Expression[B], b: Expression[B]) = 
    if (a == this) b else this
}

case class Sequence[A <: Expression[B]](values: Seq[A]) extends Expression[A] {
   def replace[B](a: Expression[B], b: Expression[B]) = 
     if (a == this) b
     else Sequence(values.map(_.replace(a, b)))
}

I assume of course that sequences are acyclic (a sequence cannot contain itself) as it would trigger an infinite recursion. These are used to implement n-ary matrices.

Thanks for your help.

Answer 1

It looks like you ran into one of those corner cases where Scala does not have an elegant solution.

What you need in the place of Expression[?] as the return type is actually a type that represents "this type", being the type that the trait is actually mixed into. There is no shorthand in Scala that lets you express this in a simple way, and you cannot use this.type either, as that is too specific and can only be used when you really always return this.

The solution usually quickly introduces mind-bending boilerplate. The Scala collections for example suffer from the same issue, traits like MapLike need to encode similar things.

I tried to quickly modify your sample to encode such a type. I made sure it compiles, but I did not run it:

sealed trait Expression[A, ThisType <: Expression[A, ThisType]] {
  def replace[B,C <: Expression[B,C]](a: Expression[B,C], b: Expression[B,C]): ThisType
}

trait Variable[A] extends Expression[A, Variable[A]] {
  def replace[B,C <: Expression[B,C]](a: Expression[B,C], b: Expression[B,C]) = 
    if (a == this) b.asInstanceOf[Variable[A]] else this
}

case class Sequence[A <: Expression[_,A]](values: Seq[A]) extends Expression[A, Sequence[A]] {
   def replace[B,C <: Expression[B,C]](a: Expression[B,C], b: Expression[B,C]) = 
     if (a == this) b.asInstanceOf[Sequence[A]]
     else Sequence(values.map(_.replace(a, b)))
}

It even has to use a cast, which usually is a smell on its own, but I'm not sure there is a way to avoid it in this case. At least it is safe, we know it has to have the right type, just the compiler does not know it. :-)