Mastering JavaScript Functional Programming - Second Edition

A final caveat

Working with persistent data structures requires some cloning, but how would you implement a persistent array? If you think about this, you'll realize that, in that case, there would be no way out apart from cloning the whole array after each operation. This would mean that an operation such as updating an element in an array, which took a constant time, would now take a length of time proportional to the size of the array.

In algorithm complexity terms, we would say that updates went from being an O(1) operation to an O(n) one. Similarly, access to an element may become an O(log n) operation, and similar slowdowns might be observed for other operations, such as mapping and reducing.

How do we avoid this? There's no easy solution. ...