In the context 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?
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).
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."
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" 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.
This is a brief discussion of maintaining performance guarantees, as implemented in clojure by Rich Hickey
http://groups.google.com/group/clojure/msg/99d1cfcc3a9b520b
(he references Purely Functional Data Structures - Okasaki's book)