On 10/07/2015 07:13 PM, Jonathan M Davis wrote:
> ...
>
> If we _were_ to look at doing something more than straight ranges, we'd
> probably look more at something like Steven's cursors than adding
> iterators, though I think that there's a decent chance that that only
> really helps with containers (it's been a while since I looked at what
> he did with cursors, and I really don't remember the details), though
> for the most part, I think that containers are the primary place where
> ranges tend to get annoying. Algorithms where they're problematic do
> exist, but they seem to be rare.
>
> - Jonathan M Davis

I think the most obvious way to generalize, such that ranges cater to those use cases, is to introduce a type of range that additionally requires the primitives:

full(); // pushFront cannot be called unless false
pushFront(); // restores one element at the front of the range

The idea is:

auto r=..., s=r.save;
assert(r.full);
r.popFront();
assert(!r.full);
r.pushFront();
assert(r.full);
assert(equal(s,r));

This is analogous to list zippers in functional languages in the same way that input ranges are analogous to lists.

Here's the original discussion with Eric's elaborate answer:
http://ericniebler.com/2014/02/21/introducing-iterables/#comment-403

> Because I want to leverage the vast amount of iterator-based code already written, and because in my experience, I don’t find that ranges as primitives solve all the problems that iterators do.

> Many algorithms return positions. These all suffer the same problem as find. One algorithm implementation isn’t sufficient; you need bunches of differently-named algorithms that differ only in the subrange they return.

> As for the political argument: I want ranges in the standard. There is just no way the C++ standardization committee would ever consider a range-only interface.

On Wednesday, 7 October 2015 at 14:59:28 UTC, Trass3r wrote:
> On Tuesday, 6 October 2015 at 22:39:01 UTC, Ulrich Küttler wrote:
>> Yes, this is an explanation. Thanks. So the argument being C++ customs. Now that you mention it, this seems to be the argument in Eric's D4128 paper, too.
>>
>> I was hoping for a somewhat deeper reasoning. Out of curiously, I am still trying to grasp all the implications. Ranges are hard.
>
> Another one is "odd number of iterators algorithms"
>> http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2014/n4128.html#appendix-3-d-ranges-and-algorithmic-complexity
>> D’s choice of algorithmic basis operations is inherently less efficient than C++’s.

Hmm... conceptually a bidirectional range should be able to iterate back and forth:

void is_word_boundary(Bidi r)
{
    bool is_word_prev = r.re.empty ? false : isword(r.re.back);
    bool is_word_this = r.empty ? false : isword(r.front);
    return is_word_prev != is_word_this;
}

auto i = myrange;
for(; !i.empty; i.popFront())
    if( is_word_boundary(i) )
        break;

The backward range can have an input range interface, like retro:

void is_word_boundary(Bidi r)
{
    bool is_word_prev = r.prev.empty ? false : isword(r.prev.front);
    bool is_word_this = r.empty ? false : isword(r.front);
    return is_word_prev != is_word_this;
}

On Thursday, 8 October 2015 at 12:35:08 UTC, Kagamin wrote:
>
> Hmm... conceptually a bidirectional range should be able to iterate back and forth:
>
> void is_word_boundary(Bidi r)
> {
>     bool is_word_prev = r.re.empty ? false : isword(r.re.back);
>     bool is_word_this = r.empty ? false : isword(r.front);
>     return is_word_prev != is_word_this;
> }
>
> auto i = myrange;
> for(; !i.empty; i.popFront())
>     if( is_word_boundary(i) )
>         break;

On Thursday, 8 October 2015 at 12:53:24 UTC, Kagamin wrote:
> The backward range can have an input range interface, like retro:
>
> void is_word_boundary(Bidi r)
> {
>     bool is_word_prev = r.prev.empty ? false : isword(r.prev.front);
>     bool is_word_this = r.empty ? false : isword(r.front);
>     return is_word_prev != is_word_this;
> }

What you're effectively describing is a trio of iterators wrapped to give an interface of two linked ranges. popFront grows the first one and shrinks the second. I'd be interested to see how to construct that, given a generic range as input.

On Thursday, 8 October 2015 at 13:10:24 UTC, John Colvin wrote:
> What you're effectively describing is a trio of iterators wrapped to give an interface of two linked ranges. popFront grows the first one and shrinks the second. I'd be interested to see how to construct that, given a generic range as input.

The C++ example doesn't work with generic iterators, it needs a specific ability to iterate in both directions, hence a bidirectional range.

The way ranges are used for iteration, they can be seen as adapters for iterators providing various consistent interfaces depending on their capabilities. In this example we need a bidirectional range that can go back and forth, one way to do it is to provide undo mechanism like undoPopFront and frontUndoEmpty to allow the range grow back, thus remaining a range that is a list of items and not an iterator. Another way is to provide a reverse range of previously popped items - this can be seen as iterator or not, more like a range with history rather than an undoable input range, so maybe the getter should be `history`.

On Thursday, 8 October 2015 at 14:36:03 UTC, Kagamin wrote:
> On Thursday, 8 October 2015 at 13:10:24 UTC, John Colvin wrote:
>> What you're effectively describing is a trio of iterators wrapped to give an interface of two linked ranges. popFront grows the first one and shrinks the second. I'd be interested to see how to construct that, given a generic range as input.
>
> The C++ example doesn't work with generic iterators, it needs a specific ability to iterate in both directions, hence a bidirectional range.

Of course.

> The way ranges are used for iteration, they can be seen as adapters for iterators providing various consistent interfaces depending on their capabilities. In this example we need a bidirectional range that can go back and forth, one way to do it is to provide undo mechanism like undoPopFront and frontUndoEmpty to allow the range grow back, thus remaining a range that is a list of items and not an iterator.

I much prefer this second version:

> Another way is to provide a reverse range of previously popped items - this can be seen as iterator or not, more like a range with history rather than an undoable input range, so maybe the getter should be `history`.

my question is: How, in practice, does one take a bidirectional range and make one of these new things? I foresee some difficulty, but perhaps I'm just not being imaginative enough.

On Thu, Oct 08, 2015 at 02:46:05PM +0000, John Colvin via Digitalmars-d wrote:
> On Thursday, 8 October 2015 at 14:36:03 UTC, Kagamin wrote:
> >On Thursday, 8 October 2015 at 13:10:24 UTC, John Colvin wrote:
> >>What you're effectively describing is a trio of iterators wrapped to give an interface of two linked ranges. popFront grows the first one and shrinks the second. I'd be interested to see how to construct that, given a generic range as input.
> >
> >The C++ example doesn't work with generic iterators, it needs a specific ability to iterate in both directions, hence a bidirectional range.
> 
> Of course.
> 
> >The way ranges are used for iteration, they can be seen as adapters for iterators providing various consistent interfaces depending on their capabilities. In this example we need a bidirectional range that can go back and forth, one way to do it is to provide undo mechanism like undoPopFront and frontUndoEmpty to allow the range grow back, thus remaining a range that is a list of items and not an iterator.
> 
> I much prefer this second version:
> 
> >Another way is to provide a reverse range of previously popped items - this can be seen as iterator or not, more like a range with history rather than an undoable input range, so maybe the getter should be `history`.
> 
> my question is: How, in practice, does one take a bidirectional range and make one of these new things? I foresee some difficulty, but perhaps I'm just not being imaginative enough.

Bidirectional ranges do have a fundamental lack in their definition, in that the bidirectionality is weaker than the C++ form of bidirectionality.

For example, suppose you're given some bidirectional range r, with
swappable elements. Clearly, reverse(r) is easily implementable (just
swap .front and .back, then popFront() and popBack() until the range is
empty).

However, suppose you want to reverse the last n elements of r. How would you do it? Conceptually speaking, if the range is bidirectional, then its last segment of n elements ought to be bidirectional too, right? However, there is currently no (easy) way to get a bidirectional subrange out of r, using the current range primitives.

One brute force way to do it, is to iterate a .save'd copy of r (since bidirectionality implies forward range) from the front, until there are only n elements left, then perform the reverse() operation. However, this is horribly inefficient if n is relatively small w.r.t. the total number of elements in r. It gets worse if r does not have .length, so you may have to iterate over *two* .save'd copies of r so that you know the subrange you end up with has exactly n elements (since you can't tell how many elements are in the subrange until you reach the end).

Ideally, though, we'd like to be able to iterate from the end of r, so that we only incur the cost of calling .popBack n times. However, no amount of trickery with the current bidirectional range API is going to get you this subrange by iterating from the back. The problem is that once you call .popBack n times, there's no way to turn .back into the new .front of the subrange. You can't unpop .back once you've called popBack(), so you can't implement .front on the subrange.  Whereas with iterators, you *could* just do iter-- n times, then use iter with the original .end() to form the n element subrange.

So D's bidirectional ranges are inherently weaker than a pair of C++ bidirectional iterators, because D's bidirectional ranges are, under the hood, a pair of *uni-directional* iterators in opposite directions. Once you advance either iterator, you can't go back anymore without resorting to ugly inefficient hacks (e.g., allocate a stack of .save'd positions), whereas in C++ both ends are bidirectional, and can go forward/back at anytime.

If we were to add an .unpop primitive to bidirectional ranges, though, then we could solve this problem. However, I'm not sure how this fits in with the overall concept of ranges.


T

-- 
Век живи - век учись. А дураком помрёшь.

On Thursday, 8 October 2015 at 14:46:07 UTC, John Colvin wrote:
>> Another way is to provide a reverse range of previously popped items - this can be seen as iterator or not, more like a range with history rather than an undoable input range, so maybe the getter should be `history`.
>
> my question is: How, in practice, does one take a bidirectional range and make one of these new things? I foresee some difficulty, but perhaps I'm just not being imaginative enough.

It should be probably possible to undo the history range too, but it would be future, so it looks like there can be a better interface: beforeFront returns a normal bidirectional range of items before current front, afterBack returns a normal bidirectional range of items after back, so r.beforeFront.back is an item right before current front. This makes it more symmetric, and properties return ranges of the same type as the source range, but I don't know how to name such a range :) A range with shadows? Those ranges can be seen as shadows (before and after).

Yes D's bidirectional range provides less guarantees than C++ bidirectional iterator, but you can build it on a random access range that provides more guarantees than bidirectional iterator, or you can provide a range with shadows, that provides as much guarantees as C++ bidirectional iterator, no less, no more.

OK, I thought a little more and... Name: divisible range. It occurred to me that we only need to reverse logic of bidirectional range: while bidirectional range is a pair of ranges that shrink towards each other, divisible range is divided into two ranges that shrink away from each other. The C++ example implies that begin and end must be bidirectional iterators, but that is not really needed as they are used for bounds checks only, ranges have empty for that, so the divisible range can be a normal input range that provides access to its left part that shrinks from back (backward input range?) and provides access to the right part.