You would want a persistent data structure, such as persistent HAMT (as in clojure, scala and others) for associative map or a tree of subvectors for an append

You would want a persistent data structure, such as persistent HAMT (as in clojure, scala and others) for associative map or a tree of subvectors for an appendable ordered list. These allow most of the structure to be shared between typical mutated versions and allow value semantics as a bonus.