There are some nice examples here but I wanted to jump in with some personal ones where immutability helped a ton. In my case, I started off designing an immutable concurrent data structure mainly with the hopes of just being able to confidently run code in parallel with overlapping reads and writes and not having to worry about race conditions. There was a talk John Carmack gave that kind of inspired me to do it where he talked about such an idea. It's a pretty basic structure and pretty trivial to implement like this:
Of course with a few more bells and whistles to it like being able to remove elements in constant time and leave reclaimable holes behind and have blocks get derefed if they become empty and potentially freed for a given immutable instance. But basically to modify the structure, you modify a "transient" version and atomically commit the changes you made to it to get a new immutable copy that doesn't touch the old one, with the new version only creating new copies of the blocks that have to be made unique while shallow copying and reference counting the others.
However, I didn't find it that useful for multithreading purposes. After all, there's still the conceptual problem where, say, a physics system applies physics concurrently while a player is trying to move elements around in a world. Which immutable copy of the transformed data do you go with, the one the player transformed or the one the physics system transformed? So I haven't really found a nice and simple solution to this basic conceptual problem except to have mutable data structures which just lock in a smarter way and discourage overlapping reads and writes to the same sections of the buffer to avoid stalling threads. That's something John Carmack seems to have possibly figured out how to solve in his games; at least he talks about it like he can almost see a solution without opening up a car of worms. I haven't gotten as far as him in that regard. All I can see are endless design questions if I tried to just parallelize everything around immutables. I wish I could spend a day picking at his brain since most of my efforts started off with those ideas he threw out.
Nevertheless, I found enormous value of this immutable data structure in other areas. I even use it now to store images which is really weird and does make random-access require some more instructions (right shift and a bitwise and along with a layer of pointer indirection), but I'll cover the benefits below.
Undo System
One of the most immediate places I found to benefit from this was the undo system. Undo system code used to be one of the most error-prone things in my area (visual FX industry), and not just in the products I worked on but in competing products (their undo systems were also flaky) because there were so many different types of data to worry about undoing and redoing properly (property system, mesh data changes, shader changes that weren't property-based like swapping one with the other, scene hierarchy changes like changing the parent of a child, image/texture changes, etc. etc. etc.).
So the amount of undo code required was enormous, often rivaling the amount of code implementing the system for which the undo system had to record state changes. By leaning on this data structure, I was able to get the undo system down to just this:
on user operation:
copy entire application state to undo entry
perform operation
on undo/redo:
swap application state with undo entry
Normally that code above would be enormously inefficient when your scene data spans gigabytes to copy it in entirety. But this data structure only shallow copies things that weren't changed, and it actually made it cheap enough store an immutable copy of the entire application state. So now I can implement undo systems as easily as the code above and just focus on using this immutable data structure to make copying unchanged portions of the application state cheaper and cheaper and cheaper. Since I started using this data structure, all my personal projects have undo systems just using this simple pattern.
Now there is still some overhead here. Last time I measured it was around 10 kilobytes just to shallow copy the entire application state without making any changes to it (this is independent of scene complexity since the scene is arranged in a hierarchy, so if nothing below the root changes, only the root is shallow copied without having to descend down into the children). That's far from 0 bytes as would be needed for an undo system only storing deltas. But at 10 kilobytes of undo overhead per operation, that's still only a megabyte per 100 user operations. Plus I could still potentially squash that down further in the future if needed.
Exception-Safety
Exception-safety with a complex application is no trivial matter. However, when your application state is immutable and you're only using transient objects to try to commit atomic change transactions, then it's inherently exception-safe since if any part of the code throws, the transient is tossed away before giving a new immutable copy. So that trivializes one of the hardest things I've always found to get right in a complex C++ codebase.
Too many people often just use RAII-conforming resources in C++ and think that's enough to be exception-safe. Often it isn't, since a function can generally cause side effects to states beyond the ones local to its scope. You generally need to start dealing with scope guards and sophisticated rollback logic in those cases. This data structure made it so I often don't need to bother with that since the functions aren't causing side effects. They're returning transformed immutable copies of application state instead of transforming the application's state.
Non-Destructive Editing
Non-destructive editing is basically layering/stacking/connecting operations together without touching the original user's data (just input data and output data without touching input). It's typically trivial to implement with a simple image application like Photoshop and might not benefit that much from this data structure since many operations might just want to transform every pixel of the entire image.
However, with non-destructive mesh editing, for example, a lot of operations often want to transform only a part of the mesh. One operation might just want to move some vertices here. Another might just want to subdivide some polygons there. Here the immutable data structure helps a ton in avoiding the need to have to make an entire copy of the entire mesh just to return a new version of the mesh with a small part of it changed.
Minimizing Side Effects
With these structures in hand, it also makes it easy to write functions that minimize side effects without incurring a huge performance penalty for it. I've found myself writing more and more functions which just return whole immutable data structures by value these days without incurring side effects, even when that seems a bit wasteful.
For example, typically the temptation to transform a bunch of positions might be to accept a matrix and a list of objects and transform those in a mutable fashion. These days I find myself just returning a new list of objects.
When you have more functions like this in your system that cause no side effects, it definitely makes it easier to reason about the correctness of it as well as test its correctness.
The Benefits of Cheap Copies
So anyway, these are the areas where I found the most use out of immutable data structures (or persistent data structures). I also got a bit overzealous initially and made an immutable tree and immutable linked list and immutable hash table, but over time I rarely found as much use for those. I mainly found the most use of the chunky immutable array-like container in the diagram above.
I also still have a lot of code working with mutables (find it a practical necessity at least for low-level code), but the main application state is an immutable hierarchy, drilling down from an immutable scene to immutable components inside of it. Some of the cheaper components are still copied in full, but the most expensive ones like meshes and images use the immutable structure to allow those partial cheap copies of only the parts that needed to be transformed.
