any() and all() on empty list?

[Dennis Lee Bieber]

In English, if I were to ask you a question like "Have you put all your
books in the truck?" when you have no books, a valid and reasonable
answer is "I don't have any books." I.e., the answer is neither yes
nor no. In fact, yes and no aren't valid answers at all (unless you're
being snarky**), because, in English, the word "all" carries an
assumption of existence. (Or maybe it doesn't for you guys in
Australia; it does in the USA.)

Of course, if the reason for the question in the first place is that
the truck can not leave until all books have been loaded -- then
answering "No" when you possess no books implies the truck must stay
until you put your (non-existant) book onto it.
--

 

[Alex Martelli]

who said anything about empty sets ?

Universally-false predicate <--> empty set

....in Cantor's/Frege's world, which is commonly accepted as equivalent
to Aristotle's Logic. Modal logic is a different kettle of fish (and,
in retrospect, what Dodgson [aka Carroll] was groping towards)... but I
know of no programming paradigm based on it (even Turing's and Church's
map more easily to naive set theory//logic, give or take a Zermelo or
so;-). I would in fact challenge the assertion that a useful programming
paradigm COULD be based on modal logic, hoping for proof of the
contrary;-)


Alex

 

[Ron Adam]

In Python, yes and no are the only possible answers. Probably the only
analogous thing you could do in Python would be for all() to raise
ValueError when passed an empty sequence.

There is also 'None' which serves a similar purpose of indicating an
invalid value when passing arguments.

Cheers,
Ron

 

[Fredrik Lundh]

Universally-false predicate <--> empty set

...in Cantor's/Frege's world

I was more thinking of Disney.

</F>

 

[Antoon Pardon]

That would make them Schrödinger elephants!

Every member of the empty set is a Schrödinger element.

 

[Ant]

I don't think that there will be any valid examples.

all(list) simply means "every element of the list evaluates to True".
This is trivially true in the case of the empty list. This is logically
equivalent to "There are no elements in the list which evaluate to
False".

any(list) simply means "at least one element of the list evaluates to
true". This is trivially false for the empty list - there are no
elements to be true.

These are logical functions and should be mathematically sound. It's
possible to add all sorts of problems if we just arbitrarily decide
what "for all x" should mean. We may just as well decide that for
convenience: math.pi == 3.

 

[Gerard Flanagan]

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?

all(list) simply means "every element of the list evaluates to True".
This is trivially true in the case of the empty list. This is logically
equivalent to "There are no elements in the list which evaluate to
False".

any(list) simply means "at least one element of the list evaluates to
true". This is trivially false for the empty list - there are no
elements to be true.

These are logical functions and should be mathematically sound. It's
possible to add all sorts of problems if we just arbitrarily decide
what "for all x" should mean. We may just as well decide that for
convenience: math.pi == 3.

I agree.

Some amateur maths - applying the identities of a 'two-element Boolean
algebra' found here:

http://en.wikipedia.org/wiki/Two-element_Boolean_algebra

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

#the identities don't hold if you use the alternative
##def all(S):
## ret_val = False
##
## for x in S:
## ret_val = True
## if not x:
## return False
##
## return ret_val

empty = []
universe = [ 0, 1 ]

one = all(empty)
zero = any(empty)

assert (one or one) == one
assert (one or zero) == one
assert (zero or one) == one
assert (zero or zero) == zero
assert (zero and zero) == zero
assert (zero and one) == zero
assert (one and zero) == zero
assert (one and one) == one
assert (not one) == zero
assert (not zero) == one

#on the other hand
one = all(universe)
zero = any(universe)

#de Morgan - swap 'and' and 'or' and complement the result
assert not(one and one) != one
assert not(one and zero) != one
assert not(zero and one) != one
assert not(zero and zero) != zero
assert not(zero or zero) != zero
assert not(zero or one) != zero
assert not(one or zero) != zero
assert not(one or one) != one
assert not(not one) != zero
assert not(not zero) != one

 

[Carl Banks]

There is also 'None' which serves a similar purpose of indicating an
invalid value when passing arguments.

If all() were to return None, then if would essentially be like
returning False, because an if-statement would treat False and None the
same (as would most anything else expecting a boolean value).

The only reasonable way to say "false assumption" in Python is to raise
an exception.


Carl Banks

 

[Ron Adam]

If all() were to return None, then if would essentially be like
returning False, because an if-statement would treat False and None the
same (as would most anything else expecting a boolean value).

The only reasonable way to say "false assumption" in Python is to raise
an exception.


Carl Banks

Then maybe None should be evaluated as True so it is consistent with
all(). ;-)


Not serious of course, Cheers,
Ron

 

[Ant]

lol!

 

[Paul Rubin]

The 'not not S' is just a conversion to bool. Is the following less
contorted to you?

bool([])

False

Oh ok. Yes, bool(S) is much less contorted than "not not S".

'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?

# go out drinking when I'm finished with today's work
if all (task.done() for task in self.things_to_do_today()):
self.go_out_drinking()

If I didn't have anything to do today, that should result in going out
drinking immediately.

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.

I think "S and all(S)" is the right way to express that, if that's
what's intended.

 

[Steve R. Hastings]

I think "S and all(S)" is the right way to express that, if that's
what's intended.

I still would like a standard function, because "S and all(S)" does not
work with iterators. I proposed one possible function, truecount(S), that
returns a tuple of how many were true and how many there were total. Then
you could do

true_count, count = truecount(S)

if count and true_count == count:
# nonempty list and all are true


And S could be an iterator or generator function expression.

You can easily write your own truecount() but it would be nice to have
something like that as standard. I don't much like the name "truecount"
though; I'm open to suggestions for a better name.

 

[Ron Adam]

I still would like a standard function, because "S and all(S)" does not
work with iterators. I proposed one possible function, truecount(S), that
returns a tuple of how many were true and how many there were total. Then
you could do

true_count, count = truecount(S)

if count and true_count == count:
# nonempty list and all are true


And S could be an iterator or generator function expression.

You can easily write your own truecount() but it would be nice to have
something like that as standard. I don't much like the name "truecount"
though; I'm open to suggestions for a better name.

How about:

countall(S, value=True)


Considering len() is used to get a length, and countall() is related to
all(), but it's explicit about what it's counting and would not return
True on an empty set. I think it would be useful.

true_count, count = countall(S), len(S)

Cheers,
Ron

 

[Paul Rubin]

true_count, count = countall(S), len(S)

In general it's preferable to not rely on len being available, since
these are arbitrary iterators.

 

[Steve R. Hastings]

true_count, count = countall(S), len(S)

Unfortunately, this does not solve the problem.

An iterator yields its values only once. If you have an iterator "itr",
you cannot do all(itr) and then do len(itr). Whichever one you do first
will run the iterator to exhaustion.

This is why my proposed truecount() returns a tuple, with the length and
the count of true values.

Suppose you wanted, for some reason, to know how many lines in a file
start with a vowel:

vowels = frozenset("aeiouAEIOU")
f = open("a_file.txt") # note that f is an iterator
true_count, count = truecount(line[0] in vowels for line in f)
print "%d lines in file; %d start with a vowel" % (count, true_count)


Because f is an iterator, we only get one pass through the values of the
file. Because truecount() returns a tuple with two values, one pass is
enough.

 

[Steve R. Hastings]

my proposed truecount() returns a tuple, with the length and
the count of true values.

I never liked the name truecount(), and the more I think about it, the
less I like the function. It should either solve a very important need,
or else it should be general enough to solve multiple needs; truecount()
doesn't really do either.

I kept thinking about this, and then suddenly I remembered an idea I read
about before. I'm not sure who invented this idea, but it wasn't me.

Here is a function called "tally()". It reduces a list to a dictionary
of counts, with one key for each value from the list. The value for
each key is the count of how many times it appeared in the list.


def tally(seq, d=None):
if d == None:
d = {}

for x in seq:
if x in d:
d[x] += 1
else:
d[x] = 1
return d



This neatly replaces truecount(), and you can use it for other things as
well.

Let's revisit my example from before:

Suppose you wanted, for some reason, to know how many lines in a file
start with a vowel:

vowels = frozenset("aeiouAEIOU")
f = open("a_file.txt") # note that f is an iterator

counts = tally(line[0] in vowels for line in f)
# counts is a dict; counts.keys() == [False, True]
count_nonvowels, count_vowels = counts.values()

total = count_nonvowels + count_vowels
print "%d lines in file; %d start with a vowel" % (total, count_vowels)

 

[Felipe Almeida Lessa]

Em Sáb, 2006-04-01 às 08:35 -0800, Steve R. Hastings escreveu:

def tally(seq, d=None):
if d == None:
d = {}

for x in seq:
if x in d:
d[x] += 1
else:
d[x] = 1
return d

Two changes:
- Use "is None".
- Use "try ... except" instead of "in"

def tally2(seq, d=None):
if d is None:
d = {}
for x in seq:
try:
d[x] += 1
except KeyError:
d[x] = 1
return d

It's also faster:

from random import choice
a = []
for i in xrange(100000):

.... a.append(choice([False, True]))
....tally').repeat(3, 100))
4.2756481170654297tally2').repeat(3, 100))
3.812028169631958

Maybe you don't like my version, and the gains aren't that much, but
please use "is None" instead of "== None".

Cheers,

 

[Steve R. Hastings]

Two changes:
- Use "is None".
- Use "try ... except" instead of "in"
Yes.


Maybe you don't like my version, and the gains aren't that much, but
please use "is None" instead of "== None".

Actually, I do like your version. And I try to always use "is None"
instead of "== None"; today I made a mistake about it. Thank you for your
comments.

Ideally there should be an official tally() function in some module in
Python, and then we can just use it and not worry about how to write it.

 

[Ron Adam]

Here is a function called "tally()". It reduces a list to a dictionary
of counts, with one key for each value from the list. The value for
each key is the count of how many times it appeared in the list.

>
def tally(seq, d=None):
if d == None:
d = {}

for x in seq:
if x in d:
d[x] += 1
else:
d[x] = 1
return d


This neatly replaces truecount(), and you can use it for other things as
well.

if True in talley(S): do_somthing()

Works for me... ;-)


Cheers,
Ron

 

[Ron Adam]

Actually, I do like your version. And I try to always use "is None"
instead of "== None"; today I made a mistake about it. Thank you for your
comments.

Ideally there should be an official tally() function in some module in
Python, and then we can just use it and not worry about how to write it.

And it's a good candidate to be written in C as well.

Cheers,
Ron