Why does `filterBidirectional` exist, and why isn't it called `filter`?

[FeepingCreature]

On Thursday, 9 March 2023 at 13:16:07 UTC, Steven Schveighoffer 
wrote:
> On 3/9/23 3:06 AM, FeepingCreature wrote:
>> Yes I know the stated reason, to save time initializing the 
>> range in `filter`.
>> 
>> You know what I did because we didn't know 
>> `filterBidirectional` existed?
>> 
>> I literally *walked the entire range* returned by `filter` to 
>> find the last matching element.
>
> Why not `rng.retro.filter`?

`retro` changes the semantics of the range, which often 
represents business data. Thinking about the underlying model is 
complicated enough without throwing in "But consider: what if the 
elements were in reverse order".

>
>> `filter` should expose `back`. By all means, let `back` lazily 
>> initialize, but I don't understand how `filterBidirectional` 
>> was ever considered acceptable. Since when do we sacrifice 
>> ease of use for performance? I mean, since 2011 apparently. - 
>> This is bad ergonomics, bad discoverability and bad API 
>> design. `filterBidirectional` delenda est.
>
> This has been a constant debate -- should ranges be allowed to 
> lazily initialize on the first call to front (or back)?
>
> I'd say no. back/front shouldn't be modifying operations. I 
> dislike the idea of storing a "was initialized" flag and having 
> to check that on every call.
>
> That being said, there's no formal requirement for it. It's 
> just a convention I think Phobos should stick to for its 
> included ranges.
>
> -Steve

Sure: so precompute both `back` and `front`, every `filter` call. 
No caching. This isn't done right now because the language 
presumes, arbitrarily, that you won't care about `back`. That's 
what I meant by sacrificing convenience for performance. Just do 
what `filterBidirectional` does, every time, and have the current 
`filter` be the odd one out. `filterForward` or whatever.

(I think the best way to go, in truth, is to *preinitialize 
front* and *cache back*. But that solution, much as I think it is 
optimal for all involved interests, is very hard to love.)

That said, I think the range API has a fundamental problem here. 
`filter` pre-initializes `front` on every access, because it 
reasonably presumes that we will then want to query it. However, 
it cannot rely on this. If we were *guaranteed* that every access 
to `popFront` would alternate with at least one access to 
`front`, and conversely `back` with `popBack`, we could just 
reduce `popBack` to `nextRange.popBack` and do the rest of the 
popping in `back`! Then in the fast case (one access to each, in 
turn) we would not waste any check. And the actual `filter` call 
would always be constant-time.