Is anyone aware of the new immutable containers in .Net framework?
http://blogs.msdn.com/b/bclteam/archive/2012/12/18/preview-of-immutable-collections-released-on-nuget.aspx.

While we can attach the immutable qualifier to any D containers, they will not perform nearly as well because they are essentially mutable structures. Making them immutable doesn't change the way they work, it merely forbids us to call the modifying methods. Every time we need to modify them we have to copy the entire thing which is not very efficient.

The .Net immutable containers are specially optimized so that they share the underlying data as much as possible. Creating a modified copy is cheap, usually O(1) or O(logN).

I think having something similar in D would make immutables much more attractive.

finalpatch:

> I think having something similar in D would make immutables much more attractive.

I think that eventually we'll have some good immutable data structure in Phobos (based on finger trees, etc). But first probably there's a need for some mutable ones :-)

Bye,
bearophile

I suppose you could implement an efficiently copied immutable singly linked list like this very easily. I think that's a basic functional programming idea, new list with head + list. Making the nodes garbage collected would save on memory usage.

On Wednesday, 3 July 2013 at 07:22:00 UTC, w0rp wrote:
> I suppose you could implement an efficiently copied immutable singly linked list like this very easily. I think that's a basic functional programming idea, new list with head + list. Making the nodes garbage collected would save on memory usage.

The irony here (as stated by Bearophile) is that this is currently how our SList and DList are actually implemented: Not value nor ref semantics: Just shared owner ship of nodes...

EG:
--------
import std.stdio, std.container;

void main()
{
    alias SLI = SList!int;
    auto a = SLI(1);
    auto b = a;
    auto c = a;
    b.insertFront(0);
    c.insertFront(2);

    writeln("a[]: ", a[]);
    writeln("b[]: ", b[]);
    writeln("c[]: ", c[]);
}
--------
a[]: [1]
b[]: [0, 1]
c[]: [2, 1]
--------

-_-

On Wednesday, 3 July 2013 at 08:04:50 UTC, monarch_dodra wrote:
> The irony here (as stated by Bearophile) is that this is currently how our SList and DList are actually implemented: Not value nor ref semantics: Just shared owner ship of nodes...

Well, that was easy! I did not know that this is exactly how SList and DList are implemented, as I haven't had to use them yet, but that will come in handy eventualy. 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.

On Wednesday, 3 July 2013 at 22:03:14 UTC, w0rp wrote:
> On Wednesday, 3 July 2013 at 08:04:50 UTC, monarch_dodra wrote:
>> The irony here (as stated by Bearophile) is that this is currently how our SList and DList are actually implemented: Not value nor ref semantics: Just shared owner ship of nodes...
>
> Well, that was easy! I did not know that this is exactly how SList and DList are implemented, as I haven't had to use them yet, but that will come in handy eventualy.

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.

> 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 no possible to have an "immutable container of mutable items". Once you give something the "const" handle, it is very hard to strip it.

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.

>> 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.

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.