functional-programming - 为什么持久展开树在函数式编程中特别有用？

Question

在Splay Trees Wikipedia 页面上，据说（在“优势”部分）：

可以创建 splay 树的持久数据结构版本——它允许在更新后访问先前版本和新版本。这在函数式编程中很有用，并且每次更新都需要分摊的 O(log n) 空间。

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

Answer 1

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

简而言之，您可能可以将这句话理解为“在仅使用不可变数据结构进行编程时创建持久展开树可能很有用”，这与重言式接壤。

Answer 2

现代函数式编程的驱动目标之一是更好地管理状态，最好尽可能少地使用它，因为有状态程序必须以正确的顺序仔细执行命令以避免错误。

持久性数据结构之所以伟大，正是因为它们不使用可变状态，允许它们用于纯粹和不可变的计算

//mutable tree
var t = new_tree();
add(t, 1);
add(t, 2);
//the tree has now changed so if anyone was depending on the old value
//we will now have a problem

//persistent tree
var t = new_tree();
var t2 = add(t, 1);
var t3 = add(t2, 2);
//t1 and t2 have not changed

您指出的引用只是强调持久数据结构在纯函数式编程中是常用的（并且是首选的）。在这种情况下，展开树没有什么特别之处。

Answer 3

我什至认为相反，展开树在函数式编程中使用起来不太舒服，因为即使在每次查找操作之后您也需要返回新树并跟踪几乎所有操作的最后一棵树。此外，我所知道的所有搜索树都可以直接在功能上使用，每次操作增加 O(log n) 空间。我想那句话中唯一有趣的事实是每个操作的内存需求保持 O(log n) 摊销，即使我们一直在重构树，但请注意，现在我们为搜索支付了空间价格。