any() and all() on empty list?

Tim Peters tim.peters at gmail.com
Wed Mar 29 08:46:39 CEST 2006


[Steve R. Hastings]
> So, Python 2.5 will have new any() and all() functions.
> http://www.python.org/dev/peps/pep-0356/
>
>
> any(seq) returns True if any value in seq evaluates true, False otherwise.
>
> all(seq) returns True if all values in seq evaluate true, False otherwise.
>
> I have a question: what should these functions return when seq is an empty
> list?

Here, from the current development trunk, is what they _do_ return:

Python 2.5a0 (trunk:43410M, Mar 28 2006, 16:42:49) ...
Type "help", "copyright", "credits" or "license" for more information.
>>> any([])
False
>>> all([])
True

> Here is Guido's original article where he suggested any() and all():
> http://www.artima.com/weblogs/viewpost.jsp?thread=98196
>
> He offered this sample code for the semantics of any() and all():
>
>
>
> def any(S):
>     for x in S:
>         if x:
>             return True
>     return False
>
> def all(S):
>     for x in S:
>         if not x:
>             return False
>     return True
>
> ...
>|
> I'm completely on board with the semantics for any().  But all() bothers
> me.  If all() receives an empty list, it will return True,

Yes.

> and I don't like that.

Tough ;-)

> To me, all() should be a more restrictive function than any(),
> and it bothers me to see a case where any() returns False but all()
> returns True.

There are deeper principles at work:  so that endcases work out as
smoothly as possible, a "reduction" function applied to an empty
collection always arranges to return the identity element for the
reduction operation.  This is the reason that sum([]) returns 0, for
example:  0 is the identity element for addition, meaning that x+0=x
for all x.

Other useful identities follow from this, and from the associativity
of most reduction operations.  For example, sum(seq) = sum(seq[:i]) +
sum(seq[i:]) for any i >= 0, even if i is such that one (or both!) of
the slices on the right-hand side is empty.  That wouldn't be true if
sum([]) were not 0, and arranging to make it true saves programmers
from having to deal with some otherwise special cases.

The reduction operation for any() is logical-or, and False is the
identity element for logical-or:   x logical-or False = x for all
Boolean x.

Likewise the reduction operation for all() is logical-and, and True is
the identity element for that:  x logical-and True = x for all Boolean
x.

Examples of other useful identities that follow from picking the
identity elements in the empty case, which hold even if `seq` is
empty:

    any(seq) = not all(not x for x in seq)
    all(seq) = not any(not x for x in seq)

> In the all() example, if there *are* no values in S, then none of the
> values can be != 0, and IMHO all() should return False.

That would break everything mentioned above.  Think of it another way:
 if all(seq) is false, shouldn't it be the case that you can point to
a specific element in seq that is false?  After all (pun intended
;-)), if it's not the case that all x in seq are true, it must be the
case that some x in seq is false.  But if seq is empty, there is no x
in seq that's either true or false, and in particular there's no x in
seq that's false.  Since we can't exhibit an x in seq such that x is
false, saying that all(seq) is false would be very surprising to you
on some other day ;-)

> Therefore, I propose that all() should work as if it were written this way:
>
> def all(S):
>     ret_val = False
>
>     for x in S:
>         ret_val = True
>         if not x:
>             return False
>
>     return ret_val
>
>
> Comments?

That won't happen, for three reasons:  several were given above; this
is also the convention used for universal and existential quantifiers
applied to empty sets in mathematical logic (and for much the same
reasons there); and it matches prior art in the ABC language (which is
one of Python's predecessors, and which had direct syntactic support
for universal and existential quantifiers in Boolean expressions).



More information about the Python-list mailing list