Comment by westoncb | Hacker News Reader

Comment by westoncb | Hacker News Reader

Parent Full thread

Anyone know if there is a best-practice immutable data structure variation here? The way I've thought about it is that if you store the entire sequence of operations which have occurred so far, and you have some function that can re-build the current state from that list, then you don't need any inverse operations. This means that undoing an operation is just removing the last operation performed from the operation list, and then rebuilding the state.

This seems nice since you don't have to figure out inverse operations (which I've seen get tricky), but I imagine the performance penalty of having to store all operations and rebuild the entire state every time could be problematic in some cases.

Then again, I imagine there are good standard optimizations for dealing with this kind of thing. One thing that occurs to me is that operations which 'cancel' each other could be sought out and eliminated before rebuilding the state.

I'd be glad for any more information on the subject!

Edit: more specifically I'm wondering if those optimizations do in fact exist, and if so what they are.

Do you mean https://en.wikipedia.org/wiki/Persistent_data_structure or something more specific for this case? It's known how to only incur an O(1) cost in time and space for making a data structure persistent. So then you just need to keep a reference to all past versions of the data structure you might ever want to undo back to.

EDIT: actually reading the wiki more carefully, I think they were talking about making a BST persistent specifically rather than any data structure. In that case looking at implementations such as rrb-vectors might be more interesting: https://github.com/clojure/core.rrb-vector

That wikipedia article looks interesting. I guess the only thing more specific I'm wondering about is persistent data structures for undo/redo systems. But just knowing the name 'persistent data structure' is useful.

You need a reference to each state, but because the components are themselves immutable you can share objects. For example a Document may contain many Blocks which contain many Lines. Changing a Line means replacing that object, its parent Block and its parent Document, but references to everything else can be copied over.

> and you have some function that can re-build the current state from that list...

You can be far mor efficient than that. The trick is to use immutable data structures to represent your state. When something changes, return a new state. Parts of the state that didn’t change are still referring to chunks from the previous state, so it’s actually sharing most of the memory from the previous state.

There are data structures in libraries in different languages that support this idea, for example system.collections.immutable in .NET. Anything you build in Erlang or Elixir will basically automatically do this. (As an aside, Erlang IOlists are a related concept to the piece tables the article talks about.)

Using this approach you don’t actually have to rebuild a previous or redo state, you just keep a list of states and move between them for undo and redo.

A list zipper? https://en.wikipedia.org/wiki/Zipper_(data_structure)

An advantage of storing operations instead of using immutable data structures is that with them you can implement region-based undo.

Seems like a fair fit for something like a Merkle tree. Do it properly and you could even save and load undo history with the file, treating external changes seen on load as new history states - which might be a nice feature to have.

Reply on news.ycombinator.com