Short-circuit range counting algorithm?

[Andrei Alexandrescu]

On 03/16/2018 03:10 PM, H. S. Teoh wrote:
> On Fri, Mar 16, 2018 at 02:58:36PM -0400, Steven Schveighoffer via Digitalmars-d wrote:
>> On 3/16/18 2:07 PM, Seb wrote:
>>> On Friday, 16 March 2018 at 17:50:37 UTC, Andrei Alexandrescu wrote:
>>>> On 3/16/18 1:41 PM, H. S. Teoh wrote:
>>>>> Given a forward range r, I want to test whether it has exactly n
>>>>> elements that satisfy some given predicate pred.  Is it possible
>>>>> to do this using current Phobos algorithms such that it does not
>>>>> traverse more members of the range than necessary?
>>>>>
>>>>> The naïve solution `r.count!pred == n` walks the entire range,
>>>>> even though it may already have seen n+1 elements that satisfies
>>>>> pred, and therefore should already know that the answer must be
>>>>> false.
>>>>
>>>> r.count!pred.walkLength(n) == n
>>>
>>> Shouldn't this be using filter (count is eager)?
>>>
>>> r.filter!pred.walkLength(n) == n
>>
>> r.filter!pred.walkLength(n + 1) == n
> [...]
> 
> Aha, so the trick is the 2-argument overload of walkLength.  That's what
> I was looking for.  Thanks!
> 
> And yes, it should be .walkLength(n+1) because otherwise you don't know
> if the actual count is >n.

Noice, thanks for the correx all.