> Most functional languages have immutable persistent data structures that don't require a linear copy and are fairly efficient.

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.