Does D have "structural sharing" of immutable collections?
schveiguy at yahoo.com
Wed May 23 15:25:36 PDT 2012
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.
> 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.
More information about the Digitalmars-d