title: creating two related ASTs with sealed case classes in Scala
body: <p>Whenever I've had to create an AST in Scala, I've used the abstract sealed trait/ case class pattern.  It's worked really well so far, having compiler checked pattern matching is a big win.</p>
  
  <p>However now I've hit a problem that I cant wrap my head around.  What if I have 2 languages where one is a subset of the other?  As a simple example consider a lambda calculus where every variable is bound, and another related language where the variables could be bound or free.</p>
  
  <p>First language:</p>
  
  <pre><code>  abstract sealed class Expression
  
    case class Variable(val scope: Lambda, val name:String) extends Expression
  
    case class Lambda(val v: Variable, val inner: Expression) extends Expression
  
    case class Application(val function: Expression, val input: Expression) extends Expression
  </code></pre>
  
  <p>Second Language:</p>
  
  <pre><code>  abstract sealed class Expression
  
    case class Variable(val name:String) extends Expression
  
    case class Lambda(val v: Variable, val inner: Expression) extends Expression
  
    case class Application(val function: Expression, val input: Expression) extends Expression
  </code></pre>
  
  <p>Where the only change is the removal of scope from Variable.</p>
  
  <p>As you can see there is a lot of redundancy.  But because I'm using sealed classes, its hard to think of a good way to extend it.  Another challenge to combining them would be that now every Lambda and Application needs to keep track of the language of its parameters, at the type level.</p>
  
  <p>This example is not so bad because it is very small, but imagine the same problem for strict HTML/weak HTML.</p>