For example in clojure, sequences are implemented as 32-ary tries so insert/delete/update to any particular index will only cost around sizeOfNode * numParents=32 * log_32(n). This comes with a cost that indexing is now log_32(n) but it's usually a fair price to pay.
Also available as a free PDF: https://www.cs.cmu.edu/~rwh/theses/okasaki.pdf
This is true, but unfortunately those libraries/languages don't make use of that tree structure for "partial memoization" of derived data. They very well could, but they don't -- even when you use Immutable.js in a Redux app, and you use Reselect, your selectors will take linear time when you mutate one element in an object/array instead of taking constant- or log-time.
I think it could be a great technique for a lot of things -- compilers and database views, in addition to front-end state.
TS and immutablejs work together surprisingly well. One enforces immutability via static analysis, and the other creates (relatively) efficient datastructures predicated on the assumption of immutability.
Immutable.js was a bad solution when it was used purely to enforce immutability. Unfortunately that's what its reputation became, but really it should be thought of as a lib that takes advantage of immutable data, not a lib that checks for immutability.