为什么持久的splay树在函数式编程中特别有用？

Question

在Splay Trees Wikipedia页面上(据优势部分)说:

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

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

Answer 1

你的问题似乎来自持续不幸的术语混淆.一个更好的短语可能纯粹是功能性的,即没有破坏性突变的函数式编程.由于各种原因,不可变的持久数据结构在整个函数式编程中更常见,这可能引起混淆.

简而言之,您可以将该短语读作"在仅使用不可变数据结构进行编程时创建持久的splay树可能很有用",这与重言式相关.

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

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