4 ms·
The extent to which immutability leads to duplication seems a matter of implementation rather than a principle. The compiler/runtime could optimize such that m
by yobbo 4y ago
The extent to which immutability leads to duplication seems a matter of implementation rather than a principle.
The compiler/runtime could optimize such that memory is reused, as long as all other laws are obeyed.
- UncleMeat 4y agoTo some degree. But it really is the case that a persistent functional data structure is going to have a slower insert operation than a traditional mutable set. There's no getting around that.
- savingsPossible 4y agohttps://hackage.haskell.org/package/containers-0.6.5.1/docs/Data-Sequence.html https://hackage.haskell.org/package/containers-0.6.5.1/docs/... log(n) slowdown to add in the end but the cost to add in the middle is cheaper then the trivial array (see insertAt)
- UncleMeat 4y agoThe asymptotic behavior is not the entire story. Because persistent data structures almost necessarily need to have their data allocated non-contiguously they have terrible cache performance and prefetching/speculation behavior in comparison to data structures that take advantage of contiguous memory locations. I also mentioned sets, not lists.
- savingsPossible 4y agoNot that this answers all your objections (it does not, caching might be a problem!) But sets are also a mere log(n) away https://hackage.haskell.org/package/containers-0.6.6/docs/Data-IntMap-Lazy.html https://hackage.haskell.org/package/containers-0.6.6/docs/Da...