Does D have "structural sharing" of immutable collections?

[Steven Schveighoffer]

On Wed, 23 May 2012 17:54:42 -0400, Roman D. Boiko <rb at d-coding.com> wrote:

> On Wednesday, 23 May 2012 at 19:51:02 UTC, Steven Schveighoffer wrote:
>> 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
>
> I don't need to invent here, and it is definitely feasible. Okasaki  
> provided efficient algorithm for inserting nodes, and, IIRC, rotations  
> (not for deleting, though). But OCaml doesn't map to D easily (neither  
> does Haskel, I think).

I looked up how it could be done, the one thing I was not sure of was the  
parent node.  If you can have multiple references to the same subtree, how  
do you keep track of the parents.  But if you only are concerned about the  
ancestry of a single node, you can dynamically determine the line in  
O(lgn) time, and use that for the running of the redblack algorithm.

I'm not sure how efficient it would be.

-Steve