Which term to use when referring to functional data structures: persistent or immutable?

In the c开发者_Python百科ontext of functional programming which is the correct term to use: persistent or immutable? When I Google "immutable data structures" I get a Wikipedia link to an article on "Persistent data structure" which even goes on to say:

such data structures are effectively immutable

Which further confuses things for me. Do functional programs rely on persistent data structures or immutable data structures? Or are they always the same thing?

The proper term for functional data structures is immutable. The teerm "persistent" is used in at least three ways:

• A persistent data structure refers to the situation where you have an old data structure, you create a new one, but you keep a pointer to the old one. Typically the old one and new one share a lot of state—they may differ only by a constant number of heap objects or perhaps a linear number of heap data structures. This kind of persistence is a consequence of having immutable data structures, plus an algorithm that retains pointers to old versions of a data structure, allowing them to persist.

• A persistent variable is one whose value persists across multiple invocations of the same program. This can be done with language features or libraries.

• A persistent programming language is one that provides persistent variables. The holy grail is orthogonal persistence: a programmer can decide whether a variable is persistent, independent of all the other properties of that variable. At the moment, this kind of programming language is far-out research, but it's useful to preserve the terminological distinction.

I don't feel up to editing Wikipedia today :-(

A persistent data struture preserves only the previous version of itself after a change. Depending on the type of persistent data structure...you may or may not be able to modify previous versions.

An immutable type can not be changed at all.

Functional Languages primarily rely on Immutable types (also called values) for their data storage (even though you can use Mutable types in some...but it has to be done explicitly).

The article also says "in a purely functional program all data is immutable," which is true.

In my opinion you don't really need to make this distinction. If you're programming in a functional language or in a completely functional style -- as opposed to using functional idioms in imperative code where convenient -- then you can just say "data structure." By definition they will be immutable and persistent.

If you need to make the distinction for some reason, then "persistent" might be more appropriate for dynamic structures like trees and queues, where values appear to "change" based on execution traces, and "immutable" for simple value objects.

Immutable generally means "does not change". Persistent generally is taken to mean "stored on permanent storage medium". However, the Wikipedia article you mention seems to take the two words to mean very similar things (but not exact same). In fact it states:

A persistent data structure is not a data structure committed to persistent storage, such as a disk; this is a different and unrelated sense of the word "persistent."

"Immutable" is used far more often, as "persistent" is overloaded (normally it means "stored outside of and outliving the program") and even the correct definition carries additional semantic baggage that's often unrelated to the distinguishing quality of purely functional programming — the fact that there is no mutable state. A = A and always will for all values of A.

In this article, the authors use the word "persistent" as meaning "observationally immutable, although implemented with mutations under the hood". In that particular case, the mutations are hidden by the module system of a functional, but not pure, programming language.