On 10/25/2015 08:33 PM, Andrei Alexandrescu wrote:
> 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
>

As I mentioned, the cheap way out for performance would be to provide what you suggested (persistent topology, arbitrary reference access to slots). Users can then use type qualifiers at their own discretion. There could probably even be short aliases to automatically have immutable elements. What's important is that use cases for mutable elements are not ruled out. They don't necessarily need to be on the path of least resistance.

On Sunday, 25 October 2015 at 15:42:02 UTC, Andrei Alexandrescu wrote:
> Jonathan, do you have a link to your work?

Sorry, but no. I haven't mucked around with this issue recently, and whatever I have left on the topic is either buried in a newsgroup post somewhere or buried on my hard drive somewhere where I wouldn't know where to find it. Searching on the newsgroup for discussions on tail-const would find stuff related to this if you want to go spelunking, since it's the tail-const issues where the fact that const(Foo!T) and Foo!(const T) aren't related typically comes up and likely causes the largest problems.

The EMSI containers may have some interesting stuff with regards to the problem, since I know that those guys tried very hard to be able to support tail-const ranges.

The main thing that I recall is that if you want to be able to get a tail-const range from a const range, you have to use a static if to protect the const opSlice declaration so that you don't end up with a recursive template instantiation (since it has to return another instantiation of the range's template). And even then, an opSlice with no arguments isn't technically a standard range function, because none of the range traits require it (so you can't rely on a range having it). Rather, it's a container function for getting a range. And even if it were a range function, it wouldn't get the special treatment that arrays get when being passed to a templated function (IFTI infers an array's type as being a tail-const slice, which doesn't happen with anything else), and even if it did, a const range wouldn't implicitly convert to its tail-const variant without an alias this, which is likely to create a whole other set of problems - particularly since implicit conversions tend to wreak havoc in generic code.

Handling tail-const with ranges in a manner consistent with arrays and supporting $ with ranges are probably the two big places that ranges can't currently emulate the behavior of arrays. The $ problem is technically solvable as-is, but without some form of https://issues.dlang.org/show_bug.cgi?id=7177 being implemented, changing hasSlicing or isRandomAccessRange to require that a range works with $ would likely break too much code, so no range-based code can really using $ unless it explicitly checks for it. However, I'm not sure that the tail-const problems is solvable without further language improvements. We likely need some sort of standard way to convert a const(Foo!T) to a Foo!(const T) - possibly via opSlice, since it wouldn't make sense for something that wasn't emulating an array. And we might need to make changes to IFTI so that it infers tail-const for ranges (at least if they provide such a conversion), but I'm not sure what the implications of that are.

There's also the issue of accidentally slicing ranges (e.g. https://issues.dlang.org/show_bug.cgi?id=14619 ) which can cause incorrect behavior in at least some cases, depending on the range type - and if a range is a reference type, then slicing it would be akin to saving it, which could mean allocating. So, unlike with arrays, we probably don't want ranges in general to get sliced just because they're passed to a function, meaning that we may just want IFTI to not play fun games with ranges and let arrays be special there.

In any case, I should probably try and find time soon to sit down and at least go over the issues in detail again so that I'm clearer on them and could possibly present a DIP intended to resolve them. I haven't dug through them recently, and my general approach up until now when I've needed to actually get work done has been to just not use const or inout with ranges.

- Jonathan M Davis

On Wednesday, 21 October 2015 at 18:49:26 UTC, Andrei Alexandrescu wrote:
> On 10/21/2015 12:25 PM, Jonathan M Davis wrote:
>> My experience with immutable containers is that their performance is
>> trash precisely because you can't mutate them.
>
> That's actually the experience in the Scala community. Over and again people start with immutable containers all over the place because they're cool, and end up with mutable containers because they work. -- Andrei

Ranges and loops. Same story. Ranges are cool, loops get stuff done.

On 10/26/2015 08:31 PM, Ulrich Küttler wrote:
> On Wednesday, 21 October 2015 at 18:49:26 UTC, Andrei Alexandrescu wrote:
>> On 10/21/2015 12:25 PM, Jonathan M Davis wrote:
>>> My experience with immutable containers is that their performance is
>>> trash precisely because you can't mutate them.
>>
>> That's actually the experience in the Scala community. Over and again
>> people start with immutable containers all over the place because
>> they're cool, and end up with mutable containers because they work. --
>> Andrei
>
> Ranges and loops. Same story. Ranges are cool, loops get stuff done.
>

This kind of reasoning sounds cool but is ultimately misguided.
(I don't think the stories are even analogous.)

Persistent containers have a /different interface/ than mutable containers and hence can be used in different algorithms, where they can help getting low asymptotic resource usage. Obviously there is not much point in using persistent containers just because one considers them "cool" if what one really wants is a mutable container.

Ranges can be iterated, loops iterate them. If one wants to get stuff done, one uses library primitives when they apply and implements the remaining functionality oneself. When one notices that certain patterns begin to repeat, one will sometimes take a short time to factor them out in order to make progress faster. If they are patterns of iteration, this means writing an opApply or sometimes a range.

On Monday, 26 October 2015 at 19:31:26 UTC, Ulrich Küttler wrote:
> On Wednesday, 21 October 2015 at 18:49:26 UTC, Andrei Alexandrescu wrote:
>> On 10/21/2015 12:25 PM, Jonathan M Davis wrote:
>>> My experience with immutable containers is that their performance is
>>> trash precisely because you can't mutate them.
>>
>> That's actually the experience in the Scala community. Over and again people start with immutable containers all over the place because they're cool, and end up with mutable containers because they work. -- Andrei
>
> Ranges and loops. Same story. Ranges are cool, loops get stuff done.

Heavily disagree. If ranges are only cool, java 8 streams wouldn't be so massively successful and ranges wouldn't be part of C++17. D's ranges are one of the main reasons I use D.

On Monday, 26 October 2015 at 19:31:26 UTC, Ulrich Küttler wrote:
> On Wednesday, 21 October 2015 at 18:49:26 UTC, Andrei Alexandrescu wrote:
>> On 10/21/2015 12:25 PM, Jonathan M Davis wrote:
>>> My experience with immutable containers is that their performance is
>>> trash precisely because you can't mutate them.
>>
>> That's actually the experience in the Scala community. Over and again people start with immutable containers all over the place because they're cool, and end up with mutable containers because they work. -- Andrei
>
> Ranges and loops. Same story. Ranges are cool, loops get stuff done.

You are conflating ranges and iteration. A range needs something to drive it, whether it be an explicit loop or some higher abstraction from std.algorithm.

bye,
lobo

On Monday, 26 October 2015 at 20:46:21 UTC, Timon Gehr wrote:
> On 10/26/2015 08:31 PM, Ulrich Küttler wrote:
>> On Wednesday, 21 October 2015 at 18:49:26 UTC, Andrei Alexandrescu wrote:
>>> On 10/21/2015 12:25 PM, Jonathan M Davis wrote:
>>>> My experience with immutable containers is that their performance is
>>>> trash precisely because you can't mutate them.
>>>
>>> That's actually the experience in the Scala community. Over and again
>>> people start with immutable containers all over the place because
>>> they're cool, and end up with mutable containers because they work. --
>>> Andrei
>>
>> Ranges and loops. Same story. Ranges are cool, loops get stuff done.
>>
>
> This kind of reasoning sounds cool but is ultimately misguided.
> (I don't think the stories are even analogous.)
>

Nobody argues against ranges.

The argument is: Designing range-based code results in something very different from traditional loop-based code. There are very good reasons why the effort is worthwhile, still, the effort is real. (See the calendar example.) Even those library primitives do not come for free.

The same is true about containers. The container variant is a design choice, not an implementation detail. Now, are persistent containers worth the effort? What would a design based on persistent containers look like? Is there a good way to implement them in D?

Who knows.