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

[Steven Schveighoffer]

On 3/9/23 11:44 AM, FeepingCreature wrote:
> 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".

Well, walking the entire range to find the last one doesn't imply that 
ordering matters at all. You are just looking for the last one.


>>> `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.
>>
> 
> 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 would be fine with that. But in truth, this is simply an acceptance of 
the status quo, just with different names.

> (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.)

I prefer to have control over all the capabilities. If there is going to 
be significant cost for something I won't actually use, I'd rather avoid it.

Allowing composability might be the way to go.

> 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.
> 

`front` and `empty` are semantically non-mutating properties. Calling 
`front` and/or `empty` as many times as you want should not alter any 
values until you call `popFront`.

I prefer them to be *actually* non-mutating as well.

Delaying construction seems like the better option, and having such a 
wrapper solves all those problems for those who want lazy, without 
imposing on users who are intending to just use a range as it's intended.

-Steve