Good question. The answer is no. Here's something I wrote elsewhere and have copied here: Immutability [in purely functional data structures] is an implementat

Good question. The answer is no. Here's something I wrote elsewhere and have copied here: Immutability [in purely functional data structures] 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: http://www.math.tau.ac.il/~haimk/papers/persistent-survey.ps http://www.math.tau.ac.il/~haimk/papers/persistent-survey.ps * "Making Data Structures Persistent" by Driscoll et al.: http://www.cs.cmu.edu/~sleator/papers/Persistence.htm http://www.cs.cmu.edu/~sleator/papers/Persistence.htm * The first lecture of the Spring 2012 incarnation of MIT's 6.851: Advanced Data Structures: http://courses.csail.mit.edu/6.851/spring12/lectures/L01.html http://courses.csail.mit.edu/6.851/spring12/lectures/L01.htm...