These things are usually called "persistent" versions of the thing, e.g. persistent Dictionary. Sometimes "immutably persistent" to distinguish it from the "durable" meaning of persistence i.e. written to disk.
It seems odd to me to call a data structure "persistent" when its purpose is to allow you to cheaply keep many similar transitory copies around until you throw them away.
The specific application was using dynamic programming to build up a complex data structure. You wind up with many copies of very similar data structures, and doing a deep copy each time is prohibitively expensive.
There is a key difference between that, and what I created.
The difference is that persistent data structures allow you to traverse the history of the data structure to find past versions. By contrast I only allowed you to see the current version, returning a new version of the root any time you made a modification. As a result, the memory associated with the old version could be freed once nothing would want to access it again. And any version that you had could still be manipulated.
For the example that I was dealing with, both made sense. On top of that it made it possible to create a hashable version of the data structure that had a good chance (not a guarantee) of matching hashes when you arrived at the same data structure through different histories.
the data structures people normally call 'persistent' behave like what you implemented; they're ubiquitous in languages like clojure, haskell, and even ocaml that privilege immutability. the map module in ocaml's standard library is an example, and so is almost everything built in to clojure. 'traverse the history of the data structure to find past versions' is not how these persistent data structures normally work
there is an unfortunate terminology clash with 'persistent' in the sense of 'not vanishing after a power cycle', so i typically use the term 'fp-persistent', because this sense of 'persistent' is associated with functional programming. this has the disadvantage that it's a term i made up, so nobody knows what i mean until i explain it
The difference is that persistent data structures allow you to traverse the history of the data structure to find past versions.
That capabilities is not a required property of persisten datastructures.
The copy on write and collect the unique parts when a root is freed semantic that you describe is exactly the common behaviour of persistent data-structures in the wild.
Libraries like Rusts "im", even do some nifty optimisations where they combine the borrow checker with reference counting to only perform copy on write when the reference you have is non-unique.
So based on your description you build a path-copying persistent data-structure.
Well, the difference isn't that great. You wrote: “the memory associated with the old version could be freed once nothing would want to access it again.” So all it really takes is something wanting.
