Thread overview | ||||||||||||||||||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
|
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? | ||||
---|---|---|---|---|
| ||||
Posted in reply to Chris Dew | 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? | ||||
---|---|---|---|---|
| ||||
Posted in reply to 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
|
May 23, 2012 Re: Does D have "structural sharing" of immutable collections? | ||||
---|---|---|---|---|
| ||||
Posted in reply to 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 |
May 23, 2012 Re: Does D have "structural sharing" of immutable collections? | ||||
---|---|---|---|---|
| ||||
Posted in reply to Roman D. Boiko | 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? | ||||
---|---|---|---|---|
| ||||
Posted in reply to simendsjo | 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? | ||||
---|---|---|---|---|
| ||||
Posted in reply to simendsjo | 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? | ||||
---|---|---|---|---|
| ||||
Posted in reply to simendsjo | 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? | ||||
---|---|---|---|---|
| ||||
Posted in reply to simendsjo | 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? | ||||
---|---|---|---|---|
| ||||
Posted in reply to Roman D. Boiko | 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.
|
Copyright © 1999-2021 by the D Language Foundation