On Friday, 23 October 2015 at 17:44:55 UTC, deadalnix wrote:
> void foo(T)(const Collection!const(T) c) {}
> void main() {
>   Collection!T c;
>   foo(c); // Error, GTFO !
> }

How about this?

void f(T)(const Collection!T c)
{
  const Collection!(Unqual!T) cc = c;
}

On 10/24/2015 09:22 PM, Andrei Alexandrescu wrote:
> On 10/24/15 3:19 PM, Timon Gehr wrote:
>> Even if this was possible, it would not be a very good idea. Persistent
>> data structures have use cases that would be hindered by required
>> transitive immutability.
>
> This part I don't quite get.

The slots are not mutable, but they are not /transitively/ immutable either. Note that this does not require any special effort, nor does it /prevent/ stored elements from being (transitively) immutable. Scala does it this way. (Haskell as well, basically.)

> Are there any languages that offer
> containers with immutable topology but mutable slots, and call them
> persistent data structures? -- Andrei

Not that I know of, unless you count the hidden updates Haskell implementations may perform in order to provide lazy semantics (which 'immutable' in D prevents, this alone is a sufficient reason not to force it on users).
However, that would be useful as well (as a potential performance optimization if the identity of the stored elements does not matter).


This paper of Sarnak and Tarjan discusses a version of what they call persistent rb-trees that only allows updates on the last version (which is often sufficient). (The point of the restriction is to lower space usage.) It changes color information on existing nodes and it keeps mutable lists in the nodes (i.e. making the nodes immutable would not work.)

http://www.link.cs.cmu.edu/15859-f07/papers/point-location.pdf

One might now say that those implementation details don't matter, and that the slots should still be transitively immutable. Well, one may want to use such data structures _within_ other persistent data structures.

(Just consider e.g. the case where, given a 3D point cloud of size n, and a number of axis-aligned boxes, you want a way to count the number of points in each box, given that the boxes arrive in an online fashion, while the points are known from the start. (Here, we want O(n log² n) preprocessing time, O(n log n) space and O(log² n) query time). One way to achieve that involves storing instances of an augmented version of their persistent rb-tree (they should support the range queries I have mentioned in my list of useful data structures) within a persistent augmented tree with predetermined O(log n)-depth topology (this container I had missed to mention).)

You can't do that if slots are transitively immutable.

On 10/24/2015 09:33 PM, David Nadlinger wrote:
> On Friday, 23 October 2015 at 17:44:55 UTC, deadalnix wrote:
>> Collection!T and Collection!const(T) are 2 completely different types.
>
> Isn't this also required anyway because of covariance vs. contravariance
> considerations?
>
>   — David

(I'm assuming 'this' is referring to a solution to the problem.)

Yes, basically one often wants bit-by-bit conversions between structs whose fields corecursively convert to each other bit-by-bit. If we had opImplicitCastTo, this could probably be implemented (somewhat inefficiently) in the library, but a targeted language feature might be in order.

On Saturday, 24 October 2015 at 19:33:03 UTC, David Nadlinger wrote:
> On Friday, 23 October 2015 at 17:44:55 UTC, deadalnix wrote:
>> Collection!T and Collection!const(T) are 2 completely different types.
>
> Isn't this also required anyway because of covariance vs. contravariance considerations?
>
>  — David

It is close, but not exactly the same. Covariance/contravariance can be emutalted via alias this without too much trouble for a container (however, it is hard to ensure correctness, but I'd assume not too hard). On the other hand, the qualifier thing turtle from the collection to the element in the collection, which is not that easy to achieve.

On Sunday, 25 October 2015 at 05:37:02 UTC, deadalnix wrote:
> On Saturday, 24 October 2015 at 19:33:03 UTC, David Nadlinger wrote:
>> On Friday, 23 October 2015 at 17:44:55 UTC, deadalnix wrote:
>>> Collection!T and Collection!const(T) are 2 completely different types.
>>
>> Isn't this also required anyway because of covariance vs. contravariance considerations?
>>
>>  — David
>
> It is close, but not exactly the same. Covariance/contravariance can be emutalted via alias this without too much trouble for a container (however, it is hard to ensure correctness, but I'd assume not too hard). On the other hand, the qualifier thing turtle from the collection to the element in the collection, which is not that easy to achieve.

The bigger problem is probably ranges rather than containers. We get tail-const slices from arrays all the time, but opSlice with no arguments isn't really a range operation (none of the range traits require it), and it's pretty painful to get it to make tail-const work with opSlice anyway (though I know that the EMSI guys were jumping through all kinds of hoops to make it work, so their containers make actually handle it reasonably well). Plus there's the fun problem of how declaring opSlice on a range causes foreach to call it, which essentially means that your range can get saved accidentally, which can be problematic (especially for ranges like RefRange).

It's been a while since I sat down and worked through the various issues that we have here. I should probably do that soon and see if I can distill them down well enough to come up with a DIP to resolve them - or at least to clearly present them so that they can be discussed. What we have right now mostly works, but it falls apart in some corner cases - especially if you want to be able to operate on a range like you would an array.

- Jonathan M Davis

On 10/23/2015 01:44 PM, deadalnix wrote:
> On Friday, 23 October 2015 at 11:03:37 UTC, Andrei Alexandrescu wrote:
>> On 10/22/15 1:09 AM, deadalnix wrote:
>>> The elephant in the room: make the template parameter's type qualifier
>>> transitive with the collection's qualifier.
>>
>> Could you please give more detail on this? Thanks! -- Andrei
>
> Sure. We have a problem when it come to collection in the fact that type
> qualifier do not turtle down as one would expect.
>
> Collection!T and Collection!const(T) are 2 completely different types.
> There is a good reason for this : static if (is(T == const)) { ... } .
> As a result thing like :
>
> void foo(T)(const Collection!const(T) c) {}
> void main() {
>    Collection!T c;
>    foo(c); // Error, GTFO !
> }

Makes sense. The way I like to think about it is in terms of compatibility with built-in types such slices. This code works:

void foo(T)(const T[] c) {}
void main() {
  int[] c;
  foo(c); // fine
}

> With the different qualifiers and implicit conversion, thing become
> quite tricky. You can simulate them partially with a set of carefully
> crafted alias this (but not having multiple alias this doesn't make
> things any simpler) but there is the monster of mutually recursive
> template instanciation that is lurking.
>
> As far as i know, jmdavis had some good work done on this, but it was
> far from perfect.

Thanks, I see. The way I see it is as the work of "alias this"; any failure can be ascribed as a burden on the alias this definition.

Jonathan, do you have a link to your work?


Andrei

On 10/23/2015 07:21 PM, bigsandwich wrote:
> On Friday, 23 October 2015 at 17:44:55 UTC, deadalnix wrote:
>> On Friday, 23 October 2015 at 11:03:37 UTC, Andrei Alexandrescu wrote:
>>> [...]
>>
>> Sure. We have a problem when it come to collection in the fact that
>> type qualifier do not turtle down as one would expect.
>>
>> [...]
>
> Its not just type qualifiers. Containers of derived types have the same
> problem.  This is also a problem in C++.

This is something easy to live with. In fact, mutable containers are not supposed to even convert to containers of base objects. -- Andrei

On 10/24/2015 07:03 PM, Timon Gehr wrote:
> On 10/24/2015 09:22 PM, Andrei Alexandrescu wrote:
>> On 10/24/15 3:19 PM, Timon Gehr wrote:
>>> Even if this was possible, it would not be a very good idea. Persistent
>>> data structures have use cases that would be hindered by required
>>> transitive immutability.
>>
>> This part I don't quite get.
>
> The slots are not mutable, but they are not /transitively/ immutable
> either. Note that this does not require any special effort, nor does it
> /prevent/ stored elements from being (transitively) immutable. Scala
> does it this way. (Haskell as well, basically.)

I see. Well, this will be unpleasant to implement in D.

One simple way to do so would be to have accessors return rvalues:

T front() { ... }

Then you get to change the indirections of T, if any, but not what's stored in the container directly.

Problem is accessing every element by rvalue is likely to be inefficient in the general case (even on data without copy ctors).


Andrei

On 10/25/2015 08:31 PM, Andrei Alexandrescu wrote:
> On 10/23/2015 07:21 PM, bigsandwich wrote:
>> On Friday, 23 October 2015 at 17:44:55 UTC, deadalnix wrote:
>>> On Friday, 23 October 2015 at 11:03:37 UTC, Andrei Alexandrescu wrote:
>>>> [...]
>>>
>>> Sure. We have a problem when it come to collection in the fact that
>>> type qualifier do not turtle down as one would expect.
>>>
>>> [...]
>>
>> Its not just type qualifiers. Containers of derived types have the same
>> problem.  This is also a problem in C++.
>
> This is something easy to live with. In fact, mutable containers are not
> supposed to even convert to containers of base objects. -- Andrei
>

This is true for containers with reference semantics, but not for containers with value semantics.

This compiles (D code):

class A{}
class B: A{}

void main(){
    A[2] a;
    B[2] b;
    a=b;
}

This does not compile (C++ code):

class A{};
class B: A{};

int main(){
    vector<A*> a;
    vector<B*> b;
    a=b;
}

However, the conversion would be safe. For persistent and COW containers, the copy would even be fast.

On 10/25/2015 05:06 PM, Timon Gehr wrote:
>
> class A{};
> class B: A{};
>
> int main(){
>      vector<A*> a;
>      vector<B*> b;
>      a=b;
> }
>
> However, the conversion would be safe.

Agreed. I don't see that as an important matter though; it's after all a coercion so a function call is plenty fine. -- Andrei