On 10/22/2015 03:39 AM, Nordlöw wrote:
> On Wednesday, 21 October 2015 at 11:05:12 UTC, Andrei Alexandrescu wrote:
>> Internally, functional containers take advantage of common
>> substructure and immutability to share actual data. The classic
>> resource for defining and implementing functional containers is
>> http://www.amazon.com/Purely-Functional-Structures-Chris-Okasaki/dp/0521663504.
>>
>
> Online at: https://www.cs.cmu.edu/~rwh/theses/okasaki.pdf

That's the doctoral dissertation; I assume the book is more approachable. -- Andrei

On Thursday, 22 October 2015 at 07:13:58 UTC, KlausO wrote:
>
> Intrusive data structures have their strengths especially when nodes are
> part of several containers.
> I implemented some of the intrusive containers back in D1 times.
> See
>
> http://dsource.org/projects/nova/browser/trunk/nova/ds/intrusive
>
> KlausO

I also like having an intrusive container library in my toolbox: they don't limit membership to one container and they don't "bake" memory management into the container type.

http://www.boost.org/doc/libs/1_59_0/doc/html/intrusive.html

On Thursday, 22 October 2015 at 14:14:09 UTC, safety0ff wrote:
>
> I also like having an intrusive container library in my toolbox: they don't limit membership to one container and they don't "bake" memory management into the container type.
>

Also wanted to mention that this allows you to store variable sized data directly in the container without being forced to use a fixed size structure with a pointer to the variable portion. Which is useful for improving cache locality and reducing memory usage.

On Thursday, 22 October 2015 at 05:09:38 UTC, deadalnix wrote:
> On Thursday, 22 October 2015 at 02:13:12 UTC, bitwise wrote:
>> I needed containers, so I implemented a few:
>> https://github.com/bitwise-github/d-collections
>>
>> Currently included:
>>
>> List(T) - contiguous list like std::vector
>> LinkedList(T) - doubly linked list like std::list
>> Queue(T) - double-ended queue/contiguous circular buffer
>> Stack(T) - contiguous fifo stack
>>
>
> You got such a good start with the first 2 ones, but somehow missed on consistency. You should name the 2 other ones QueueList and StackList.

Actually, I was thinking of calling them QueueSeq and StackSeq ;)


>> I initially had this reversed, where List(T) was a value type, and ListRef(T) was a reference type, but I flipped it the other way to avoid unneeded copying for naive usage. I'm still not sure this is the right direction though. Optimization is a job of it's own, and it's a job for a pro. I believe the amount of effort spent to idiot-proof(for lack of a better term) the containers should be limited. Especially with the power of D's ranges, I think containers should generally(and in my code, usually do) stay put. IMO, If someone wants to pass something around, they should pass a range, not the container itself. My solution, however, does support both(ref/value), if needed.
>>
>
> Reference types or COW are definitively the way to go for the naive road. Think about it, 40% to 50% of chrome memory is std::string . Eager copy is not a healthy default.

I can't ignore how many times I've heard people talking about eager-copy containers in C++ and how they're a pain. I believe the value-type option should be available though.

Maybe the idea of default-ref-type containers could be taken a step further to hide the value types from casual users:

struct List(T)
{
    struct Core { ... } // specified as a fully useable container on it's own
    RefCounted!Core core;
    alias core this;
}

List!int.Core list; // value type container

Unlike the current std.container.Array(T) though, the payload inside the container should be fully useable on it's own.

I don't understand exactly how a COW container would work. Is this what's done with D strings right now? I've got a bad feeling about this idea. Containers have been around a long time, and I don't think it would be prudent to stray to far from traditional approaches.

>> There is still work to do, of course.
>>
>
> The elephant in the room: make the template parameter's type qualifier transitive with the collection's qualifier.

Not sure exactly what you mean by this. Currently, Ranges and Cursors are templated on the type of the container, so If the container is const, you get a const Range or Cursor. I haven't gone over the containers with a fine tooth comb yet, so if you can point anything out, it would be helpful.

    Bit

On Thursday, 22 October 2015 at 15:26:30 UTC, bitwise wrote:
> On Thursday, 22 October 2015 at 05:09:38 UTC, deadalnix wrote:
>> The elephant in the room: make the template parameter's type qualifier transitive with the collection's qualifier.
>
> Not sure exactly what you mean by this. Currently, Ranges and Cursors are templated on the type of the container, so If the container is const, you get a const Range or Cursor. I haven't gone over the containers with a fine tooth comb yet, so if you can point anything out, it would be helpful.

LOL. const and ranges do _not_ mix well - in part because popFront inherently requires that the range be mutable - but mostly because of templates.

If you have const(T)[], and you then you slap another const on it - const(const(T)[]) - the compiler knows full-well that that's equivalent to const(T[]). In fact, it even knows that if you slice a const(T[]), it's perfectly safe for the result to be const(T)[], because it's a different array, and by keeping the elements const, it won't screw with the elements of the one it was sliced from (since they're the same elements). But what about with ranges?

If you have Range!(const T) and then you do const Range!(const T), is that equivalent to const(Range!T)? Maybe, maybe not. The compiler certainly doesn't treat it as such - and it can't. Similarly, if you have const(Range!T) or const(Range!(const T)), and you slice the range, the compiler doesn't magically know that the slice can be Range!(const T). As far as the compiler is concerned, we're dealing with different types here. After all, what if the Range type had something like this in it

struct Range(T)
{
    static if(is(T == const))
    {
        // do something differently here
    }
}

The entire guts of Range could be completely different simply due to a difference in constness. Template constraints could also be used to overload on constness. So, unlike with arrays, there really is no guarantee that two instantiations of the same template are at all related to one another even when they seem to only differ by constness. Heck, to even attempt to have a range type which has an opSlice which returns a tail-const slice _requires_ that you have static ifs checking for constness, or you end up with a recursive template instantiation.

So, even without getting containers involved, const and ranges do _not_ mix well, even though const and arrays get along fantastically. And when you have to start considering what a containers opSlice is going to return an how it's going to deal with const, things get that much worse (e.g. is it even going to work to have opSlice be const). And depending on the container's internals, having a range only have const access to its underlying container could be problematic. IIRC, std.container.Array has had some issues with const related to its internals not having been designed in a way that worked well with D's const.

So, const throws a very interesting wrench into the mix when dealing with either ranges or containers, and the fact that const(Foo!T) is not necessarily the same as const(Foo!(const T)) can definitely be problematic.

- Jonathan M Davis

On Thursday, 22 October 2015 at 15:53:21 UTC, Jonathan M Davis wrote:
> On Thursday, 22 October 2015 at 15:26:30 UTC, bitwise wrote:
>> On Thursday, 22 October 2015 at 05:09:38 UTC, deadalnix wrote:
>>> The elephant in the room: make the template parameter's type qualifier transitive with the collection's qualifier.
>>
>> Not sure exactly what you mean by this. Currently, Ranges and Cursors are templated on the type of the container, so If the container is const, you get a const Range or Cursor. I haven't gone over the containers with a fine tooth comb yet, so if you can point anything out, it would be helpful.
>
> LOL. const and ranges do _not_ mix well - in part because popFront inherently requires that the range be mutable - but mostly because of templates.
>
> If you have const(T)[], and you then you slap another const on it - const(const(T)[]) - the compiler knows full-well that that's equivalent to const(T[]). In fact, it even knows that if you slice a const(T[]), it's perfectly safe for the result to be const(T)[], because it's a different array, and by keeping the elements const, it won't screw with the elements of the one it was sliced from (since they're the same elements). But what about with ranges?
>
> If you have Range!(const T) and then you do const Range!(const T), is that equivalent to const(Range!T)? Maybe, maybe not. The compiler certainly doesn't treat it as such - and it can't. Similarly, if you have const(Range!T) or const(Range!(const T)), and you slice the range, the compiler doesn't magically know that the slice can be Range!(const T). As far as the compiler is concerned, we're dealing with different types here. After all, what if the Range type had something like this in it
>
> struct Range(T)
> {
>     static if(is(T == const))
>     {
>         // do something differently here
>     }
> }
>
> The entire guts of Range could be completely different simply due to a difference in constness. Template constraints could also be used to overload on constness. So, unlike with arrays, there really is no guarantee that two instantiations of the same template are at all related to one another even when they seem to only differ by constness. Heck, to even attempt to have a range type which has an opSlice which returns a tail-const slice _requires_ that you have static ifs checking for constness, or you end up with a recursive template instantiation.
>
> So, even without getting containers involved, const and ranges do _not_ mix well, even though const and arrays get along fantastically. And when you have to start considering what a containers opSlice is going to return an how it's going to deal with const, things get that much worse (e.g. is it even going to work to have opSlice be const). And depending on the container's internals, having a range only have const access to its underlying container could be problematic. IIRC, std.container.Array has had some issues with const related to its internals not having been designed in a way that worked well with D's const.
>
> So, const throws a very interesting wrench into the mix when dealing with either ranges or containers, and the fact that const(Foo!T) is not necessarily the same as const(Foo!(const T)) can definitely be problematic.
>
> - Jonathan M Davis

Maybe look at the code next time before you LOL......

     Bit

On Thursday, 22 October 2015 at 16:29:19 UTC, bitwise wrote:
> Maybe look at the code next time before you LOL......

My point would be the same regardless. Range!(const T) and const(Range!T) - and Container!(const T) and const(Container!T) - have no relation as far as the compiler is concerned, and that makes dealing with const correctly a royal pain - particularly if you want a range to act like an array like it's supposed to be able to do (at least insofar as they have the same operations). You asked what deadalnix meant by

> The elephant in the room: make the template parameter's type qualifier transitive
> with the collection's qualifier.

and I tried to explain.

- Jonathan M Davis

On Thursday, 22 October 2015 at 17:13:48 UTC, Jonathan M Davis wrote:
> On Thursday, 22 October 2015 at 16:29:19 UTC, bitwise wrote:
>> Maybe look at the code next time before you LOL......
>
> My point would be the same regardless. Range!(const T) and const(Range!T) - and Container!(const T) and const(Container!T) - have no relation as far as the compiler is concerned, and that makes dealing with const correctly a royal pain - particularly if you want a range to act like an array like it's supposed to be able to do (at least insofar as they have the same operations). You asked what deadalnix meant by
>
>> The elephant in the room: make the template parameter's type qualifier transitive
>> with the collection's qualifier.
>
> and I tried to explain.
>
> - Jonathan M Davis

I'm not even sure you're talking about the same thing as deadalnix, and I think I have already done what he's asking.

example:
  List!int a = [1, 2];
  writeln( typeof(a[]).stringof );
  writeln( typeof(a[].front).stringof );
  writeln( is(typeof({ a[].popFront(); })).stringof );

  const(List!int) b = [1, 2];
  writeln( typeof(b[]).stringof );
  writeln( typeof(b[].front).stringof );
  writeln( is(typeof({ b[].popFront(); })).stringof );

output:
  Range!(ListBase!int)
  int
  true
  Range!(const(ListBase!int))
  const(int)
  true


Of course, neither of the following are possible because of the design of D's const.

import std.container;
Array!(const(int)) a;

import collections;
List!(const(int)) b;

Both will produce compilation errors.

    Bit

On Wednesday, 21 October 2015 at 20:06:41 UTC, Andrei Alexandrescu wrote:
> On 10/21/2015 03:38 PM, Jonathan M Davis wrote:
>> On Wednesday, 21 October 2015 at 19:19:23 UTC, Andrei Alexandrescu wrote:
>>> I'd say let's first have a Pope before becoming more Catholic than
>>> him. -- Andrei
>>
>> I confess that I really don't understand that one.
>
> "More Catholic than the Pope" = overdoing something all too pedantically. What I mean is: let's get things started and if there's any need for isXxx we'll add them. -- Andrei

In principle, I agree with the sentiment, but I would have thought that our experience thus far already showed that being imprecise with code involving compile time introspection was problematic at best. This sort of thing in static ifs probably isn't as bad as it would likely be in template constraints, but it seems like way too often we end up with problems like user code compiling at first and then not compiling later due to a small change in Phobos or dmd, just because someone did something differently from what we expected, and the template constraints or static ifs didn't take it into account properly.

- Jonathan M Davis

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