Comparison
ImmutabilityvsPersistent data structure
Immutability
nothing that was handed out can be changed, so you stopped copying defensively and stopped worrying about who else holds it.
Building values that cannot change after construction, so a change produces a new value instead. It removes aliasing bugs, makes equality and hashing safe, makes objects shareable across threads without locks, and makes change detection a reference comparison. The costs are allocation and awkwardness in the places where a large structure genuinely does change often, which is what persistent data structures address.
Full entry →Persistent data structure
you added an item and got a new list back, and the old one is still there and still valid.
A structure that preserves its previous versions when modified, so every update yields a new value and the old one remains usable. The naive implementation copies everything and is unusable at scale; real ones share the unchanged parts, which is what makes immutability affordable. It is what underpins undo stacks, time-travel debugging and the change detection in several frontend frameworks.
Full entry →