Just some beginner questions...

Does D have "structural sharing" of its immutable collections?

i.e. Can I make a copy of an immutable Map or List collection with an extra (or mutated) member, and will the returned (new) collection share most of it's structure with the earlier collection.

Thanks,

Chris.

Chris Dew:

> Does D have "structural sharing" of its immutable collections?
>
> i.e. Can I make a copy of an immutable Map or List collection with an extra (or mutated) member, and will the returned (new) collection share most of it's structure with the earlier collection.

Currently Phobos doesn't have a Map (there are built-in associative arrays), and there isn't a true List (there is a linked list, that so far I have not used).
Currently I think nothing in D works as you ask, it doesn't even have "immutable collections" like a Finger Tree or something.
But writing such collections is well within D type system capabilities, so I think eventually they will be present in Phobos if there is enough need.

Bye,
bearophile

Thanks for your answer,

Chris.

On Wednesday, 23 May 2012 at 14:35:31 UTC, bearophile wrote:
> Chris Dew:
>
>> Does D have "structural sharing" of its immutable collections?
>>
>> i.e. Can I make a copy of an immutable Map or List collection with an extra (or mutated) member, and will the returned (new) collection share most of it's structure with the earlier collection.
>
> Currently Phobos doesn't have a Map (there are built-in associative arrays), and there isn't a true List (there is a linked list, that so far I have not used).
> Currently I think nothing in D works as you ask, it doesn't even have "immutable collections" like a Finger Tree or something.
> But writing such collections is well within D type system capabilities, so I think eventually they will be present in Phobos if there is enough need.
>
> Bye,
> bearophile

On Wednesday, 23 May 2012 at 14:35:31 UTC, bearophile wrote:
> Chris Dew:
>
>> Does D have "structural sharing" of its immutable collections?
>>
>> i.e. Can I make a copy of an immutable Map or List collection with an extra (or mutated) member, and will the returned (new) collection share most of it's structure with the earlier collection.
>
> Currently Phobos doesn't have a Map (there are built-in associative arrays), and there isn't a true List (there is a linked list, that so far I have not used).
> Currently I think nothing in D works as you ask, it doesn't even have "immutable collections" like a Finger Tree or something.
> But writing such collections is well within D type system capabilities, so I think eventually they will be present in Phobos if there is enough need.
>
> Bye,
> bearophile

I need some immutable collections for my D Compiler Tools project, namely linked list, red-black tree, and possibly some others.

So I'm going to create them for my use, and later generalize. I've created a project on GitHub, but didn't implement anything useful yet.

Some more information is available at http://d-coding.com/2012/05/21/functional-data-structures.html

On Wed, 23 May 2012 17:05:21 +0200, Roman D. Boiko <rb@d-coding.com> wrote:

> I need some immutable collections for my D Compiler Tools project, namely linked list, red-black tree, and possibly some others.
>  So I'm going to create them for my use, and later generalize. I've created a project on GitHub, but didn't implement anything useful yet.

http://dlang.org/phobos/std_container.html#SList
http://dlang.org/phobos/std_container.html#RedBlackTree

On 23.05.2012 22:18, simendsjo wrote:
> On Wed, 23 May 2012 17:05:21 +0200, Roman D. Boiko <rb@d-coding.com> wrote:
>
>> I need some immutable collections for my D Compiler Tools project,
>> namely linked list, red-black tree, and possibly some others.
>> So I'm going to create them for my use, and later generalize. I've
>> created a project on GitHub, but didn't implement anything useful yet.
>
> http://dlang.org/phobos/std_container.html#SList

Awful junk.

> http://dlang.org/phobos/std_container.html#RedBlackTree

More or less fine... in git version.

-- 
Dmitry Olshansky

On Wed, 23 May 2012 20:18:54 +0200, simendsjo <simendsjo@gmail.com> wrote:

> On Wed, 23 May 2012 17:05:21 +0200, Roman D. Boiko <rb@d-coding.com> wrote:
>
>> I need some immutable collections for my D Compiler Tools project, namely linked list, red-black tree, and possibly some others.
>>  So I'm going to create them for my use, and later generalize. I've created a project on GitHub, but didn't implement anything useful yet.
>
> http://dlang.org/phobos/std_container.html#SList
> http://dlang.org/phobos/std_container.html#RedBlackTree

And http://dsource.org/projects/dcollections

On Wednesday, 23 May 2012 at 18:18:55 UTC, simendsjo wrote:
> On Wed, 23 May 2012 17:05:21 +0200, Roman D. Boiko <rb@d-coding.com> wrote:
>
>> I need some immutable collections for my D Compiler Tools project, namely linked list, red-black tree, and possibly some others.
>> So I'm going to create them for my use, and later generalize. I've created a project on GitHub, but didn't implement anything useful yet.
>
> http://dlang.org/phobos/std_container.html#SList
> http://dlang.org/phobos/std_container.html#RedBlackTree

Those are not immutable, unfortunately

On Wednesday, 23 May 2012 at 18:24:28 UTC, simendsjo wrote:
> On Wed, 23 May 2012 20:18:54 +0200, simendsjo <simendsjo@gmail.com> wrote:
>
>> On Wed, 23 May 2012 17:05:21 +0200, Roman D. Boiko <rb@d-coding.com> wrote:
>>
>>> I need some immutable collections for my D Compiler Tools project, namely linked list, red-black tree, and possibly some others.
>>> So I'm going to create them for my use, and later generalize. I've created a project on GitHub, but didn't implement anything useful yet.
>>
>> http://dlang.org/phobos/std_container.html#SList
>> http://dlang.org/phobos/std_container.html#RedBlackTree
>
> And http://dsource.org/projects/dcollections

Those aren't immutable either :(

On 23/05/2012 16:05, Roman D. Boiko wrote:
<snip>
> I need some immutable collections for my D Compiler Tools project, namely linked list,
> red-black tree, and possibly some others.
<snip>

What's the point of an immutable red-black tree?

The whole point of a red-black tree is to facilitate fast dynamic addition, removal and lookup of elements.

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.

Stewart.