any() and all() on empty list?

[Steven D'Aprano]

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

At risk of flogging a dead horse...

On Wed, 29 Mar 2006 01:01:00 -0800, vdrab wrote:
[color=blue][color=green]
>> 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]
>
> 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.[/color]

(Dis)proof by counter-example:

GvR is in deep trouble -- the police now have sufficient evidence of his
guilt to lock him away for life for all of the terrorist attacks he is
suspected of:
[color=blue][color=green][color=darkred]
>>> def enough_evidence (crime):[/color][/color][/color]
.... return True
....[color=blue][color=green][color=darkred]
>>> suspected_attac ks = []
>>> sufficient_proo f = filter(enough_e vidence, suspected_attac ks)
>>> guilty = all(sufficient_ proof)
>>> if guilty:[/color][/color][/color]
.... print "Send him to Gitmo!"
....
Send him to Gitmo!


I understand and accept Tim Peter's explanation for why the proposed
behaviour is the Right Way to handle all() and any() -- but that doesn't
mean that there isn't a paradox buried in there.

Notice that the police, by setting themselves the more difficult task of
proving Guido's guilt on all() charges, can lock him up even though no
crime was committed. Whereas, if they took the simpler task of merely
proving his guilt on any() charge, Guido would be a free man:
[color=blue][color=green][color=darkred]
>>> guilty = any(sufficient_ proof)
>>> if not guilty:[/color][/color][/color]
.... print "Walk free!"
....
Walk free!


While the implemented behaviour might be more practical than the
alternatives, it is still worrying paradoxical. If "All sheep are woolly",
then obviously it must also be true that "Any sheep is woolly". More
formally, if all(X), then any(X) -- except for the case of empty X. Hmmm.



--
Steven.

[Paul Rubin]

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

Steven D'Aprano <steve@REMOVETH IScyber.com.au> writes:[color=blue]
> While the implemented behaviour might be more practical than the
> alternatives, it is still worrying paradoxical. If "All sheep are woolly",
> then obviously it must also be true that "Any sheep is woolly". More
> formally, if all(X), then any(X) -- except for the case of empty X. Hmmm.[/color]

Maybe "any" should be renamed to "some".

[Steve R. Hastings]

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

On Wed, 29 Mar 2006 21:34:08 +1000, Steven D'Aprano wrote:[color=blue]
> While the implemented behaviour might be more practical than the
> alternatives, it is still worrying paradoxical. If "All sheep are woolly",
> then obviously it must also be true that "Any sheep is woolly". More
> formally, if all(X), then any(X) -- except for the case of empty X. Hmmm.[/color]

It seems strange, but Tim Peters explained it well. It would also seem
strange if this didn't work:

all(lst0) and all(lst1) == all(lst0 + lst1)

Clearly that should work, and it shouldn't fail just because one of the
lists happens to be empty.



If you are working with a list, you can just do this:

lst and all(lst)

What bothers me is the iterator case. There is no simple way to write a
test like the above if you have an iterator.

Hmmm. How about this?


def truecount(seq):
count_true = 0
count= 0
for x in seq:
if x:
count_true += 1
count += 1
return count_true, count



count_true, count = truecount(enoug h_evidence(x) for x in suspected_attac ks)
if not count:
print "Walk free!"
elif count == count_true:
print "Send him to Gitmo!"
else:
print "%d proven attacks out of %d suspected" % (count_true, count)
if float(count_tru e) / float(count) >= 0.8:
print "prepondera nce of evidence!"



The good thing is that these are simple functions that you can write for
yourself. I'm happy any() and all() will be built in, but I don't know
that there is sufficient need for truecount() or anything similar. If you
need it, just write it.
--
Steve R. Hastings "Vita est"
steve@hastings. org http://www.blarg.net/~steveha

[Ron Adam]

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

Paul Rubin wrote:[color=blue]
> Ron Adam <rrr@ronadam.co m> writes:[color=green]
>> 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.[/color]

The 'not not S' is just a conversion to bool. Is the following less
contorted to you?
[color=blue][color=green][color=darkred]
>>> bool([])[/color][/color][/color]
False
[color=blue]
> Someone asked for a cite; I listed one before:
>
> http://en.wikipedia.org/wiki/For_all
>
> See the "Negation" section.[/color]


'Is all True' isn't the same as 'Has all True'. As I said, I'm not
questioning the mathematical meaning of the set relation 'is all True',
but wondering weather or not an alternate relation 'has all True' would
be better for use as a flow control test.


Do you have some examples uses since it's obvious to you?

We could all probably come up with examples that support either side.
What I'm looking for are the obvious and common use examples. How would
they behave differently depending on weather 'is all true' or 'has all
true' is used? Which would be faster and simpler to use in most cases.

I just have a feeling we will see a lot of "S and all(S)" expressions
being used. Maybe that's not so bad, but I would prefer to not have to
do that if it turns out to the standard idiom for all testing within a loop.


The actual code used would be more efficient than my examples, they will
have shortcutting behavior, and written in C. Those examples where
meant to show the principle.

And the question still stands:

"Does it do the right thing in most situations it will be used in?"


That will of course depend on weather it's being used as a mathematics
test, or for flow control test. Which is why I suggested the possibly
of having both. I believe the flow control semantics will be the more
common use, but I may be mistaken thinking "S and all(S)" will be needed
in most cases.

<shrug>This doesn't seem to be an issue for anyone else, so I'll wait
and see how it turns out.

Cheers,
Ron

[Ron Adam]

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

Carl Banks wrote:[color=blue]
> Steve R. Hastings wrote:[color=green]
>> 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[/color]


Yes, But that should be a test for 'not any()'.

if not any(bug.status == 'open' for bug in bugs_filed):
do_release()


So to give a counter example...

Where we are assembling widgets in a manufacturing plant. Where we don't
want to go to the next step until *all* the sub parts are present.

if all(part.status == 'present' for part in unit):
do_release()

Oops! Some empty bins showed up at the next assembly station. ;-)


Cheers,
Ron

[Duncan Booth]

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

Ron Adam wrote:
[color=blue]
> Where we are assembling widgets in a manufacturing plant. Where we don't
> want to go to the next step until *all* the sub parts are present.
>
> if all(part.status == 'present' for part in unit):
> do_release()
>
> Oops! Some empty bins showed up at the next assembly station. ;-)[/color]

I don't see the problem. You only get an empty bin if there is some part
assembled from no sub-parts, in which case you wanted an empty bin.

[Steven D'Aprano]

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

Tim Peters wrote:
[color=blue][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 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?[/color]

Think of it this way: if all(seq) is true, shouldn't it
be the case that you can point to a specific element in
seq that is true?

It may be that all([]) => True is useful more often
than all([]) => False would be, in the same way that it
is useful to define 0! = 1 and other mathematical
identities, but that doesn't imply that, strictly
speaking, there isn't some monkey-business going on there.

Now, I'm happy to admit that this is useful
monkey-business, but it can still lead to unexpected
results, as in my example in a previous post.



--
Steven.

[Paul Rubin]

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

Steven D'Aprano <steve@REMOVEME cyber.com.au> writes:[color=blue]
> Think of it this way: if all(seq) is true, shouldn't it be the case
> that you can point to a specific element in seq that is true?[/color]

No, all(seq) is true if you can't point to a specific element in seq
that's false.

[Steven D'Aprano]

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

Paul Rubin wrote:
[color=blue]
> Steven D'Aprano <steve@REMOVEME cyber.com.au> writes:
>[color=green]
>>Think of it this way: if all(seq) is true, shouldn't it be the case
>>that you can point to a specific element in seq that is true?[/color]
>
>
> No, all(seq) is true if you can't point to a specific element in seq
> that's false.[/color]

No, all(seq) is true if every element in seq is true.
Surely that's a more intuitive definition than your
definition by what you can't do.

The question that needs to be answered is, what if
there are no elements at all? That's an arbitrary
decision. Like the question "what is 0**0?" in
mathematics, some answers are more useful than others.
I can respect that practical answer -- but it isn't the
*only* answer.

(For those who don't see why 0**0 is problematic, 0**x
is equal to 0 for all x, and x**0 is equal to 1 for all
x, so what do you do for 0**0?)

Here's another way of looking at the problem:

all(flying elephants which are pink) => true
all(flying elephants which are not pink) => true

So, these flying elephants -- are they pink or not?



--
Steven.

[Steven D'Aprano]

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

Duncan Booth wrote:
[color=blue]
> Ron Adam wrote:
>
>[color=green]
>>Where we are assembling widgets in a manufacturing plant. Where we don't
>>want to go to the next step until *all* the sub parts are present.
>>
>>if all(part.status == 'present' for part in unit):
>> do_release()
>>
>>Oops! Some empty bins showed up at the next assembly station. ;-)[/color]
>
>
> I don't see the problem. You only get an empty bin if there is some part
> assembled from no sub-parts, in which case you wanted an empty bin.[/color]

Okay, Ron's example wasn't the best. How about this
one, from chess:

The intention is to play cautiously if all threatened
pieces are valuable, and daringly otherwise. Here is
the obvious, but wrong, code:

if all(piece.value () > 5 for piece in \
threatened_piec es):
play_cautiously ()
else:
play_daringly()

It is wrong because it leads to incorrect behaviour
when there are no threatened pieces at all -- the
intention is to play daringly by default, except for
the specific case of there being threatened pieces, all
of which are high value pieces.

So one correct, but more verbose, way to code this
would be:

valuable_danger = [piece.value() > 5 for piece in \
threatened_piec es]
if valuable_danger and all(valuable_da nger):
play_cautiously ()
else:
play_daringly()


Another obvious way of coding this would be to reverse
the sign of the test like so:

if not any(piece.value () <= 5 for piece in \
threatened_piec es):
play_cautiously ()
else:
play_daringly()

In other words, play daringly unless no threatened
piece is low value. Unfortunately, while this is
obvious, it also gives the wrong behaviour when there
are no threatened pieces.



The lesson of this example is that while the standard
behaviour of any() and all(), as implemented in Python,
are often, usually, the Right Way to do things, they do
fail on some occasions, and coders should be aware of
cases where the assumptions break down.


--
Steven.

[Carl Banks]

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


Steven D'Aprano wrote:[color=blue]
> Paul Rubin wrote:
>[color=green]
> > Steven D'Aprano <steve@REMOVEME cyber.com.au> writes:
> >[color=darkred]
> >>Think of it this way: if all(seq) is true, shouldn't it be the case
> >>that you can point to a specific element in seq that is true?[/color]
> >
> >
> > No, all(seq) is true if you can't point to a specific element in seq
> > that's false.[/color]
>
> No, all(seq) is true if every element in seq is true.
> Surely that's a more intuitive definition than your
> definition by what you can't do.
>
> The question that needs to be answered is, what if
> there are no elements at all?[/color]

Then every element in seq is true.

(And false. :)


Carl Banks

[Peter Otten]

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

Steven D'Aprano wrote:
[color=blue]
> Okay, Ron's example wasn't the best. How about this
> one, from chess:
>
> The intention is to play cautiously if all threatened
> pieces are valuable, and daringly otherwise.[/color]

Isn't that example even worse? Compare:

- You have one of your valuable pieces threatened. You decide to play
cautiously.

- You have one valuable and one piece of lesser value threatened. You play
daringly.

What is that? The courage of despair?

if any(piece.value > 5 for piece in threatened):
# play cautiously
else:
# play daringly

looks more convincing to the non-chessplaying bystander (read: me) and --
surprise -- is supported by the new builtins just fine.

Peter

[Georg Brandl]

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

Steven D'Aprano wrote:[color=blue]
> Paul Rubin wrote:
>[color=green]
>> Steven D'Aprano <steve@REMOVEME cyber.com.au> writes:
>>[color=darkred]
>>>Think of it this way: if all(seq) is true, shouldn't it be the case
>>>that you can point to a specific element in seq that is true?[/color]
>>
>>
>> No, all(seq) is true if you can't point to a specific element in seq
>> that's false.[/color]
>
> No, all(seq) is true if every element in seq is true.
> Surely that's a more intuitive definition than your
> definition by what you can't do.
>
> The question that needs to be answered is, what if
> there are no elements at all? That's an arbitrary
> decision. Like the question "what is 0**0?" in
> mathematics, some answers are more useful than others.
> I can respect that practical answer -- but it isn't the
> *only* answer.
>
> (For those who don't see why 0**0 is problematic, 0**x
> is equal to 0 for all x, and x**0 is equal to 1 for all
> x, so what do you do for 0**0?)
>
> Here's another way of looking at the problem:
>
> all(flying elephants which are pink) => true
> all(flying elephants which are not pink) => true
>
> So, these flying elephants -- are they pink or not?[/color]

No, you ask two different sets whether they are true.

Georg

[Ron Adam]

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

Duncan Booth wrote:[color=blue]
> Ron Adam wrote:
>[color=green]
>> Where we are assembling widgets in a manufacturing plant. Where we don't
>> want to go to the next step until *all* the sub parts are present.
>>
>> if all(part.status == 'present' for part in unit):
>> do_release()
>>
>> Oops! Some empty bins showed up at the next assembly station. ;-)[/color]
>
> I don't see the problem. You only get an empty bin if there is some part
> assembled from no sub-parts, in which case you wanted an empty bin.[/color]

Hmmm... It wasn't a well though out example. I was thinking in terms
of several processes working at the same time, and not communicating
with each other. Ie.. a bin getter, a part inserter, a part checker, a
bin mover. etc.

But even then if all the parts get marked as 'present' even though they
are aren't there, the bin could be released to the next station. And so
that example is void. I'll try and think of a better one.


Cheers,
Ron

[Ron Adam]

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

Steven D'Aprano wrote:[color=blue]
> Paul Rubin wrote:
>[color=green]
>> Steven D'Aprano <steve@REMOVEME cyber.com.au> writes:
>>[color=darkred]
>>> Think of it this way: if all(seq) is true, shouldn't it be the case
>>> that you can point to a specific element in seq that is true?[/color]
>>
>>
>> No, all(seq) is true if you can't point to a specific element in seq
>> that's false.[/color]
>
> No, all(seq) is true if every element in seq is true. Surely that's a
> more intuitive definition than your definition by what you can't do.[/color]


Yes, they are both valid view points. One is 'is all true' and the
other is 'has all true'.

You can also use either to express the other...

S and isalltrue(S) -> hasalltrue(S)

not S or hasalltrue(S) -> isalltrue(S)



A possibly useful thing to have:

hasall(S, value, test=None)

hasall(S, True) # Test for actual "True" values or 1.
hasall(S, True, bool) # test for true values, not zero or False.
hasall(S, 'ok')
hasall(S, True, lambda n: n=42)

Cheers,
Ron