optimized immutable containers

[monarch_dodra]

On Thursday, 4 July 2013 at 06:36:52 UTC, w0rp wrote:
> On Thursday, 4 July 2013 at 05:45:41 UTC, monarch_dodra wrote:
>> Just to be clear, I didn't say it before: That behavior is a 
>> bug, and is currently undergoing correction. Please don't 
>> relly on it.
>
> I see. Well, a garbage collected linked list is very easy to 
> implement, so I suppose it's easy for you to get these 
> semantics if you want them.

For a Doubly linked list, the semantics and implementation are 
actually kind of hard to get right. What you basically have is a 
"chain" of nodes, and each list simply references a part of that 
chain. It is not, however, possible to "fork" that chain.

For Singly Linked list, the semantics and implementation are 
actually easier: The data structure is more like a "mountain 
river", where every chain is a creek that converges to the same 
river.

>>> The operations on the types could use more qualifiers, 
>>> though. Using them in pure functions would make it possible 
>>> to implicitly convert them to immutable, which is a powerful 
>>> thing indeed.
>>
>> Keep in mind that in D, const is "turtles all the way down", 
>> so it is not possible to have an "immutable container of 
>> mutable items". Once you give something the "const" handle, it 
>> is very hard to strip it.
>
> I am aware of how const and immutable work, and that's what I 
> want. It's just nice that with a pure qualifier, you can 
> sometimes build immutable data from functions returning mutable 
> data without creating any copies.

Well, I was thinking maybe something maybe even better? An 
immutable shared container that contains shared mutable objects 
would be more helpful. Implemented as a *shared* class with no 
functions that pdrovide actual mutation. The container itself 
would provide lock-free access to all its elements, and then each 
element would individually manage concurrency.

Such a container could also provide shallow copy (eg: elements 
are not copied). The interface would need more work, but I think 
this is an example of what D could provide that is better than 
what other languages ca do.