What is Persistent Data Structure?

“Persistent Data Structure” should be called “Data Structure by Copy”

1 xah's edu corner extempore, on persistent data structure

2 wouldn't it be nice, if your lang's array/list/hash/dictionary etc functions, all just return a copy instead?

3 what's wrong with references? you got the problem of shallow/deep copy, pass by value/ref, val of ref

4 basically, you can't be sure when you modified a list, some other list is modified too or not. diff language deal with this differently. very confusing.

• Python: Copy Nested List, Shallow/Deep Copy
• Python: dict={} vs dict.clear()
• JavaScript: Array Compare Equality
• JavaScript: Test Object Equality 🚀
• JavaScript: Clone Object

5 why didn't all langs just always do copy? cuz that's too slow. programer haven't been able to solve the problem in the past.

6 this is the primary reason, the concept of reference came into programer's brain. by-product of computer engineering, so to speak.

7 persistent data structure is about 2 things. (1) all functions return a copy. (2) implementation to make this very efficient.

8 all functions return a copy isn't new. Mathematica since 1990 does that, as well as almost all math/science languages such as APL.

9 all you need to know about persistent data structure is just all list functions always return a copy. nice n simple.

10 persistent data structure is rather new. popularized by clojure. JavaScript has immutable.js

[see Clojure Tutorial]

PostScript: the word “persistent” is a misnomer. It's better called “data structure by copy”.