[Solved]: What classes of data structures can be made persistent?

Positive result: persistence does not cost too much. One can show that every data structure can be made fully persistent with at most a $O(lg n)$ slowdown. Proof: You can take an array and make it persistent using standard data structures (e.g., a balanced binary tree; see the end of this answer for a bit more detail). This incurs a $O(lg n)$ slowdown: each array access takes $O(lg n)$ time with the persistent data structure, instead of $O(1)$ time for the non-persistent array. Now take any imperative algorithm whose running time in the RAM model is $O(f(n))$, where $n$ denotes the amount of memory used. Represent all of memory as one big array (with $n$ elements), and make it persistent using a persistent map. Each step of the imperative algorithm incurs at most a $O(lg n)$ slowdown, so the total running time is $O(f(n) lg n)$. Apparently it is possible to do a bit better: apparently one can reduce the slowdown factor to $O(lg lg n)$ (expected, amortized time), using the techniques in the Demaine paper cited below — but I am not familiar with the details of that work, so I cannot vouch for this myself. Thanks to jbapple for this observation. Negative result: you cannot avoid some slowdown, for some data structures. To answer your third question, there exist data structures where it is known that making them persistence introduces some slowdown. In particular, consider an array of $n$ elements. Without persistence, each array access takes $O(1)$ time (in the RAM model). With persistence, it has apparently been shown that there is no way to build a persistent array with $O(1)$ worst-case complexity for accessing a random element. In particular, there is apparently a lower bound showing that fully persistent arrays must have $Omega(lg lg n)$ access time. This lower bound is asserted on p.3 of the following paper:

• Confluently Persistent Tries for Efficient Version Control. Erik D. Demaine, Stefan Langerman, Eric Price. Algorithmica, volume 57, number 3, 2010, pages 462–483.

The lower bound is attributed to Mihai Patrascu, but there is no citation to a source that gives the details of the proof of this asserted lower bound. A rich area of research. If we take an arbitrary data structure or algorithm, it’s a bit of a delicate question whether you can make it persistent with at most $O(1)$ slowdown or not. I don’t know of any general classification theorem. However, there is a lot of research into ways to make specific data structures persistent, in an efficient way. There is also a strong connection with functional programming languages. In particular, every data structure that can be implemented in a purely functional way (with no mutations) is already a persistent data structure. (The converse is not necessarily the case, alas.) If you want to squint your eyes, you could take this as some weak sort of partial classification theorem: if it is implementable in a purely functional programming language with the same time bounds as in an imperative language, then there is a persistent data structure with the same time bounds as the non-persistent one. I realize this probably isn’t what you were looking for — it is mostly just a trivial re-phrasing of the situation. How to make a persistent array. I won’t try to describe the construction for how to build a fully persistent array with $O(lg n)$ worst-case access time. However, the basic ideas are not too complicated, so I’ll summarize the essence of the ideas. The basic idea is that we can take any binary tree data structure, and make it persistent using a technique called path copying. Let’s say we have a binary tree, and we want to modify the value in some leaf $ell$. However, for persistence, we don’t dare modify the value in that leaf in place. Instead, we make a copy of that leaf, and modify the value in the copy. Then, we make a copy of its parent, and change the appropriate child pointer in the copy to point to the new leaf. Continue in this way, cloning each node on the path from the root to the leaf. If we want to modify a leaf at depth $d$, this requires copying $d$ nodes. If we have a balanced binary tree has $n$ nodes, then all leaves have depth $O(lg n)$, so this operation on the binary tree takes $O(lg n)$ time. There are some details I’m skipping — to achieve $O(lg n)$ worst-case time, we may need to rebalance the tree to ensure it remains balanced — but this gives the gist of it. You can find more explanations, with pretty pictures, at the following resources:

• Read the sections labelled “Binary search trees” and “Random-access structures” (specifically, the tree method) at http://toves.org/books/persist/index.html.
• Or, read http://netcode.ru/dotnet/?artID=6592#BinaryTrees and some of the subsequent sections.
• Or, read the sections labelled “Functional data structures” and “Path copying” (starting on p.4) of the Demaine paper cited above: http://erikdemaine.org/papers/ConfluentTries_Algorithmica/paper.pdf

That will give you the main idea. There are extra details to take care of, but the details are out of scope for this question. Fortunately, this is all standard stuff, and there is lots of information available in the literature on how to build such data structures. Feel free to ask a separate question if the above resources aren’t enough and you want more information about the details of building a persistent array data structure.