Editing Persistent data structure (section)

== Usage in programming languages ==

=== Haskell ===
Haskell is a [[pure functional language]] and therefore does not allow for mutation. Therefore, all data structures in the language are persistent, as it is impossible to not preserve the previous state of a data structure with functional semantics.<ref>{{Cite web|url=https://www.haskell.org/|title=Haskell Language|website=www.haskell.org|access-date=2018-10-22}}</ref> This is because any change to a data structure that would render previous versions of a data structure invalid would violate [[referential transparency]].

In its standard library Haskell has efficient persistent implementations for linked lists,<ref>{{Cite web|url=http://hackage.haskell.org/package/base-4.12.0.0/docs/Data-List.html|title=Data.List|website=hackage.haskell.org|access-date=2018-10-23}}</ref> Maps (implemented as size balanced trees),<ref>{{Cite web|url=http://hackage.haskell.org/package/containers-0.6.0.1/docs/Data-Map-Strict.html|title=Data.Map.Strict|website=hackage.haskell.org|access-date=2018-10-23}}</ref> and Sets<ref>{{Cite web|url=http://hackage.haskell.org/package/containers-0.6.0.1/docs/Data-Set.html|title=Data.Set|website=hackage.haskell.org|access-date=2018-10-23}}</ref> among others.<ref>{{Cite web|url=https://wiki.haskell.org/Performance/Arrays|title=Performance/Arrays - HaskellWiki|website=wiki.haskell.org|language=en|access-date=2018-10-23}}</ref>

=== Clojure ===
Like many programming languages in the [[Lisp (programming language)|Lisp]] family, Clojure contains an implementation of a linked list, but unlike other dialects its implementation of a linked list has enforced persistence instead of being persistent by convention.<ref>{{Cite web|url=https://clojure.org/reference/lisps|title=Clojure - Differences with other Lisps|website=clojure.org|access-date=2018-10-23}}</ref> Clojure also has efficient implementations of persistent vectors, maps, and sets based on persistent hash array mapped tries. These data structures implement the mandatory read-only parts of the [[Java collections framework]].<ref>{{Cite web|url=https://clojure.org/reference/data_structures|title=Clojure - Data Structures|website=clojure.org|access-date=2018-10-23}}</ref>

The designers of the Clojure language advocate the use of persistent data structures over mutable data structures because they have [[value semantics]] which gives the benefit of making them freely shareable between threads with cheap aliases, easy to fabricate, and language independent.<ref>{{Cite web|url=https://www.infoq.com/presentations/Value-Values|title=Keynote: The Value of Values|website=InfoQ|access-date=2018-10-23}}</ref>

These data structures form the basis of Clojure's support for [[parallel computing]] since they allow for easy retries of operations to sidestep [[data race]]s and atomic [[Compare-and-swap|compare and swap]] semantics.<ref>{{Cite web|url=https://clojure.org/reference/atoms|title=Clojure - Atoms|website=clojure.org|access-date=2018-11-30}}</ref>

=== Elm ===
The [[Elm (programming language)|Elm programming language]] is purely functional like Haskell, which makes all of its data structures persistent by necessity. It contains persistent implementations of linked lists as well as persistent arrays, dictionaries, and sets.<ref>{{Cite web|url=https://package.elm-lang.org/packages/elm/core/latest/|title=core 1.0.0|website=package.elm-lang.org|access-date=2018-10-23}}</ref>

Elm uses a custom [[Document Object Model|virtual DOM]] implementation that takes advantage of the persistent nature of Elm data. As of 2016 it was reported by the developers of Elm that this virtual DOM allows the Elm language to render HTML faster than the popular [[JavaScript]] frameworks [[React (JavaScript library)|React]], [[Ember.js|Ember]], and [[Angular (application platform)|Angular]].<ref>{{Cite web|url=https://elm-lang.org/blog/blazing-fast-html-round-two|title=blog/blazing-fast-html-round-two|website=elm-lang.org|access-date=2018-10-23}}</ref>

=== Java ===
The [[Java (programming language)|Java programming language]] is not particularly functional. Despite this, the core JDK package java.util.concurrent includes CopyOnWriteArrayList and CopyOnWriteArraySet which are persistent structures, implemented using copy-on-write techniques. The usual concurrent map implementation in Java, ConcurrentHashMap, is not persistent, however. Fully persistent collections are available in third-party libraries,<ref>{{Cite web|url=https://github.com/sigbla/sigbla-pds/|title=Persistent (immutable) collections for Java and Kotlin|website=github.com|access-date=2023-12-13}}</ref> or other JVM languages.

=== JavaScript ===
{{Confusing section|date=May 2021}}

The popular JavaScript frontend framework [[React (JavaScript library)|React]] is frequently used along with a state management system that implements the [[Flux architecture]],<ref>{{Cite web|url=https://facebook.github.io/flux/|title=Flux {{!}} Application Architecture for Building User Interfaces|website=facebook.github.io|access-date=2018-10-23}}</ref><ref>{{Cite web|url=https://medium.com/react-ecosystem/how-to-handle-state-in-react-6f2d3cd73a0c|title=How to handle state in React.|last=Mora|first=Osmel|date=2016-07-18|website=React Ecosystem|access-date=2018-10-23}}</ref> a popular implementation of which is the JavaScript library [[Redux (JavaScript library)|Redux]]. The Redux library is inspired by the state management pattern used in the Elm programming language, meaning that it mandates that users treat all data as persistent.<ref>{{Cite web|url=https://redux.js.org/|title=Read Me - Redux|website=redux.js.org|access-date=2018-10-23}}</ref> As a result, the Redux project recommends that in certain cases users make use of libraries for enforced and efficient persistent data structures. This reportedly allows for greater performance than when comparing or making copies of regular JavaScript objects.<ref name=":0">{{Cite web|url=https://redux.js.org/faq/immutabledata|title=Immutable Data - Redux|website=redux.js.org|access-date=2018-10-23}}</ref>

One such library of persistent data structures Immutable.js is based on the data structures made available and popularized by Clojure and Scala.<ref>{{Cite web|url=https://facebook.github.io/immutable-js/|title=Immutable.js|website=facebook.github.io|access-date=2018-10-23|archive-url=https://web.archive.org/web/20150809185757/http://facebook.github.io/immutable-js/|archive-date=2015-08-09|url-status=dead}}</ref> It is mentioned by the documentation of Redux as being one of the possible libraries that can provide enforced immutability.<ref name=":0" /> Mori.js brings data structures similar to those in Clojure to JavaScript.<ref>{{Cite web|url=https://swannodette.github.io/mori/|title = Mori}}</ref> Immer.js brings an interesting approach where one "creates the next immutable state by mutating the current one".
<ref>{{Cite web|url=https://github.com/immerjs/immer|title = Immer| website=[[GitHub]] |date = 26 October 2021}}</ref> Immer.js uses native JavaScript objects and not efficient persistent data structures and it might cause performance issues when data size is big.

=== Prolog ===
Prolog terms are naturally immutable and therefore data structures are typically persistent data structures. Their performance depends on sharing and garbage collection offered by the Prolog system.<ref>{{Citation|title= The Implementation of Prolog - Patrice Boizumault|date=1993|isbn=9780691637709|url=https://press.princeton.edu/books/hardcover/9780691637709/the-implementation-of-prolog|last1=Djamboulian|first1=Ara M.|last2=Boizumault|first2=Patrice|publisher=Princeton University Press }}</ref> Extensions to non-ground Prolog terms are not always feasible because of search space explosion. Delayed goals might mitigate the problem.

Some Prolog systems nevertheless do provide destructive operations like setarg/3, which might come in different flavors, with/without copying and with/without backtracking of the state change. There are cases where setarg/3 is used to the good of providing a new declarative layer, like a constraint solver.<ref>{{Citation|title=The Use of Mercury for the Implementation of a Finite Domain Solver - Henk Vandecasteele, Bart Demoen, Joachim Van Der Auwera|date=1999|url=https://lirias.kuleuven.be/retrieve/440562}}</ref>

=== Scala ===
The Scala programming language promotes the use of persistent data structures for implementing programs using "Object-Functional Style".<ref>{{Cite news|url=https://blog.codecentric.de/en/2015/08/essence-of-object-functional-programming-practical-potential-of-scala/|title=The Essence of Object-Functional Programming and the Practical Potential of Scala - codecentric AG Blog|date=2015-08-31|work=codecentric AG Blog|access-date=2018-10-23|language=en-US}}</ref> Scala contains implementations of many persistent data structures including linked lists, [[red–black tree]]s, as well as persistent hash array mapped tries as introduced in Clojure.<ref>{{Citation|last=ClojureTV|title=Extreme Cleverness: Functional Data Structures in Scala - Daniel Spiewak|date=2013-01-07|url=https://www.youtube.com/watch?v=pNhBQJN44YQ|access-date=2018-10-23}}{{cbignore}}{{Dead YouTube link|date=February 2022}}</ref>