Persistent data structure: Difference between revisions

Revision as of 13:36, 20 June 2025

Revision as of 13:52, 20 June 2025

Line 101:

==Examples of persistent data structures==

[[Purely functional data structure]] are automatically persistent.

Perhaps the simplest persistent data structure is the [[Linked list|singly linked list]] or ''cons''-based list, a simple list of objects formed by each carrying a [[reference]] to the next in the list. This is persistent because the ''tail'' of the list can be taken, meaning the last ''k'' items for some ''k'', and new nodes can be added in front of it. The tail will not be duplicated, instead becoming shared between both the old list and the new list. So long as the contents of the tail are immutable, this sharing will be invisible to the program.

Many common reference-based data structures, such as [[red–black tree]]s,<ref name="sarnak2">{{cite journal |author=Neil Sarnak |author2=Robert E. Tarjan |year=1986 |title=Planar Point Location Using Persistent Search Trees |url=http://www.link.cs.cmu.edu/15859-f07/papers/point-___location.pdf |journal=Communications of the ACM |volume=29 |issue=7 |pages=669–679 |doi=10.1145/6138.6151 |s2cid=8745316 |author2-link=Robert Tarjan |access-date=2011-04-06 |archive-url=https://web.archive.org/web/20151010204956/http://www.link.cs.cmu.edu/15859-f07/papers/point-___location.pdf |archive-date=2015-10-10 |url-status=dead }}</ref> [[Stack (data structure)|stacks]],<ref name="okasaki2">{{Cite journal|author=Chris Okasaki|title=Purely Functional Data Structures (thesis)|url=https://www.cs.cmu.edu/~rwh/theses/okasaki.pdf}}</ref> and [[treap]]s,<ref>{{cite journal |last=Liljenzin |first=Olle |title=Confluently Persistent Sets and Maps|arxiv=1301.3388|bibcode=2013arXiv1301.3388L|year=2013 }}</ref> can easily be adapted to create a persistent version. Some others need slightly more effort, for example: [[Queue (data structure)|queues]], [[Double-ended queue|dequeues]], and extensions including [[min-deque]]s (which have an additional ''O''(1) operation ''min'' returning the minimal element) and [[random access deque]]s (which have an additional operation of random access with sub-linear, most often logarithmic, complexity).

Persistent data strctures which are based on immutable ("pure functional") structures should be constrasted with structures that used destructive updates (mutation) and are made persistent using the fat node or path copying techniques, described above.

There also exist persistent data structures which use destructive{{clarify|date=June 2013}} operations, making them impossible to implement efficiently in purely functional languages (like Haskell outside specialized monads like state or IO), but possible in languages like C or Java. These types of data structures can often be avoided with a different design. One primary advantage to using purely persistent data structures is that they often behave better in multi-threaded environments.

===Linked lists===

Line 151 ⟶ 152:

Notice two points: first, the original tree (<code>xs</code>) persists. Second, many common nodes are shared between the old tree and the new tree. Such persistence and sharing is difficult to manage without some form of [[Garbage collection (computer science)|garbage collection]] (GC) to automatically free up nodes which have no live references, and this is why GC is a feature commonly found in [[Functional programming|functional programming languages]].

==== Code ====

GitHub repo containing implementations of persistent BSTs using Fat Nodes, Copy-on-Write, and Path Copying Techniques.

To use the persistent BST implementations, simply clone the repository and follow the instructions provided in the README file.<ref>{{github|DesaultierMAKK/PersistentBST}}</ref>

=== Persistent hash array mapped trie ===