Clojure: immutability and perseverance

Question

Each tutorial says that Clojure's data structures are "immutable and constant." They go differently, explaining the concept, but so far I have not been able to figure out what is the difference between immutability and perseverance. Is the object persistent but volatile? or unchanging, but not persistent?

Answer 1

Immutability means that the value cannot be changed, and constancy means that the path to the value is copied if the value already exists in the program. Clojure uses this as part of a structural exchange implementation. If data does not exist, it is created. If data exists, new data is built on the old version of the data without modification or deletion.

Atoms are stable, but safely mutable.

user> (def +a+ (atom 0)) #'user/+a+ user> @+a+ 0 user> (swap! +a+ inc) 1 user> @+a+ 1 

Transients are mutable, but must be stable after mutation

 user> (def t (transient [])) #'user/t user> (conj! t 1) #<TransientVector clojure.lang.PersistentVector$TransientVector@658ee462 > user> (persistent! t) [1] 

Understanding Clojure Resistant Vectors, pt. 1 => http://hypirion.com/musings/understanding-persistent-vector-pt-1

Persistent data structure => https://en.wikipedia.org/wiki/Persistent_data_structure

Persistent data structures and managed links => http://www.infoq.com/presentations/Value-Identity-State-Rich-Hickey

Answer 2

The purely functional data structures of Chris Okasaki refer to an article [1] that appears to contain an initial definition of the term persistent:

Regular data structures are ephemeral in the sense that making changes to the structure destroys the old version, leaving only the new one .... We call a data structure persistent if it supports access to multiple versions. The structure is partially permanent if all versions are available, but only a new version can be changed and completely constant if each version can be accessed and modified.

[1] James R. Driscoll, Neil Sarnak, Daniel D. Slattor and Robert E. Tarjan. Continuous creation of data structures. Journal of Computer and System Sciences, 38 (1): 86-124, February 1989

Answer 3

Immutable implies constancy, but resilience does not mean immutable. That way you could have something permanent, but not constant.

An example of a mutable and persistent data structure is the Java CopyOnWriteArrayList .

Persistence does not imply a shared structure and does not say anything about performance. Of course, overall structure and good performance are highly desirable and both are provided by Clojure's persistent data structures. But it would be entirely possible to create something that did not share structure and terrible performance (see CopyOnWriteArrayList , for example ;-)), but still persisted.

Answer 4

In principle, immutable == cannot be changed, and constant == immutable, with a common structure.

If I have a language in which arrays cannot be changed, the arrays are immutable. To “modify” an array, I have to create a new array and copy each element (except for one (s) that need to be changed) into a new array. This makes any update O (n), where n is the number of elements in the array. Obviously, this is ineffective for large n.

On the other hand, if I use a constant data structure instead of an array, instead of copying each item every time the data structure is “changed”, the new version has most of the same structure with the old.

Details are structure dependent, but wood is often used. If the tree is balanced, replacing the element means creating new copies of the nodes along the path from the root to the sheet containing the element. The remaining nodes are shared with the original version. The length of this path is O (n log (n)). Since the nodes are O (1) in size, the whole operation takes O (n log (n)) time and extra space.

Note that not all permanent structures effectively support the same operations. For example, in Clojure, lists are lists that are related to each other. You can effectively add and remove items to / from the front, but more on that. On the other hand, vectors allow you to efficiently receive any element and add / remove elements on the rear panel.