Does D have "structural sharing" of immutable collections?

[Steven Schveighoffer]

On Wed, 23 May 2012 14:32:57 -0400, Roman D. Boiko <rb at d-coding.com> wrote:

> On Wednesday, 23 May 2012 at 18:24:28 UTC, simendsjo wrote:
>> On Wed, 23 May 2012 20:18:54 +0200, simendsjo <simendsjo at gmail.com>  
>> wrote:
>>
>>> On Wed, 23 May 2012 17:05:21 +0200, Roman D. Boiko <rb at 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 :(

There is a very good reason however :)

I need tail-immutable and tail-const structs to be able to avoid "code  
pasting hell".

Until then, I feel very unmotivated to do anything regarding const and  
immutability.

FWIW, std.container.RedBlackTree is derived from dcollections.RBTree.

Regarding sharing structure, the class type would have to be specifically  
written to use this.  It's not just slapping on immutable tags.

For at least RBTree, and my implementation of Hash, this would not be  
feasible.

Certainly ArrayList, LinkedList, and probably Deque, they could share  
structure

If you need a sorted tree structure that supports sharing immutable state,  
you likely have to find a different algorithm than redblack, since adding  
nodes can modify the tree structure via rotates.

-Steve