View mode: basic / threaded / horizontal-split · Log in · Help
May 23, 2012
Does D have "structural sharing" of immutable collections?
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
Re: Does D have "structural sharing" of immutable collections?
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
Re: Does D have "structural sharing" of immutable collections?
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
Re: Does D have "structural sharing" of immutable collections?
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
Re: Does D have "structural sharing" of immutable collections?
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
Re: Does D have "structural sharing" of immutable collections?
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
Re: Does D have "structural sharing" of immutable collections?
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
Re: Does D have "structural sharing" of immutable collections?
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
Re: Does D have "structural sharing" of immutable collections?
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
Re: Does D have "structural sharing" of immutable collections?
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