That's not quite right. All immutable data structures are persistent, but not all persistent data structures strictly use immutability. Immutability is a commo

That's not quite right. All immutable data structures are persistent, but not all persistent data structures strictly use immutability. Immutability is a common way of achieving persistence, but fundamentally a persistent data structure simply preserves previous versions. This can be achieved through some mutability via things like fat nodes[1]. It turns out that when you use immutability, many other nice properties often fall out from that decision. You can absolutely insert and delete into an immutable data structure though. You'll simply get back a new structure. [1] http://en.wikipedia.org/wiki/Persistent_data_structure#Fat_Node http://en.wikipedia.org/wiki/Persistent_data_structure#Fat_N...