Re:Why Functional Programming Should Be the Future of Software
by UncleMeat on Wednesday November 02, 2022 @08:14AM
(#33434465)
To 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.
Re:Why Functional Programming Should Be the Future of Software
by savingsPossible on Wednesday November 02, 2022 @09:01AM
(#33435016)
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)
Re:Why Functional Programming Should Be the Future of Software
by UncleMeat on Wednesday November 02, 2022 @09:09AM
(#33435092)
The 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.
Re:Why Functional Programming Should Be the Future of Software
by savingsPossible on Friday November 04, 2022 @01:50PM
(#33470963)
Not 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/Da...
The compiler/runtime could optimize such that memory is reused, as long as all other laws are obeyed.