www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.learn - Best way to test predicate against a range

reply Jonathan M Davis <jmdavisprog gmail.com> writes:
Okay. The functions in std.algorithm are quite powerful, but sometimes you =
have=20
to play around with them a bit to figure out how to do exactly what you're =
trying=20
to do. Sometimes it's a matter of figuring out exactly which algorithm real=
ly=20
does what you want, and sometimes it's a matter of figuring out how to cont=
ort=20
one of them to do what you want.

=46or example, there are two functions that I'd like to be have: all() and =
any().=20
That is, I want a function which checks a predicate against a range and ret=
urns=20
whether all elements in that range satisfy the predicate, and I want a func=
tion=20
that checks a predicate against a range and returns whether any element sat=
isfies=20
the predicate. Ideally, all() would shortcut if it found even one element w=
hich=20
didn't satisfy the predicate, and any() would shortcut if it found even one=
 that=20
did.

=46rom the looks of it, canFind() is essentially any(), so that new additio=
n to=20
std.algorithm should deal with that. Previously, the best that I could figu=
re out=20
was to use find() for that and check whether the returned range was empty, =
which=20
wasn't as efficient or elegant. So, that's a nice addition to phobos.

The problem is all(). I can't find any function which seems to effectively =
do=20
all(). The best that I can think of is to use canFind() with a negated=20
predicate, so if it returns true, it found an element which satisfied the=20
negation of the predicate and therefore didn't satisfy the predicate. Howev=
er,=20
ideally, I'd be able to give a function the exact predicate that I'm lookin=
g for=20
without having to contort the predicate to be able to use the function that=
 I=20
want. It feels like I'm dealing with only a || and I don't have a &&.

Is there a function in phobos which can't be used as an all(), and I'm just=
=20
missing it, or is there at least a better solution than using canFind() wit=
h a=20
negated predicate, or is canFind() with a negated predicate the best that t=
here=20
is at the moment?

=2D Jonathan M Davis


P.S. By the time that std.algorithm is completed, I suspect that it would b=
e=20
possible to write a small book on the myriad of ways to use it. It's extrem=
ely=20
powerful and not really all that hard to use, but sometimes it takes a fair=
 bit=20
of thinking (for me at least) to figure out which function to use to do=20
something. Hopefully I get better at it with time at least.
Jun 26 2010
next sibling parent reply BCS <none anon.com> writes:
Hello Jonathan,


 For example, there are two functions that I'd like to be have: all()
 and any(). That is, I want a function which checks a predicate against
 a range and returns whether all elements in that range satisfy the
 predicate, and I want a function that checks a predicate against a
 range and returns whether any element satisfies the predicate.
 Ideally, all() would shortcut if it found even one element which
 didn't satisfy the predicate, and any() would shortcut if it found
 even one that did.


The trivial solution (no shortcuting) would be to map the predicate and reduce 
via 'and' or 'or'.

-- 
... <IXOYE><
Jun 26 2010
parent Philippe Sigaud <philippe.sigaud gmail.com> writes:
On Sun, Jun 27, 2010 at 08:07, BCS <none anon.com> wrote:


 Hello Jonathan,


  For example, there are two functions that I'd like to be have: all()

 and any(). That is, I want a function which checks a predicate against
 a range and returns whether all elements in that range satisfy the
 predicate, and I want a function that checks a predicate against a
 range and returns whether any element satisfies the predicate.
 Ideally, all() would shortcut if it found even one element which
 didn't satisfy the predicate, and any() would shortcut if it found
 even one that did.


 The trivial solution (no shortcuting) would be to map the predicate and
 reduce via 'and' or 'or'.



Or do a new version of reduce that stops the reducing on a certain condition

reduceWhile(alias reducer, alias predicate) {... reduce using reducer, as
long as predicate holds }

That would be a nice addition to std.algo. The question is: what should test
the predicate? The last returned value, the entire result being created?



As an asideJonathan, you may be interested in using some of the algorithms
here:

http://www.dsource.org/projects/dranges

'all' and 'some' are in the 'predicates' module. They accept predicates of
any arity (even 0!), because I wanted to test for increasing numerical
ranges, like this :

auto isGrowing = all ! "a<b" (range);

Note that the fact of accepting variable-arity predicates represents 90% of
the complexity, because a simple all is:

import std.functional: unaryFun;
import std.range: isInputRange;

bool all(alias predicate, R)(R range) if (isInputRange!R)
{
    foreach(elem; range)
    {
        if (!unaryFun!predicate(elem)) return false;
    }
    return true;
}
// warning : untested.

usage:

auto a = all ! "a<0" (range)

or

auto a = all ! foo (range)


Philippe
Jun 27 2010
prev sibling parent bearophile <bearophileHUGS lycos.com> writes:
Jonathan M Davis:


 Okay. The functions in std.algorithm are quite powerful, but sometimes you
have 
 to play around with them a bit to figure out how to do exactly what you're
trying 
 to do.


Some of them need to be improved in their concept and API. Some of them are
awkward to use or they are not the most handy. They are not battle-tested at
all, the best group of functions is yet to be found.

Bye,
bearophile
Jun 27 2010