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