tree - Dart:高效重建树结构

Question

我有一个架构问题。我正在 Dart 中构建计算机代数系统(尽管该语言很大程度上无关)并且想要不可变的表达式树。 BuiltValue似乎是一个完美的起点，但我正在考虑构建构建器的最佳方式。

用例:给定一个表达式树和一些操作，有效地构造被操作的表达式树。示例:

// 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(...)

大多数操作都是多个链式操作的结果，并且我越能避免在每一步重建表达式就越好。有时这是不可能的 - 例如重复之后。

我天真地可以为每个表达式类型创建一个单独的构建器 - IntBuilder、SumBuilder 等 - 但在这些操作期间，根类型可能会发生变化。

我考虑过的事情:

• 每类构建器 - 尽管我不确定如何更改根类型更改。像 Sum([x]).simplify() == x 这样的简化(或上面的第一个示例)在重建后不会太难处理，但我不确定它们是如何处理的d 使用上面第二个示例。
• 单个 ExpressionBuilder，用于跟踪操作数和一些标识生成子类的类似枚举的对象。

我是否遗漏了一些非常明显的东西？

Answer 1

我给自己施加了不必要的限制。

虽然我最初认为所有构建器操作都应该改变实例化构建器并且不返回任何内容，但如果只需要这些操作来返回构建器，问题就会变得简单得多。 unarySimplify(相当于下面的 Sum([x]) -> x 的构建器)。

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