On 5/23/12 1:54 PM, David Nadlinger wrote:
On Wednesday, 23 May 2012 at 18:39:02 UTC, Stewart Gordon wrote:
When the tree is immutable, only lookup speed is of any real
relevance, so you might as well create a perfectly balanced binary
tree. Or even better, an array.
An array does not facilitate sharing common subsets between containers,
which is usually what you are aiming for when designing immutable
containers – the idea is to get away with immutability performance-wise
because you don't have to copy much on the common mutation operations.
Yah, FP doesn't like arrays and immutable containers essentially eschew
arrays altogether. (The most surprising thing to me is that the FP
community generally fails to acknowledge that as a problem.)
Immutable data structures use trees pervasively for random-access data.
Andrei
