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
