Durable data structure

Durable data structure or purely functional data structure - a data structure that always retains its previous versions when modified. Such data structures are unchanging as the operations on them do not change the structure itself, but result in a new, updated version. A persistent data structure is not a data structure stored on a persistent data medium, such as a disk; This is another and unrelated meaning of the word "lasting."

The data structure is partially stable if all versions can be read, but only the latest version can be modified. The data structure is completely persistent if all versions can be read and modified. The data structure is confluently persistent if there is a hash or merge operation that can create a new version based on two previous versions. Structures that are not permanent are ephemeral.

These types of data structures are particularly common in logical and functional programming. In purely functional programming, all data is invariant, and thus data structures become fully automatic. Durable data structures can also be created by updating data in place, so they can be faster or take up less space than their purely functional counterparts.

Durability can be achieved by simple copying, but this is time-consuming and takes up too much space, because most operations only make minor changes to these data structures. A better way is to use the similarity between new and old versions to share structures between them, eg using the same subtree in the tree structure. Because of this, we quickly come to the situation that there are many older versions and it is then necessary to specify which parts of the shared structure are shared by these versions, so it is desirable to have a garbage collection management environment in place. Then you can easily get rid of older, unnecessary versions.

Perhaps the simplest persistent data structure is a unidirectional list, where each object (the link of this list) has a pointer to the next list object. This is a persistent structure because we can take the list tail, ie the last k objects and add new objects to the front of that tail. Then the tail will not be duplicated; It will be shared between the old and the new list. As long as the tail content remains unchanged, the sharing will be invisible to the program.

Many commonly used data structures based on pointers such as red-black trees and queues can easily be changed to persistent versions. For example, the equivalent of an array could be a VList, a data structure created in 2002 by Phil Bagwell. Bibliography

wiki