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. :-)

Answer 2

Usually in situations like this there is a required relationship between A and B. E.g., consider what happens when you add an element to a (hypothetical and highly simplified) sequence type:

class Sequence[+A] {
  def +: [B >: A](b: B): Sequence[B] = {
    /* Build the new sequence with b at the beginning and this sequence's elments after */
  }
}

So in your case (if this pattern applies for you), signature in Expression[A] would be:

def replace[B >: A](a: Expression[B], b: Expression[B]): Expression[B]

Answer 3

Thank you for your answers. I ended simplifying up my problem to obtain a simpler solution. I simply "flattened" the type parameter of sequences:

case class Sequence[A] (values: Seq[Expression[A]]) extends Expression[A] {
  def replace[B <: A](a: Expression[A], b: Expression[B]) {
    // (Code in initial question)
  }
}

A in Expression now means that Expression is either a variable of type A, a sequence of variables of type A, a sequence of sequence of variables of type A…

I lose expressiveness here, but gain in usability. Having two parameters for Expression was getting too complicated, and broke Java interoperability. Maybe I will try to improve this on later.