On 06/23/2013 10:54 AM, monarch_dodra wrote:
> Not quite, it returns an object that returns those items when iterated on. But it is not the same type.

Why does that matter to you?  One of the nice things about ranges is that the strict object type seems to matter less than the interface and the type that .front returns.  E.g. someRange.takeExactly(10) is not of the same type as someRange, but I find that largely irrelevant when using it.

Not intending to dismiss your concern, just curious to understand your requirements.

On Sunday, 23 June 2013 at 11:06:07 UTC, Joseph Rushton Wakeling wrote:
> On 06/23/2013 10:54 AM, monarch_dodra wrote:
>> Not quite, it returns an object that returns those items when iterated on. But
>> it is not the same type.
>
> Why does that matter to you?  One of the nice things about ranges is that the
> strict object type seems to matter less than the interface and the type that
> .front returns.  E.g. someRange.takeExactly(10) is not of the same type as
> someRange, but I find that largely irrelevant when using it.
>
> Not intending to dismiss your concern, just curious to understand your requirements.

That's a very "I have a range and want to iterate on it" view. Which is fine and it works in that case (and I have no problems there).

But as soon as you need an algorithm that actually *handles* ranges: swaps them, merges them, searches in them and splices them, then things get hairy.

For example, try implementing a sort (either merge or q) with a non-sliceable range... very very hard...

On Sunday, 23 June 2013 at 11:04:17 UTC, monarch_dodra wrote:
> It's a bit more than that, it's also about limiting template bloat. For example:

To mitigate template bloat, you can downgrade compile-time polymorphism to runtime polymorphism. D provides the facilities for this, e.g. using the above-mentioned pre-made InputRange interface, or using the new `wrap` template from std.typecons in git / 2.064.

> It also means iteration will be more expensive than necessary (take will compare both length and empty).

FWIW, `takeExactly` does not.

> Also, and this is subtle: If you use take, your range will have a fixed size, whereas a "true" bidirectional range will be defined by a start and end point. For example, with the above find split, taken from a DList:
> If I add elements to the DList, a DList.Range will "grow" to accomodate new elements that where inserted between its bounds. Take!(DList.Range), on the other hand, will *not* grow, and as elements are inserted, the back elements will be pushed outside of the Range.

Then the answer would be to not use `take` on ranges that might change. `take` is one way to limit the length of a range (by a number), but it is not the only way to limit the length of a range.

> For example, try implementing a sort (either merge or q) with a non-sliceable range... very very hard...

Are we talking about random-access range types that do not implement opSlice? Wouldn't it be easy to create a wrapper range on top of any random-access range that does implement opSlice?

Otherwise, I don't see how it's even possible (or desirable) to sort a non-random-access range.

> It might not sound like much, but have you *tried* using DList?

No. I clearly do not have the same experience with using ranges as you. It's just that the problems that you have presented, as you have presented them, appeared to me to have obvious solutions.

On 06/23/2013 12:34 PM, monarch_dodra wrote:
> That's a very "I have a range and want to iterate on it" view. Which is fine and it works in that case (and I have no problems there).
> 
> But as soon as you need an algorithm that actually *handles* ranges: swaps them, merges them, searches in them and splices them, then things get hairy.
> 
> For example, try implementing a sort (either merge or q) with a non-sliceable range... very very hard...

I would take that as a fault in the adaptor, surely?  A well designed implementation of take or takeExactly or until or any of these other range adaptors ought to preserve as many properties of the input range as possible.

On 6/23/13 4:04 AM, monarch_dodra wrote:
> R range;
> auto r3 = findSplit(range);
> void do_it(r3[0]);
> void do_it(r3[1]);
> void do_it(r3[2]);
>
> This will actually instantiate 2 different do_it functions.

Yah, this is a good summary. If individual iterators are accessible, findSplit can return three ranges of the same type. Otherwise, generally findSplit must return ranges of distinct types.

Note, however, that if the initial range is strictly forward, the three resulting range may not have the same type as the initial range. As a simple example, findSplit over a singly-linked list cannot return three singly-linked lists.

(I don't think template bloat is the main problem here, instead a sort of matter of principles.)

Again, we can make things work by introducing a primitive for bidirectional ranges:

R before(R r1, R r2);

Assuming r2 is reachable from r1, returns the portion of r1 that lies before r2. (Definition: a range r2 is reachable from another range r1 if calling r1.popFront() repeatedly will at some point make r1.front and r2.front refer to the same value.)


Andrei

23-Jun-2013 06:13, Brad Anderson пишет:
> On Sunday, 23 June 2013 at 01:34:53 UTC, Andrei Alexandrescu wrote:
>> On 6/22/13 2:58 PM, monarch_dodra wrote:
>>> long story short: we don't have rfind. C++ does.
>>
>> We do, just that it's for random-access ranges. C++ offers it for
>> bidirectional ranges too. We could of course support it if
>> bidirectional ranges were required to have something like
>> r1.before(r2) that, assuming r2 is reachable from r1, returns the
>> portion in r1 that's before r2.
>>
>> Andrei
>
> That sounds like exactly what I needed for a version of toUpper I was
> playing with that added support for output ranges.
>
> The implementation is rather trivial:
>
> Writer toUpper(S, Writer)(S s, Writer w) @trusted

And I would love to add functions of this style to the new std.uni especially as toLower is a fair bit more tricky then this.

>      if(isSomeString!S)
> {
>      size_t count = 0;
>      foreach (c, i; s)
>      {
>          if (std.uni.isLower(c))
>          {
>              c = std.uni.toUpper(c);
>          }
>          put(w, c);
>          count = i;
>      }
>
>      return w;
> }
>
> Works just fine with something like Appender. The problem is that if you
> pass in dynamic or static array slice to store the result in you have no
> way of knowing how much of the target array was filled by the function.
> You could use save() and keep track of how many bytes were consumed and
> return a slice of that size but that feels very clunky (and could be
> tricky to implement correctly if the input string is a different
> encoding than the output range).


-- 
Dmitry Olshansky

On 6/23/13 7:39 AM, Andrei Alexandrescu wrote:
> Again, we can make things work by introducing a primitive for
> bidirectional ranges:
>
> R before(R r1, R r2);
>
> Assuming r2 is reachable from r1, returns the portion of r1 that lies
> before r2. (Definition: a range r2 is reachable from another range r1 if
> calling r1.popFront() repeatedly will at some point make r1.front and
> r2.front refer to the same value.)

The question is, should we add this primitive? There's discussion on adding ranges to C++, and discussion inevitably reaches an impasse when it gets to this particular matter.

I personally think we should and am amazed that we made it so far without that primitive. However, unlike others, I don't think it's an essential matter. Some C++ people tend to be apprehensive when they figure they can do something with iterators that's not doable with ranges.


Andrei

On Sunday, 23 June 2013 at 14:47:17 UTC, Andrei Alexandrescu wrote:
> On 6/23/13 7:39 AM, Andrei Alexandrescu wrote:
>> Again, we can make things work by introducing a primitive for
>> bidirectional ranges:
>>
>> R before(R r1, R r2);
>>
>> Assuming r2 is reachable from r1, returns the portion of r1 that lies
>> before r2. (Definition: a range r2 is reachable from another range r1 if
>> calling r1.popFront() repeatedly will at some point make r1.front and
>> r2.front refer to the same value.)
>
> The question is, should we add this primitive? There's discussion on adding ranges to C++, and discussion inevitably reaches an impasse when it gets to this particular matter.
>
> I personally think we should and am amazed that we made it so far without that primitive. However, unlike others, I don't think it's an essential matter. Some C++ people tend to be apprehensive when they figure they can do something with iterators that's not doable with ranges.
>
> Andrei

Just for the record (because I'm the one that usually brings this up), I think ranges are a big win overall. I just find it frustrating every time the "always shrink never grow" problem gets in my way of writing simple and efficient algorithms.

"before" might work, but it would also introduce a new primitve, as well as a new trait ("isSpliceable?"). There is a real gain to cost ratio, which I'm not sure is worth it. The semantics for it would also be kind of complicated: you'd have "before", "after", "beforeIncluding", "merge"...

I'm wondering if something along the lines of an "iterable" range might not be much more simple? Probably not :(

On Sunday, 23 June 2013 at 14:47:17 UTC, Andrei Alexandrescu wrote:
> On 6/23/13 7:39 AM, Andrei Alexandrescu wrote:
>> Again, we can make things work by introducing a primitive for
>> bidirectional ranges:
>>
>> R before(R r1, R r2);
>>
>> Assuming r2 is reachable from r1, returns the portion of r1 that lies
>> before r2. (Definition: a range r2 is reachable from another range r1 if
>> calling r1.popFront() repeatedly will at some point make r1.front and
>> r2.front refer to the same value.)
>
> The question is, should we add this primitive? There's discussion on adding ranges to C++, and discussion inevitably reaches an impasse when it gets to this particular matter.
>
> I personally think we should and am amazed that we made it so far without that primitive. However, unlike others, I don't think it's an essential matter. Some C++ people tend to be apprehensive when they figure they can do something with iterators that's not doable with ranges.
>
>
> Andrei

BTW, kind of off topic, but since we are talking about bidirectional ranges, and DList is the most relevant object: Do you think you would have time to review my DList fix?
https://github.com/D-Programming-Language/phobos/pull/953

As Dmity said: "are we all in agreement to pull this in before release?" ; which was 6 months ago :/ I think its time we deal with DList's issues.

On 6/23/13 9:33 AM, monarch_dodra wrote:
> BTW, kind of off topic, but since we are talking about bidirectional
> ranges, and DList is the most relevant object: Do you think you would
> have time to review my DList fix?
> https://github.com/D-Programming-Language/phobos/pull/953
>
> As Dmity said: "are we all in agreement to pull this in before release?"
> ; which was 6 months ago :/ I think its time we deal with DList's issues.

LGTM modulo some nits. We should take a close look at all containers.

Andrei