functional-programming - 为什么持久伸展树(Splay Tree)在函数式编程中特别有用？

Question

关于Splay Trees Wikipedia page据说(在优点部分):

Possibility of creating a persistent data structure version of splay trees—which allows access to both the previous and new versions after an update. This can be useful in functional programming, and requires amortized O(log n) space per update.

这是为什么？函数式编程如何特别使用持久的 Splay 树？

Answer 1

你的问题似乎来自一个持续不幸的术语混淆。更好的短语可能是 纯功能 ，即没有破坏性突变的函数式编程。混淆可能源于这样一个事实，即出于各种原因，不可变的、持久的数据结构在整个函数式编程中更为常见。

简而言之，您可能会将这句话理解为“在仅使用不可变数据结构进行编程时，创建持久的展开树会很有用”，这接近于同义反复。