5 ms·
Not good enough. When the time comes that you do need to add something, then what? Clone it? In languages that allow you to freeze a collection, adding somethin
by _halgari 12y ago
Not good enough. When the time comes that you do need to add something, then what? Clone it? In languages that allow you to freeze a collection, adding something to a frozen collection is often a O(n) operation. Most of the collections in this library provide operations that grow collections in (almost) constant time.
- Kiro 12y ago> Clone it? Yes, isn't that enough?
- dannysatan 12y agoNo, it's time and memory inefficient. When you add something to immutable data structure, a new structure is created but internally it shares the data with a structure it was derived from.
- afandian 12y agoLet's say you want to create a set by recursing along a million long sequence, collecting the unique values. This would be done with an operation called `reduce`. The time and storage complexity of that would be exponential if each step you had to clone a copy of the output list. With a persistent data structure, as much of the structure as possible is re-used. And a list is the simplest possible structure. What about a tree? Using `reduce` is, I would say, in the top 5 techniques used in functional programming. And it would be severely hobbled without efficient persistent immutable structures.