Regarding your skeptism of immutable data structures, it's best to think of immutable data and data structures as copy-on-write instead of update-in-place. This is a technique that is currently very underused, for example most programming languages do not come with "persistent" copy-on-write collections.
Here is an example text editor built using immutable data structures in C++: https://github.com/arximboldi/ewig
Advantages are excellent support for concurrency (background save works while you edit) and trivial support for undo/redo.