Does D have "structural sharing" of immutable collections?
Andrei Alexandrescu
SeeWebsiteForEmail at erdani.org
Wed May 23 15:03:02 PDT 2012
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
More information about the Digitalmars-d
mailing list