The rfind challenge

[monarch_dodra]

On Tuesday, 15 January 2013 at 19:44:39 UTC, FG wrote:
> On 2013-01-15 19:00, Andrei Alexandrescu wrote:
>> That's too many. Simpler approaches?
>
>
> Let me give an outside perspective of someone that doesn't work 
> with D all day.
> For forward ranges the original method is fine, but for 
> bidirectional r and e I would expect the following code to 
> somehow just work, but it doesn't:
>
>     auto rfind(R1 r, R2 e) {
>         return retro(findSplitAfter(retro(r), retro(e))[0]);
>     }
>
> Other than the tiny detail of this not working, existing stuff 
> like findSplit, findSplitBefore and findSplitAfter would be 
> enough to define their r* versions.

Well, you just stumbled on the entire problem.

Given a bidirectional range BR, findSplitBefore actually cheats. 
This is the basic algorithm: popFront until you find the what you 
are looking for. Return the found range, as well as "what was 
before"

The problem is that there is no real way to return "what was 
before", so we use a tool called "Take", that adapts a range to 
only hold the first N elements. Basically, it returns "take(br, 
n)". The problem though is that:
a) The type is not BR anymore, but Take!BR
b) Take!BR is not bidirectional.

So basically:
//--------
BR br = BR(1, 2, 3, 4);
result = br.findSplitAfter([3]);
auto lhs = result[0]; //[1, 2]
auto rhs = result[1]; //[4]
//typeof(lhs): Take!BR
//typeof(rhs): BR
//--------

And this is the root problem. As you can see, element 0 is not 
actually a bidirectional range anymore, nor is it of type BR 
either. This "tiny detail" as you say, is actually fundamental ;)

This is why I'd like to find a way to cut bidirectional ranges: 
Not just for r* functions, but also for our everyday functions: 
As you can see, we don't have any way to "findBefore" and store 
the result in a BR. Ouch.

As a user of D, I agree with you that it should "just work". Real 
life is different though :/