May 23, 2012
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.
May 23, 2012
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
May 23, 2012
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


May 23, 2012
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
May 23, 2012
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
May 23, 2012
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
May 23, 2012
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
May 23, 2012
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
May 23, 2012
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 :(
May 23, 2012
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.
« First   ‹ Prev
1 2 3
Top | Discussion index | About this forum | D home