Mastering JavaScript Functional Programming

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 basically 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 slow-downs might be observed for other operations, such as mapping, reducing, and so on.

How do we avoid this? ...