Dart: efficiently rebuilding tree structures

Question

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. BuiltValue seems like the perfect base to start from, but I'm pondering the best way of structuring the builder.

Use case: given an expression tree and some manipulation, construct the manipulated expression tree efficiently. Examples:

// 2 + 3 -> 5
Sum([Int(2), Int(3)]).simplify() == Int(5)

// (x + y)^2 -> x^2 + 2*x*y + y^2
Power(Sum([Symbol('x'), Symbol('y')]), Int(2)).expand() == Sum(...)

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.

Naively I could create a separate builder for each expression type - IntBuilder, SumBuilder etc. - but during these manipulations the root type can change.

Things I've considered:

• per-class builders - though I'm unsure how to change root-type changes. Simplifications like Sum([x]).simplify() == x (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.
• a single ExpressionBuilder that tracks operands and some enum-like object identifying the resulting subclass.

Am I missing something really obvious?

Answer 1

I was giving myself uneccessary constraints.

While I originally thought all builder manipulations should mutate the instantiating builder and return nothing, the problem becomes much simpler if one simply requires those manipulations to return a builder. unarySimplify (builder equivalent of Sum([x]) -> x) below.

class SumBuilder implements ExpressionBuilder {
    ListBuilder<ExpressionBuilder> args;
    ExpressionBuilder unarySimplify() => args.length == 1? args[0]: this;
}