any() and all() on empty list?

[Tim Peters]

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