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)))
}

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)))
}

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 */
  }
}

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

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)
  }
}