Re: [boost] AlRangeExandrescu?

Subject: Re: [boost] AlRangeExandrescu?
From: Andrei Alexandrescu (andrei_at_[hidden])
Date: 2009-07-23 11:38:41

Thorsten Ottosen wrote:
 > David Abrahams skrev:
 >> Hi Neil,
 >>
 >> I'm sure someone already spoke to you about this, but just in case:
 >> Andrei Alexandrescu gave a very interesting presentation at BoostCon
 >> that was based on a "ranges only" approach that should eliminate
 >> issues like this one:
 >>
 >>   2: return type specification for find() etc
 >>   ===========================================
 >>   There where no major objection to the mechanism, but some found
 >>   the syntax ugly. I believe the suggested syntax (e.g.)
 >>
 >>    boost::find[_f,_e]( range, x )
 >>
 >>    boost::find[_f+1,_e]( range, x )
 >>
 >>
 >> He says he's implemented a superset of the STL algorithms with it so
 >> we know the expressive power is fairly complete.
 >
 > If I remember correctly, he claims that his return of find() is the
 > "correct" one. I think that is plain wrong, as the syntax above shows
 > that there are many useful return ranges, perhaps with an obvious 
default.

(Thanks Dave for pointing out this thread to me.)

I can think of four useful subranges you might want to look at when 
searching linearly: the range before the found element (including it or 
not) and the one after the found element (including it or not).

If find() is to work on most ranges, it needs to return the range 
starting with the found element. Then it's easy to derive the range 
after the found element by simply popping one element off the range.

There remains the case when the range preceding the found element is 
needed. Requiring find to be able to do that reduces the generality of 
find(), so the principled approach is to confine that task to a 
different function. Without having looked at RangeEx, I infer from the 
code above that for example find[_b, _f] would only work on forward 
iterators and better, whereas find[_f, _e] would also work on input 
iterators.

During my talk at Boost this same issue was brought again, so after 
thinking some more about it I found what I think is the principled 
solution: define a different function that returns the range before the 
found element. That function is called until().

Surprisingly, until() also works on input ranges! It works because it 
finds the element lazily - it returns a range that tests for termination 
condition in its .empty() test. So until() returns a range that iterates 
the original passed-in range until the sought element is found, at which 
time until() reports termination.

So one design is to define find[_b, _f] that works with forward ranges 
and find[_f, _e] that works with input ranges. With the design proposed 
above we have until that works with input ranges and find that works 
with input ranges. That is a net expressiveness win, and the cost is the 
necessity of defining a new type of range (the one returned by until).

Again, I haven't looked at find[] and RangeEx so please apologize if I 
mis-inferred how it works.

Andrei