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（或上面的第一个示例）这样的简化在重建后不太难处理，但我不确定它们如何与上面的第二个示例一起使用。 - 一个跟踪操作数和某些类似枚举的对象标识结果子类的单个ExpressionBuilder。

我是否忽略了什么非常明显的东西？

- DomJack

---

“Naively I could create a separate builder for each expression type - IntBuilder, SumBuilder etc. - but during these manipulations the root type can change." 这句话的意思是：我可能会天真地为每个表达式类型创建一个单独的构建器 - IntBuilder、SumBuilder 等等，但在这些操作过程中，根类型可能会发生变化。在不可变数据结构中，根节点总是会改变（分支和叶子节点不能改变或者它们是不可变的）。也许您可以分享一下代码，说明一下这是一个问题？ - Mike Fairhurst

根节点中包含的数据在重建时会发生变化，但通常类型不会改变 - 即签名为“Built -> Built”。例如，在重建后的BuiltList可以具有不同的元素，但它仍将保持为BuiltList。简化“单个元素的总和是该元素”的方法将具有签名BuiltSum -> BuiltInt。此外，我假设复合结构的所有子项本身都是BuiltValue，因此在重建阶段可变。 - DomJack

我明白了。你想要不可变的表达式树把我搞糊涂了。你并不总是需要不可变的表达式树，而是只需要不可变的结果。而且通过优化重建，你的意思是尽量减少“build()”调用。这听起来很合理，很高兴你找到了解决方案。 - Mike Fairhurst

谢谢你的提问 - 回答让我认识到了我不必要的限制 :)。 - DomJack

Answer 1

我给自己设置了不必要的限制。

虽然我最初认为所有构建器操作都应该改变实例化构建器而不返回任何内容，但如果一个人只需要这些操作返回构建器，那么问题就变得简单得多。下面是unarySimplify（Sum([x]) -> x的构建器等效）。

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

- DomJack