Does D have "structural sharing" of immutable collections?
Andrei Alexandrescu
SeeWebsiteForEmail at erdani.org
Wed May 23 14:13:35 PDT 2012
On 5/23/12 1:53 PM, Roman D. Boiko wrote:
> On Wednesday, 23 May 2012 at 18:51:32 UTC, Roman D. Boiko wrote:
>> Immutable collections in most cases have the same performance
>> characteristics as mutable ones. Space consumption may be higher, but
>> not necessarily.
>>
>> Instead of mutating a collection, a new one is returned each time you
>> add or remove an element. It shares most nodes with a previous one.
>
> I've posted some links with information on this topic:
> http://d-coding.com/2012/05/21/functional-data-structures.html
>
> It is also easy to find other sources on this topic for those who are
> interested.
Okasaki put together the ultimate work on immutable data structures. I
have plans to add immutable collections to D containers once I sort out
the allocators matter. Unfortunately, I find myself gasping for time so
the news that you are working on such are awesome. I suggest you to
absorb the approach taken by ranges and (however incomplete it looks at
the moment) std.container, and build on such.
Andrei
More information about the Digitalmars-d
mailing list