any() and all() on empty list?

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



And he pointed out how nifty it is to combine generator functions with
these two new functions:


any(x > 42 for x in S) # True if any elements of S are > 42
all(x != 0 for x in S) # True if all elements if S are nonzero



I'm completely on board with the semantics for any(). But all() bothers
me. If all() receives an empty list, it will return True, and I don't
like that. 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.

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.

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?

P.S. I searched with Google, and with Google Groups, trying to find
anyplace this might have been discussed before. Apologies if this has
already been discussed and I missed it somehow.
--
Steve R. Hastings "Vita est"
steve@hastings. org http://www.blarg.net/~steveha

[Paul Rubin]

Re: any() and all() on empty list?

"Steve R. Hastings" <steve@hastings .org> writes:[color=blue]
> 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.[/color]

That goes against the usual meaning of "all" in, say, mathematical logic.

Usually, "for all X in S, PRED(x) is true" means:
there does not exist X in S so that PRED(x) is false.

So, all(empty sequence) should be true.

[Paul McGuire]

Re: any() and all() on empty list?

"Paul Rubin" <http://phr.cx@NOSPAM.i nvalid> wrote in message
news:7x3bh1x0ym .fsf@ruckus.bro uhaha.com...[color=blue]
> "Steve R. Hastings" <steve@hastings .org> writes:[color=green]
> > 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.[/color]
>
> That goes against the usual meaning of "all" in, say, mathematical logic.
>
> Usually, "for all X in S, PRED(x) is true" means:
> there does not exist X in S so that PRED(x) is false.
>[/color]
How do you get this "usually" stuff? I would agree that this is usually
implemented as a short-circuited loop through the list, that breaks out at
the first False value. But I would not be quick to equate "commonalit y of
implementation" with "meaning".
[color=blue]
> So, all(empty sequence) should be true.[/color]
"should be"? Or "usually turns out to be"?

To my mind, the *meaning* of all() is that every element in the list asserts
True. But this is with an initial assumption that all() is False, unless I
test every value and find them to be True. Since I assume False to begin
with, I get no values in the list to contradict the assumption, and so
all([]) returns False.

It would seem that the resolution rests on which initial condition we
choose, False or True. Perhaps we should consult a more formal mathematical
resource for this.

-- Paul
"If it was so, it might be; and if it were so, it would be; but as it isn't,
it ain't. That's logic."

[Tim Peters]

Re: any() and all() on empty list?

[Steve R. Hastings][color=blue]
> 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?[/color]

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.[color=blue][color=green][color=darkred]
>>> any([])[/color][/color][/color]
False[color=blue][color=green][color=darkred]
>>> all([])[/color][/color][/color]
True
[color=blue]
> 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,[/color]

Yes.
[color=blue]
> and I don't like that.[/color]

Tough ;-)
[color=blue]
> 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.[/color]

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)
[color=blue]
> 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.[/color]

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 ;-)
[color=blue]
> 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?[/color]

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

[Ben Finney]

Re: any() and all() on empty list?

"Steve R. Hastings" <steve@hastings .org> writes:
[color=blue]
> So, Python 2.5 will have new any() and all() functions.
> http://www.python.org/dev/peps/pep-0356/[/color]

And there was much rejoicing.
[color=blue]
> any(seq) returns True if any value in seq evaluates true, False otherwise.[/color]

Yep.
[color=blue]
> all(seq) returns True if all values in seq evaluate true, False otherwise.[/color]

Not quite how I'd phrase it. I prefer, for symmetry with 'any':

all(seq) returns False if any value in seq evaluates false, True otherwise.
[color=blue]
> I have a question: what should these functions return when seq is an
> empty list?
>
>
>
> 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[/color]

I love the symmetry of these semantics, find them quite intuitive, and
therefore disagree with your interpretation of 'all()'.
[color=blue]
> I'm completely on board with the semantics for any(). But all() bothers
> me. If all() receives an empty list, it will return True, and I don't
> like that. 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.[/color]

-1.

You may as well argue that "any() should be a more restrictive
function than all(), and it bothers me to see a case where all()
returns False but any() returns True."


It seems clear to me that an empty argument list fails a check for
"any True?", because that's the same as a check for "all False?". The
only reasonable alternative would be a special case for an empty
argument list, and that's too ugly.

It seems clear to me that an empty argument list passes a check for
"all True?", because that's the same as a check for "any False?". The
only reasonable alternative would be a special case for an empty
argument list, and that's too ugly.

To imagine that one of these "should be a more restrictive function"
would belie their simple, elegant, and (to me) obvious definitions. I
disagree with your interpretation.

--
\ "My house is made out of balsa wood, so when I want to scare |
`\ the neighborhood kids I lift it over my head and tell them to |
_o__) get out of my yard or I'll throw it at them." -- Steven Wright |
Ben Finney

[Paul McGuire]

Re: any() and all() on empty list?

"Steve R. Hastings" <steve@hastings .org> wrote in message
news:pan.2006.0 3.29.05.32.50.2 21097@hastings. org...[color=blue]
> 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?
>[/color]
Here is my attempt at a more formal approach to this question, rather than
just using our intuition. Unfortunately, following this process proves my
earlier post to be wrong, but, oh well...

Consider two sets A and B where A+B is the union of the two sets.

if any(A+B) = True -> any(A) or any(B) = True
but we cannot assert either any(A)=True or any(B)=True.

if any(A+B) = False -> any(A) = False and any(B) = False.


if all(A+B) = True -> all(A)=True and all(B)=True
if all(A+B) = False -> all(A)=False or all(B)=False
but we cannot assert either all(A)=False or all(B)=False.


Now instead of B, lets add the empty set 0 to A. We want to come up logic
such that adding the empty set does not change the values of all() or any(),
since A+0=A.

any(A+0) = any(A) or any(0)

any(0) must be False, so that if any(A) is True, any(A+0) is True, and if
any(A) is False, any(A+0) is False.

all(A+0) = all(A) and all(0)

if all(A) is True, all(A+0) is True.
Therefore, all(0) is True.

-- Paul

[Steve R. Hastings]

Re: any() and all() on empty list?

Thank you very much for explaining this. And so thoroughly!

Of course I withdraw all objections. :-)
--
Steve R. Hastings "Vita est"
steve@hastings. org http://www.blarg.net/~steveha

[Paul Rubin]

Re: any() and all() on empty list?

"Paul McGuire" <ptmcg@austin.r r._bogus_.com> writes:[color=blue][color=green]
> > Usually, "for all X in S, PRED(x) is true" means:
> > there does not exist X in S so that PRED(x) is false.
> >[/color]
> How do you get this "usually" stuff? I would agree that this is usually
> implemented as a short-circuited loop through the list, that breaks out at
> the first False value. But I would not be quick to equate "commonalit y of
> implementation" with "meaning".[/color]

See <http://en.wikipedia.or g/wiki/For_all>:

Generally, then, the negation of a propositional function's universal
quantification is an existential quantification of that propositional
function's negation; symbolically,

\lnot\ \forall{x}{\in} \mathbf{X}\, P(x) \equiv\
\exists{x}{\in} \mathbf{X}\, \lnot\ P(x)

[Sybren Stuvel]

Re: any() and all() on empty list?

Paul McGuire enlightened us with:[color=blue][color=green]
>> That goes against the usual meaning of "all" in, say, mathematical
>> logic.
>>
>> Usually, "for all X in S, PRED(x) is true" means: there does not
>> exist X in S so that PRED(x) is false.
>>[/color]
> How do you get this "usually" stuff?[/color]

From its mathematical definition.
[color=blue]
> I would agree that this is usually implemented as a short-circuited
> loop through the list, that breaks out at the first False value.[/color]

Implementation is irrelevant when it comes to the definition of a
mathematical operator.
[color=blue]
> But I would not be quick to equate "commonalit y of implementation"
> with "meaning".[/color]

Which is good.
[color=blue]
> Perhaps we should consult a more formal mathematical resource for
> this.[/color]

In mathematics, 'for all x in A, f(x) is True' is true when A is
empty. You can either look it up on trust someone who studied
mathematics (me) on it.

Sybren
--
The problem with the world is stupidity. Not saying there should be a
capital punishment for stupidity, but why don't we just take the
safety labels off of everything and let the problem solve itself?
Frank Zappa

[Ron Adam]

Re: any() and all() on empty list?

Paul McGuire wrote:[color=blue]
> "Paul Rubin" <http://phr.cx@NOSPAM.i nvalid> wrote in message
> news:7x3bh1x0ym .fsf@ruckus.bro uhaha.com...[/color]
[color=blue]
> To my mind, the *meaning* of all() is that every element in the list asserts
> True. But this is with an initial assumption that all() is False, unless I
> test every value and find them to be True. Since I assume False to begin
> with, I get no values in the list to contradict the assumption, and so
> all([]) returns False.[/color]

Looking at in a different way... If we consider also having a function
none() (for comparison), would it be consistent with all()?

def none(S):
for x in S:
if x: return False
return True


any([]) -> False

none([]) -> True (same as 'not any(S)')

all([]) -> True ? False


I think I agree that all() should have an initial presumption of being
False.


Looking at it in yet another way... (yes, not as efficient)

def all(S):
S_ = [x for x in S if x]
return S_ == S

def any(S):
S_ = [x for x in S if x]
return S_ != []

def none(S):
S_ = [x for x in S if x]
return S_ == []


In this view and empty set can be True for all(). Is it posible
'all([])' is undefined? Here, none() and all() return contradicting
values. So maybe the correct version may be...

def all(S):
if S == []: return False
for x in S:
if x return True
return False

I think a few valid actual use case examples could clear it up. What
makes the most sense?

Cheers,
Ron

[Paul Rubin]

Re: any() and all() on empty list?

Ron Adam <rrr@ronadam.co m> writes:[color=blue]
> In this view and empty set can be True for all(). Is it posible
> 'all([])' is undefined? Here, none() and all() return contradicting
> values. So maybe the correct version may be...[/color]

I don't see any contradiction. all([]) and none([]) are both true.

Anyway, this has all been discussed before in a slightly different context:

Harary, F. and Read, R. "Is the Null Graph a Pointless Concept?" In
Springer Lecture Notes in Math. 406 (1974) 37-44

[vdrab]

Re: any() and all() on empty list?

> I'm completely on board with the semantics for any(). But all() bothers[color=blue]
> me. If all() receives an empty list, it will return True, and I don't
> like that. 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.[/color]

Who should we call to report this fallacy? GvR? Goedel? Tarski? no,
wait... Frege ! or wait... actually, I think that must be Aristotle.
Sorry Aristotle, the ol' syllogisms have to go.

; -)
All silliness aside, the meaning of all() in python corresponds just
fine with "all" in both language and logic.
s.

[Ron Adam]

Re: any() and all() on empty list?

Paul Rubin wrote:[color=blue]
> Ron Adam <rrr@ronadam.co m> writes:[color=green]
>> In this view and empty set can be True for all(). Is it posible
>> 'all([])' is undefined? Here, none() and all() return contradicting
>> values. So maybe the correct version may be...[/color]
>
> I don't see any contradiction. all([]) and none([]) are both true.[/color]

Contradicting wasn't the correct term to use I suppose. And in any case
it's not really the point at hand. See below.

[color=blue]
> Anyway, this has all been discussed before in a slightly different context:[/color]

I'm sure it has. And I don't mean to disagree with the pure
mathematical or logical meanings.

I'm thinking more in terms of weather or not they are defined correctly
for their desired usage. If they are meant to be used as pure logic
functions in math formulas then of course they should follow the
mathematical definitions. But if they are meant to be used as flow
control tests, then they should follow pythons flow control semantics
and do what give the best results when used as flow control tests in
most situations.

Currently:

not not [] -> False -> has None
not not [...] -> True -> has Some


So using the same semantics... (With no conditional statements)

# has any True
def any(S):
result = not not []
for x in S:
result = result or x
return not not result

# has all True
def all(S):
result = not not S
for x in S:
result = result and x
return not not result

These are 'has any True' and 'has all True' which aren't the same as the
math operations 'any True' and 'all True'.

But the real questions is, does it do the right thing in real code?

Wouldn't I want to skip a block if the sequence is an empty set?

while all(S):
...

Would I need to prefix some or many tests with a condition or logical
check for an empty set?

if S and all(S): foo()

How often would these situations come up?

Could pure logic functions 'anytrue()' and 'alltrue()' live in the math
module and 'any()' and 'all()' be flow control tests as builtins?

(Only if there is desire and need for both of course.)

Just thinking about things. I really just want what is best for Python
in the long term and am not trying to be difficult. I haven't seen
many use cases yet and it seems to me it may make a difference. So I'm
going to try to find places in my own code where these will be useful in
the meantime.

Cheers,
Ron

[Paul Rubin]

Re: any() and all() on empty list?

Ron Adam <rrr@ronadam.co m> writes:[color=blue]
> Just thinking about things. I really just want what is best for
> Python in the long term and am not trying to be difficult.[/color]

I'm sorry, maybe it's the math geek in me, but I just see all those
suggestions about "not not S" as being contorted. It's obvious to me
that all([]) should be True, that while(any(S)) should not terminate
if S is empty, etc.

Someone asked for a cite; I listed one before:

http://en.wikipedia.org/wiki/For_all

See the "Negation" section.

[Carl Banks]

Re: any() and all() on empty list?

Steve R. Hastings wrote:[color=blue]
> I'm completely on board with the semantics for any(). But all() bothers
> me. If all() receives an empty list, it will return True, and I don't
> like that. 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.[/color]

Perhaps a practical example will illustrate why all() returns False
better than all this mathematical mumbo-jumbo.

Ok, say you're writing a simple software management/bug tracking
system. It manage another software package that is to have periodic
releases, but the release can only be made when there are no
outstanding bugs. You might have a line of code that looks like this:

if all(bug.status == 'closed' for bug in bugs_filed):
do_release()

As you can see, the release will only happen if all the bugs are marked
closed. But... what if no bugs have been filed? If all() were to
return False on an empty sequence, the software couldn't be fixed until
at least one bug had been filed and closed!

The point is, whenever you have to test that every item in a list is
true, it is almost always correct for the test to pass when the list is
empty. The behavior of all() is correct.


Carl Banks