Hacker News Reader

In most situations, you use persistent data structures where you only have to copy the modified leaves.

If you really need your type to be backed by a contiguous block of memory, you batch updates (stencils, SIMD, etc.)

But if you modify the leaf, don't you also have to modify the branch node that points to the leaf, so that it points to the new one? And every node from there to the root?

Yes, you (or rather, core library developers) need to pick a data structure appropriate to your access patterns: linked lists for iteration, search trees for concatenation, finger trees for random access, and so on. But you should be doing this anyway for clarity, even if you face no performance constraints.

Reply on news.ycombinator.com