tl;dr summary: every persistent data structure is immutable, i.e. persistence is a subset of immutability, but not the other way around.
Note: the Wikipedia article is about the more general concept of persistent data structures, not limited to functional programming. You are asking specifically about the context of functional programming, though, where the term is used in a narrower sense, so I will restrict my answer to this narrower sense.
Immutability
Immutable means unchangeable, i.e. something which cannot be changed. I've never learned Latin, but I am reasonably sure that is quite literally the translation with im- being a negative prefix – think of immature, immaterial, etc. – and mutability meaning changeability – think of mutation.
The primary example of a data type that is immutable even in languages that otherwise fully embrace mutability is numbers. I can't name any language off the top of my head that would allow to mutate the state of a number such that, e.g. 1 + 1 suddenly equals 4.
An example of a more complex data structure that is immutable in some (but not all) languages, is strings. They are immutable in Java, C#, Python, and ECMAScript, all of which are languages which otherwise embrace mutability. They are mutable in Ruby, for example, although efforts are underway to restrict that mutability.
Immutability means that I cannot just "change" a sub-element of a complex data structure, such as an array. If I have an immutable array [1, 2, 3], I cannot change an element of the array so that I now have [1, 99, 3]. I have to copy the entire array with one element changed, so that I now have two arrays, I still have the original [1, 2, 3] and I also have the new [1, 99, 3].
This copying process is slow: every time I want to change one element, I need to copy the entire array, i.e. changing one element has a worst-case step complexity of θ(length of the array).
This is where Persistence comes in:
Persistence
An informal definition of a persistent data structure is a data structure that is BOTH
- immutable AND
- has "efficient operations".
Now, I don't want to go into too much detail of what we mean by "efficient operations", but I want to motivate it with an example. Let's look at dynamic arrays.
Example: dynamic arrays
Dynamic arrays are arrays which can change their size, i.e. you can add and remove elements. Many collections libraries have dynamic arrays, both mutable (e.g. Python's list, Ruby's Array, Java's ArrayList, .NET's ArrayList) and immutable (e.g. Clojure's Vector, Scala's Vector).
Mutable dynamic arrays
… naïve implementation
A simple and naïve implementation of mutable dynamic arrays is to allocate a new array of size n+1 and copy all the existing elements over every time you append an element. This gives you a worst-case step complexity of θ(1) for indexing and mutation of an element, just like a mutable non-resizable array, and it gives you θ(length of the array) appending, which is an operation a static array cannot do.
… the clever implementation
However, we can do better by using geometric resizing. Instead of just adding one storage place when we append one element, we add c × n storage places (i.e. a constant multiplier of the current size) whenever we run out of storage. A popular textbook choice is c = 2, i.e. doubling the array in size whenever it gets full, although smaller constants are sometimes preferable.
This still has the same worst-case step complexity as we had before, since we still need to copy the entire array in the worst case.
However, the amortized worst-case step complexity is much better: it is θ(1) for appending. Dynamic arrays are the standard introductory example for amortized analysis, so I will not repeat the proof here as you can find it readily online or in any textbook. Just to give you an intuition, though, the fundamental "trick" is that the "worst-case" of needing to copy all θ(n) elements only happens every θ(n) operations, so if you amortize this worst-case "cost" over many successive appends, each append on average only takes θ(1).
Immutable dynamic arrays
… naïve implementation
The naïve implementation of immutable dynamic arrays is that we copy the array for every "mutating" operation. This means that almost all operations, i.e. append, pop (delete last element), insert in the middle, delete from the middle, and mutate (change an element at a fixed index) are θ(n), only indexing is θ(1).
This is similar to the naïve mutable dynamic array, except that the naïve mutable array has θ(1) mutation of an element.
So, this is clearly an undesirable implementation. Can we get an implementation that is closer to the performance of the "clever" mutable dynamic array implementation but still immutable?
… implementation based on difference
One idea for implementing immutable data structures efficiently is to only record the difference to the previous version instead of copying the whole thing. So, for example, when inserting an element into the array, instead of copying the whole array, we create a special "array proxy" that behaves externally just like an array, but internally, it contains a reference to the previous array and a description of the difference, e.g. "at index i, insert value 42, shift all later indices by 1".
However, this means that the operations get slower the longer you use the data structure, as the list of differences gets longer and longer and ever more complex. Everybody who has ever used a version control system that is based on storing a forward chain of patches knows that checking out a file takes longer and longer the older the project is, because in order to reconstruct the current state of the file, all patches have to be applied one-by-one from the original version.
We can implement a scheme similar to the clever dynamic mutable array, where we "collapse" the differences into a new array when they reach a certain size or complexity. However, that still means that we have different performance characteristics for what looks like the same array, depending on how it was constructed. For example, if I construct a new array directly as [1, 2, 3, 4, 5], it will have faster operations than if I start with an empty array [], then append 1, then append 2, and so on, even though the result should behave the same.
This is what persistent data structures are about: they are immutable and they are efficient, and this efficiency applies regardless of how many "version changes" there have been.
The solution to our problem is structural sharing.
… efficient implementation exploiting structural sharing
Aside: CONS lists
The simplest example of a data structure exploiting structural sharing is the CONS list. The CONS list is built like this:
- We have special object which is the empty list (often called
() or NIL).
- A list is either the empty list or a pair of references
<head, tail> where head points to the first element of the list and tail points to the rest of the list.
Here is a (runnable) example in Scala:
sealed trait MyList[+A]:
@throws(classOf[NotImplementedError]) def head: A
def tail: MyList[A]
override def toString: String
case object MyNil extends MyList[Nothing]:
@throws(classOf[NotImplementedError]) override def head = ???
override val tail = this
override val toString = "()"
case class MyCons[+A](val head: A, override val tail: MyList[A]) extends MyList[A]:
override val toString = s"($head, $tail)"
val list1 = MyCons(4, MyCons(5, MyNil))
val list2 = MyCons(1, MyCons(2, MyCons(3, list1)))
val second = list2.tail.head
list1.toString //=> (4, (5, ()))
list2.toString //=> (1, (2, (3, (4, (5, ())))))
second //=> 2
As you can see, we were able to efficiently construct a new list (list2) based on an existing list (list1), by the fact that list1 and list2 share their structure. (In fact, in this simple example, list1 is fully contained within list2.) Even though the two lists share their structure, everybody who has a reference to the head of list1 can still independently use it without even having to know about list2 and vice versa.
This gives us θ(1) prepending of a new element at the head. If we want to insert, delete, or "mutate" an element in the middle, we only need to copy the path from the head up to the mutation point, but we can still share the tail with the previous version.
This kind of structural sharing is used by many widely-used persistent data structure implementations.
Generalizing lists to trees
In particular, many persistent data structure implementations are based on trees. I started with the list first, because I found it easier to understand how structural sharing and path copying works in lists and then generalize this understanding to trees. After all, you can think of a list as a degenerate tree where each node has only a single child. Conversely, once you understand how CONS lists work, how they share their structure, and how path copying works, you can sort-of imagine a persistent tree as a CONS list with more than one head value and more than one tail.
And that is exactly how typical persistent dynamic arrays are implemented: as trees.
You probably have learned about trees already. The vast majority of trees that are taught are binary trees where each node has two children. And you can build a dynamic array this way. You can think of a dynamic array as a binary search tree where the array index is the search key.
Just like with the CONS list example, a newer version and an older version can share a sub-structure. In the case of the CONS list, that was a list tail, in the case of a tree, that will be a sub-tree. And just like with the CONS list, when you make a change in the middle of the tree, you only need to copy the path from the root to the location of the change, but not the entire tree. The rest of the tree structure can still be shared!
In reality, persistent dynamic arrays don't use binary trees, they use much wider, much shallower trees where the tree nodes are themselves immutable arrays. This improves cache locality, i.e. multiple consecutive elements of the "tree array" are actually implemented as multiple consecutive elements of the internal immutable array (which is an actual array, i.e. a contiguous region of memory). It also reduces the number of "steps" you need to take until you find the value.
For example, Clojure's Vector uses a 32-ary tree, i.e. each node is an array of size 32. That means it takes at most log32(n) steps to go from the root to the leaf of an array with n values. While this is still, technically θ(log n) for indexing, in reality, log32 grows very slow and is almost indistinguishable from O(1) even for billions of elements.
This is an example where constants do matter! Rich Hickey, the creator of Clojure, likes to say that Clojure's Vectors are "θ(log32 n)", where the 32 is not irrelevant. Just as an example: Arrays and mutable ArrayLists in Java can only have a maximum of 2,147,483,647 elements. log32(2147483647) is slightly less than 6.2, meaning it will take a maximum of 7 pointer dereferences plus one array access to find a value in a Clojure Vector as opposed to one pointer dereference and one array access in a Java ArrayList.
Which means that not only is our dynamic array immutable and persistent with preservation of old versions and efficient operations regardless of number of versions, but it is even almost as efficient as its mutable counterpart.
Conclusion
So, in conclusion, the difference between an immutable data structure and a persistent data structure in functional programming is that persistent data structures are immutable with additional restrictions, namely:
- Efficient operations AND
- Preservation of old versions
Where efficient operations applies both to new and old versions.
Often, they are also "efficient" compared to their mutable counterparts.
Further reading
As mentioned in Karl Bielefeldt's answer, Prof. Chris Okasaki, Ph.D.'s book Purely Functional Data Structures, based on his Ph.D. thesis of the same name is the definitive work on immutable and persistent data structures.
However, there have been some improvements since then. Phil Bagwell created the Hash Array Mapped Trie (HAMT). Rich Hickey used HAMTs in Clojure with some tweaks. Phil Bagwell then improved on those tweaks when he helped re-write the collections library in Scala 2.8.
There is a big list question on the sister site cstheory.se titled What's new in purely functional data structures since Okasaki? which has links to a lot of interesting stuff.
Functional programming
Please note that everything I wrote above only applies within the context of functional-programming.
In the Wikipedia article, a distinction is made between fully persistent and partially persistent:
In the partial persistence model, a programmer may query any previous version of a data structure, but may only update the latest version. This implies a linear ordering among each version of the data structure. In the fully persistent model, both updates and queries are allowed on any version of the data structure.
In functional programming, we only care about the fully persistent model. The distinction between versions that can be updated and ones which can't doesn't make sense for the way we use persistent data structures in FP. In FP, we use persistent data structures as immutable data structures with efficient operations. We don't consider them to be "versions", they are all just values that we want to manipulate.
The Wikipedia article continues:
In some cases the performance characteristics of querying or updating older versions of a data structure may be allowed to degrade […]
Again, when we talk about persistent data structures in the context of functional programming, we do not allow this.
Regarding this statement in your question:
My current understandings are that every persistent data structure is immutable and vice versa.
Neither of those two things is true in general.
Only within the context of functional programming is the first statement true: every persistent data structure is an immutable data structure. (Although that is trivially true in functional programming, as everything is immutable.)
In functional programming, a persistent data structure is a special kind of immutable data structure with efficient operations.
The general concept of persistent data structures, though, is broader then immutable data structures.
Red herring: persistent storage
To add to the confusion, the term persistence can have another, very different, meaning.
The term persistence is also used in the context of persistent storage. Here, it means data storage which outlives the lifetime of the process which created the data.
A typical example of persistent storage would be a hard disk. The antonym here would be something like "volatile".
While there is some relationship in the etymology of those two terms, the concepts are completely different and from distinct sub-fields.
Note that the tag persistence you used on your question refers to this kind of persistence, not the functional-programming kind, which seems to have caused some confusion among answerers and commenters.
