Why are persistent splay trees particularly useful in functional programming?

Question

On the Splay Trees Wikipedia page it is said (in the Advantages section):

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.

Why is that? How is functional programming particulary making use of persistent Splay trees?

Answer 1

One of the driving goals of modern Functional Programming is a better management of state, preferrably using as little of it as necessary, since stateful programs must carefully execute the commands in the correct sequence to avoid errors.

Persistent data structures are great precisely because they do not use mutable state, allowing them to be used in pure and immutable computations

//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

The quote you pointed out is just emphasizing that persistent data structures are commonly used (and preferred) in pure functional programming. There is nothing particular about splay trees in this case.

Answer 2

Your question seems to come from a persistently unfortunate bit of terminological confusion. A better phrase might be purely functional, i.e., functional programming without destructive mutation. The confusion likely arises from the fact that immutable, persistent data structures are more common in functional programming as a whole, for a variety of reasons.

In short, you can probably read that phrase as "creating persistent splay trees can be useful when programming with only immutable data structures", which borders on the tautological.

Answer 3

I'd even argue the opposite, splay trees are less comfortable to work with in functional programming because you need to return the new tree even after every find operation and keep track of the last tree for almost all operations. Also, all the search trees I know of can be directly used functionally with O(log n) additional space per operation. I suppose the only interesting fact in that sentence of that the memory requirement per operation stays O(log n) amortized, even though we restructure the tree all the time, but notice that now we pay that space price even for searches.