functional-programmingbinary-treetheorysplay-tree

Why are persistent splay trees particularly useful in functional programming?


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?


Solution

  • 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.