Persistent data structures

The efficiency of software depends very much on the way it organizes the data it manipulates into algorithmically efficient structures. Most data structures known today are transient : updates to the structure are made by modification in place, making the state of the structure before modification inaccessible. In contrast, persistent data structures retain the complete history of the data : everything happens as if an update recreates a new structure, independent of the previous one ; this can be achieved in a time- and memory-saving way, provided ingenious algorithms are used. These efficient persistent data structures play a crucial role in purely functional programming, where programs take the form of mathematical definitions that can be reasoned about equationally. The lecture will present the main persistent data structures known today, some implemented in a purely functional way and others using hidden imperative modifications, and will describe the general principles guiding the design of these persistent structures as well as their complexity analysis.