Immutable data structures are great for undo-redo.

Sean Parent has a conference video out there about how undo in Photoshop is implemented by breaking the image into tiles then making a list of the history of each tile. This allows the “History Brush” to reach into the past and paint old pixels over new ones.

In C++, we usually copy the resources that we want to share, so as that accidental modification of a resource doesn't take place.

However, the copying becomes impractical from a performance point of view if the resources are big, so immutable resources offer an alternative that does not have the performance issues.

For example, if you have multiple threads computing sub-graphs of a graph and passing those sub-graphs around to other threads, copying the whole graph each time a thread needs to compute something that may potentially alter the graph is a killer for performance. You then have two choices:

Choice 1: make the graph thread-safe. Which is the usual route C++ takes.

Choice 2: make the graph out of immutable data structures.

Choice 1 is the practical choice when the scope of the work is limited, and therefore thread safety is easy to implement.

When the problem at hand becomes very complex though, and it's difficult to reason about the ordering of locks, immutable data structures is an easier choice.

The author has created a text editor which uses immutable data structures s.t. he can do fast undo / redo [1]

[1] https://github.com/arximboldi/ewig

I saw a demonstration where he copy pasted a file into itself until it was larger than whatever memory he had in the computer. He could still efficiently edit it (the data pointers were duplicated, not the data).

Pretty impressive.

Do you have the URL to the video?

I wrote something similar for a resource system for a game engine. If you had a ResourceHandle<T> you knew that the T inside it would never change, and it was safe to pass to any other system. You could always make a mutable copy of the RH<T> to get a T out (and as an optimization if you held the last handle, skip the copy). Once you were done writing to the T, you could tell the resource system to harden it into a handle to give to other systems again (which included serializing it to give it a static hash for the T). There was other cleverness to make it ergonomic that I've since forgotten. Across a large codebase it _was_ nice to ensure that immutable data wasn't going to change, and that you could load up data with the same hash again later and get the same results. It _is_ possible to do via mutable data structures, but you can't always ensure that every person on your team will be careful in the right way.

Try implementing a scheme on top of this. Stack and env management suddenly becomes trivial.

The same simplicity applies analogously to various other use cases which would be tedious and error prone to implement without immutable data structures.

Yes, there are many other benefits to immutability than parallelism applications related to correctness and ability to reason about programs. See referential transparency, etc.

Yes, immutable data structures can be used for capturing a temporal aspect without actually needing to model it explicitly in the underlying data.

Here's a document[1] explaining how to make a tree-like data structures persistent along with a motivating example of their use (at the end). The wikipedia page[2] for the problem also goes into other techniques and has some diagrams too.

tl;dr a naive approach to the point location query problem achieves O(N^2) space and O(logN) time per query, while simply modifying the data structure to be persistent achieves O(N) space while retaining O(logN) time per query.

[1] https://saco-evaluator.org.za/presentations/camp3_2017/persi... [2] https://en.wikipedia.org/wiki/Point_location