3 ms·
I think we are still talking past each other. So, first the link you asked for. https://news.ycombinator.com/item?id=7928653 https://news.ycombinator.com/item
by taeric 12y ago
I think we are still talking past each other. So, first the link you asked for. https://news.ycombinator.com/item?id=7928653 https://news.ycombinator.com/item?id=7928653 If I am misrepresenting it, apologies. And let me know. :)
I think how I'm talking past you is I am perfectly fine with mutation based algorithms using immutable data structures. That is, union find can easily be done using a standard Scala immutable Vector for the array. Only caveat is each "mutation" has to be of the form "x = x.setValue(index, value)".
So, the question I give you is do you consider that a mutation based algorithm or not? I would, as the heart of the algorithm is still based on the updates of the array. You are just safe in knowing that any place you have let a reference to it leak out is never going to change. This is both good and bad, of course. Depending on what you are doing.
Stated differently, I don't think we have been distinguishing between mutation based algorithms that use immutable data structures with mutation based data structures. (That is to say, I have not been concerning myself with that.) So, if you consider it an immutable algorithm as soon as an immutable data structure enters into the mix, then yes, most of what I've been saying is nonsense.
Seems unnecessarily restrictive to me, as just changing it such that each update to the underlying structure requires changing a pointer as well as following the data structure update is much less of a change than, for example, the story that is at the root of this discussion.
For Git, this is roughly what it does. If you do a repack, the new pack is only used once it is done. They rebuild the entire pack, then update the reference to the active pack. If you cancel the process at any point, the old pack is still good and still works. The process of building the structure is heavily "mutation" based, but once it is made, nothing is ever changed.
And you should look into the DLX made parallel. It is very different than how algorithms are made so in most popular literature.