4 ms·
Brief nitpicking: "persistent" and "purely functional" are not really the same thing. On the "purely functional" end, any stochastic algorithm is by definition
by camccann 17y ago
Brief nitpicking: "persistent" and "purely functional" are not really the same thing.
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.
- keefe 17y agolocal state, I like to have it... I think this is a nice argument for using oop
- chancho 17y agolocal state, you will not like what concurrent threads do to it... For every nice argument there is a counter.
- keefe 17y agoI'm absolutely fine with what concurrent threads would do to it? Thread synch stuff is really not hard once you've done it a while. It's actually one of the more fun pieces of programming, given that you have jprofiler (or similar) to inspect what's going on in the jvm as you try different things. To me, it is a very logical idea and powerful tool to pair up a bit of memory with a bit of algorithm.
- eru 17y ago> Brief nitpicking: "persistent" and "purely functional" are not really the same thing. 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.
- camccann 17y agoFor 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.
- chancho 17y ago'Probabilistic' doesn't have to mean 'nondeterministic'. Hash tables are deterministic and probabilistic. You could probably do the same with a skip list: hash the key to see what level of the skip list it gets promoted to.
- eru 17y agoIf you split your PRNG, you can 'tree' it through your algorithm instead of threading it. That should help with lazyness.