Easy persistent data structures in Rust

Summary:

• A persistent data structure can easily keep track of previous versions of itself with little overhead.
• A regular data structure can be converted into a persistent one by replacing instances of Box with Rc, and replacing mutable dereferences with Rc::make_mut.
• The resulting structure is both more performant and uses less memory if you plan on performing lots of clones.

What is a persistent data structure?

Data structures are persistent when they can keep track of all of their old states. Every time a modification is made, a new structure is created instead of modifying the original data. Persistent data structures are often referred to as immutable, because the original data is left untouched.

A naive persistent version of any data structure is trivial to make: Just clone the entire structure every time a change is made, and then commit the relevant changes to the new version. That way the old version is kept. However, for anything larger than a trivially small structure, this is going to be problematic.

There is a better way to create persistent data structures. Instead of copying the entire structure each time a modification is made, only the parts that have been modified need to be copied. The rest of the data is shared between old and new versions. This can be performed through the use of clone-on-write pointers.