How do you develop a persistent (i.e. purely functional) version of them?
On the "purely functional" end, any stochastic algorithm is by definition not pure in the "referentially transparent" sense, so that's right out, and building a PRNG into the data structure is probably suboptimal.
As far as persistence/immutability go, the skip list doesn't seem well suited to that, either--any time you change an element, you'd have to replace all the elements with pointers to it, and elements with pointers to those, and so on recursively. There are standard solutions to this, but all would entail nontrivial changes to the structure.
In the end, it would be easy to make something not obviously broken that looked like a skip list, but I don't know whether it would have the same performance characteristics, or even worthwhile performance at all.
Given that skip lists are, in essence, a way of retrofitting some of the benefits of a tree structure onto a linked list, I suspect it would be more worthwhile to find an existing immutable, functional tree structure and retrofit some of the benefits of a linked list onto it.
You are right about that. But I did not have time for a longer explanation and some people take "persistent" to mean "can be saved to disk".
For stochastic algorithms you will probably use the same trick as with monadic I/O --- you can make the description of the algorithm purely functional, but not its execution.
Certainly possible, but how well this works depends on how, and to what extent, referential transparency is enforced by the language.
For instance, in Haskell, there really isn't a satisfying solution that I'm aware of. Threading a PRNG (as with the state monad) keeps the code "pure", but enforces a strict sequencing on use of the structure, wrecking laziness. On the other hand, any nondeterminism without threading a PRNG probably requires unsafePerformIO.