Proposal: takeFront and takeBack

[Dmitry Olshansky]

On 03-Jul-12 20:37, Jonathan M Davis wrote:
> This seems like it probably merits a bit of discussion, so I'm bringing it up
> here rather than simply opening a pull request.
>
> At present, for some ranges (variably-lengthed ranges such as strings in
> particular), calling front incurs a cost which popFront at least partially
> duplicates. So, the range primitives are inherently inefficient in that they
> force you to incur that extra cost as you iterate over the range. Ideally,
> there would be a way to get front and pop it off at the same time so that you
> incur the cost only once (either that or have front cache its result in a way
> that lets it avoid the extra cost in popFront when popFront is called - though
> that wouldn't work with strings, since for them, the range primitives are free
> functions). So, I'm proposing takeFront and takeBack:
>

I was about to propose fetchFront/fetchBack with similar semantics. 
Thanks for pushing this proposal it looks good.

My initial intent however was to add Variable Length Range as a concept. 
... Now I think binary predicate hasFetch a-la hasSlicing is better.

> https://github.com/jmdavis/phobos/commit/5bfa8126fa14a539fee67807821ec0a10503f27b
>
> For most ranges, takeFront does this:
>
> auto takeFront(R)(ref R range)
>      if(isInputRange!R && !isNarrowString!R)
> {
>      assert(!range.empty);
>      auto retval = range.front;
>      range.popFront();
>      return retval;
> }
>

Aye. Yet there is indeed a problem with pseudo-ranges that reuse 'slot' 
for front on each popFront. Well they always been brittle.

>
> So, for strings, it'll be more efficient to use takeFront than calling front and
> popFront separately. The idea then is that any user-defined range which can
> implement takeFront more efficiently than the default will define it. Then range-
> based functions use takeFront - e.g. range.takeFront() - and if the user-
> defined range implements a more efficient version, that one is used and they gain
> the extra efficiency, or if they don't, then the free function is used with
> UFCS, and they incur the same cost that they'd incur calling front and
> popFront separately. So, it's invisible to range-based functions whether a
> range actually implements takeFront itself. takeBack does the same thing as
> takeFront but it does it with back and popBack for bidirectional ranges.
>
> I _think_ that this is a fairly clean solution to the problem, but someone
> else might be able to point out why this is a bad idea, or they might have a
> better idea. And this will have a definite impact on how ranges are normally
> used if we add this, so I'm bringing it up here for discussion. Opinions?
> Thoughts? Insights?
>
> Oh, and if we go with this, ideally, the compiler would be updated to use
> takeFront for foreach instead of front and popFront if a range implements it
> (but still do it the current way if it doesn't). So, if typeof(range)
> implements takeFront,

Right. In fact as we've seen above with e.g. stdin.byLine not every 
range can do fetchFront correctly so it's a strict subset. That was the 
reason for current trio of basic operations BTW.


-- 
Dmitry Olshansky