title: Dart: efficiently rebuilding tree structures
body: <p>I have an architectural problem. I'm building a computer algebra system in Dart (though the language is largely irrelevant) and want immutable expression trees. <a href="https://pub.dartlang.org/packages/built_value" rel="nofollow noreferrer">BuiltValue</a> seems like the perfect base to start from, but I'm pondering the best way of structuring the builder.</p>
  
  <p>Use case: given an expression tree and some manipulation, construct the manipulated expression tree efficiently. Examples:</p>
  
  <pre><code>// 2 + 3 -&gt; 5
  Sum([Int(2), Int(3)]).simplify() == Int(5)
  
  // (x + y)^2 -&gt; x^2 + 2*x*y + y^2
  Power(Sum([Symbol('x'), Symbol('y')]), Int(2)).expand() == Sum(...)
  </code></pre>
  
  <p>Most manipulations will be the result of multiple chained manipulations, and the more I can avoid rebuilding the expressions at each step the better. Sometimes this won't be possible - e.g. after duplications.</p>
  
  <p>Naively I could create a separate builder for each expression type - <code>IntBuilder</code>, <code>SumBuilder</code> etc. - but during these manipulations the root type can change.</p>
  
  <p>Things I've considered:</p>
  
  <ul>
  <li>per-class builders - though I'm unsure how to change root-type changes. Simplifications like <code>Sum([x]).simplify() == x</code> (or the first example above) wouldn't be too hard to deal with after rebuild, but I'm not sure how they'd work with examples like the second above.</li>
  <li>a single ExpressionBuilder that tracks operands and some enum-like object identifying the resulting subclass.</li>
  </ul>
  
  <p>Am I missing something really obvious?</p>