persistent vs immutable data structure

Question

Is there any difference in a persistent and immutable data structure? Wikipedia refers to immutable data structure when discussing persistence but I have a feeling there might be a subtle difference between the two.

Kazim

Answer 1

Immutability is an implementation technique. Among other things, it provides persistence, which is an interface. The persistence API is something like:

• version update(operation o, version v) performs operation o on version v, returning a new version. If the data structure is immutable, the new version is a new structure (that may share immutable parts of the old structure). If the data structure isn't immutable, the returned version might just be a version number. The version v remains a valid version, and it shouldn't change in any observe-able way because of this update - the update is only visible in the returned version, not in v.
• data observe(query q, version v) observes a data structure at version v without changing it or creating a new version.

For more about these differences, see:

• The chapter "Persistent data structures" by Haim Kaplan in Handbook on Data Structures and Applications
• "Making Data Structures Persistent" by Driscoll et al.
• The first lecture of the Spring 2012 incarnation of MIT's 6.851: Advanced Data Structures

Deplume

If you have a fully persistent data structure map, and you have already set (1, 1), if you set (1, 1) again, is this considered a mutation, and should you return a new version of the data structure, even if nothing has really changed? – Stuffed

@CMCDragonkai, I don't think there is a single "right" answer to that question. – Deplume

Answer 2

Yes, there is a difference. An immutable data structure cannot be modified in any way after its creation. The only way to effective modify it would be to make a mutable copy or something similar (e.g. slightly modifying the parameters you pass to the constructor of the new one). A persistent data structure, on the other hand, is mutable in the sense that the exposed API appears to allow changes to the data structure. In truth, though, any changes will retain a pointer to the existing data structure (and therefore every preceding structure); they only seem to mutate the data structure because the exposed API returns a new pointer that may include pointers to a subset of the previous data structure (in trees, e.g., we will point at the node whose subtree hasn't changed as a result of the operation).

Aberdare