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.


T

-- 
The early bird gets the worm. Moral: ewww...

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

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

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

-Steve

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.


T

-- 
Don't drink and derive. Alcohol and algebra don't mix.

On Friday, 16 March 2018 at 17:41:22 UTC, 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.
>
>
> T

I've implemented these by hand as special cases of count named countsExactly, countsAtLeast, countsAtMost beginning at

https://github.com/nordlow/phobos-next/blob/3682da65ecb8497946379b41d8027b8292c635a1/src/algorithm_ex.d#L1941

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.