title: Trouble with encapsulating "recursive types" in Scala
body: <p>Sorry, I have hard times figuring out a relevant title for my problem.</p>
  
  <p>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.</p>
  
  <pre><code>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 &lt;: 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)))
  }
  </code></pre>
  
  <p>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.</p>
  
  <p>Thanks for your help.</p>