7 ms·

all([]) returns True but any([]) returns False, which seems like a contradiction.

by celias 7y ago

kragen 7y ago
It follows from exactly the same logic. The following are theorems, at least as long as x and y are lists of Booleans: all(x + [True]) == all(x) any(x + [False]) == any(x) all(x + y) == (all(x) and all(y)) any(x + y) == (any(x) or any(y)) not all(x) == any(not xi for xi in x) not any(x) == all(not xi for xi in x) Any other values for all([]) and any([]) would cause some or all of these theorems to be correct for all values of x and y except the empty list. In practice this would mean you would have a bug in your program on most occasions where the argument of one of these functions was empty, unless you included a special case for empty sequences. For example, suppose you're processing a request that includes some tasks and some attachments. You might write something like this: if any(task.is_failed() for task in request.tasks): raise TaskFailed(request) if any(x.is_too_large() for x in request.attachments): raise AttachmentTooLarge(request) Clearly for this code to do the right thing in the case where a request has tasks or attachments but not both, we need any([]) to be false. And the corresponding requirement applies to all([]) if our task interface is a little different: if not all(task.is_succeeded() for task in request.tasks): raise TaskFailed(request) Now, there are occasionally programs where you do need a special case for empty sequences; for example, if you have three search results, you might want to return a page containing just those results, but if you have zero, you probably don't want to just return an empty page — the user might think the software is just broken. And in the above example, if there are neither any tasks nor any attachments, it might or might not be useful to report that the user accidentally submitted an empty request. But it is unusual for such a special case to just fall out of a possible alternative semantics of all() and any().
ben-schaaf 7y ago
Hardly. As described in the article `all([])` is equivalent to `∀x Fx` or "all unicorns are blue". `any([])` is equivalent to `∃x Fx` or "a blue unicorn exists".
mlazos 7y ago
The way I think about it is the base case of a recursive function to evaluate the two. In order to preserve folding Boolean AND across a list your base case must be true. Folding Boolean OR across a list only works if your base case is false.
- xscott 7y ago
  False is the identity element for Or, similar to how Zero is the identity element for addition. True is the identity element for And, similar to how One is the identity element for multiplication.
deleted 7y ago
[deleted]
ummonk 7y ago
How so? Any means "at least one is true" and all means "all in the array are true".
- pacala 7y ago
  all: "there is none in the array that is false".
  - thaumasiotes 7y ago
    >> all means "all in the array are true" > all: "there is none in the array that is false" You... are aware that those statements are exactly the same, right?
    - Benjamin_Dobell 7y ago
      They're not. In fact, that's what this entire article is about.
      - thaumasiotes 7y ago
        I don't know what to say to this. They are exactly the same. It's not a controversial point. You could write an article on the theme "why apples fall upward in the winter", but that wouldn't make apples fall upward in the winter. See e.g. https://en.wikipedia.org/wiki/Universal_quantification#Negation https://en.wikipedia.org/wiki/Universal_quantification#Negat...
        Benjamin_Dobell 7y ago
        > It's not a controversial point. I wouldn't have thought so personally, but alas, here we are ;)
        eru 7y ago
        Perhaps you two are not using precise enough language? The common definitions for 'all' and 'any' as used in math are certainly on thaumasiotes' side. But English as a natural, every-day language is a bit more fuzzy.
layoutIfNeeded 7y ago
Read up on DeMorgan’s law.
- thaumasiotes 7y ago
  De Morgan's law isn't the right one for this. You want the identity ∀x.P(x) ⟺ ¬∃x.¬P(x). ∀x.P(x) is obviously true when the universe is empty -- no counterexamples exist. ∃x.P(x) is obviously not true in that case -- no examples exist.
  - deleted 7y ago
    [deleted]
  - maweki 7y ago
    That is De Morgan if you expand the quantifiers.
    - thaumasiotes 7y ago
      You have to make some assumptions if you want to "expand the quantifiers". In particular, you have to assume that the universe is non-empty, which is a really bad idea if you're commenting in this thread.
pfortuny 7y ago
I think of it as: the minimum of an empty set is +inf as the min of a union must be the min of the mins. Similarly, the max of empty must be -inf.
- thaumasiotes 7y ago
  Those will get you the right result if you use them as an initial value in a fold and the set is not empty. They're not correct on their own; an empty set has no minimum or maximum.
  - eru 7y ago
    It depends. You _can_ define minimum and maximum over empty sets exactly as described and get a consistent mathematical system. But eg Python's minimum and maximum functions don't do that. They throw an error by default. In mathematical terms, if you have a lattice https://en.wikipedia.org/wiki/Lattice_(order) https://en.wikipedia.org/wiki/Lattice_(order) you can always just arbitrarily introduce a least and greatest element, and all the relevant laws stay valid. Whether that's a good idea for your application or not, is a different question. In programming, types often give you trouble. Eg the integers don't have least or greatest element, but you want your minimum function over list of integers to return an integer. So throwing an error is the only choice, if you can't represent something like minus infinity in your return type.
    - thaumasiotes 7y ago
      > You _can_ define minimum and maximum over empty sets exactly as described and get a consistent mathematical system. You can define infimum and supremum that way. But I was under the impression that wherever the concept of a "minimum element" of a set is used, the minimum element of any set must be an element of that set. So e.g. the positive reals have an infimum, 0, but no minimum. The page you link doesn't do much to dispute this idea; it uses "minimum" and "maximum" to talk about the largest and smallest elements of the lattice, but never to talk about a property that a subset of the lattice might have.
catblast 7y ago
This is also consistent with Boolean algebra where the empty sum is 0 (any), and the empty product is 1 (all).

all([]) returns True but any([]) returns False, which seems like a contradiction.

by celias 7y ago

all([]) returns True but any([]) returns False, which seems like a contradiction.

It follows from exactly the same logic. The following are theorems, at least as long as x and y are lists of Booleans: all(x + [True]) == all(x) any(x + [False]) == any(x) all(x + y) == (all(x) and all(y)) any(x + y) == (any(x) or any(y)) not all(x) == any(not xi for xi in x) not any(x) == all(not xi for xi in x) Any other values for all([]) and any([]) would cause some or all of these theorems to be correct for all values of x and y except the empty list. In practice this would mean you would have a bug in your program on most occasions where the argument of one of these functions was empty, unless you included a special case for empty sequences. For example, suppose you're processing a request that includes some tasks and some attachments. You might write something like this: if any(task.is_failed() for task in request.tasks): raise TaskFailed(request) if any(x.is_too_large() for x in request.attachments): raise AttachmentTooLarge(request) Clearly for this code to do the right thing in the case where a request has tasks or attachments but not both, we need any([]) to be false. And the corresponding requirement applies to all([]) if our task interface is a little different: if not all(task.is_succeeded() for task in request.tasks): raise TaskFailed(request) Now, there are occasionally programs where you do need a special case for empty sequences; for example, if you have three search results, you might want to return a page containing just those results, but if you have zero, you probably don't want to just return an empty page — the user might think the software is just broken. And in the above example, if there are neither any tasks nor any attachments, it might or might not be useful to report that the user accidentally submitted an empty request. But it is unusual for such a special case to just fall out of a possible alternative semantics of all() and any().

ben-schaaf 7y ago

Hardly. As described in the article `all([])` is equivalent to `∀x Fx` or "all unicorns are blue". `any([])` is equivalent to `∃x Fx` or "a blue unicorn exists".

mlazos 7y ago

The way I think about it is the base case of a recursive function to evaluate the two. In order to preserve folding Boolean AND across a list your base case must be true. Folding Boolean OR across a list only works if your base case is false.

xscott 7y ago
False is the identity element for Or, similar to how Zero is the identity element for addition. True is the identity element for And, similar to how One is the identity element for multiplication.

deleted 7y ago

[deleted]

ummonk 7y ago

How so? Any means "at least one is true" and all means "all in the array are true".

pacala 7y ago
all: "there is none in the array that is false".
- thaumasiotes 7y ago
  >> all means "all in the array are true" > all: "there is none in the array that is false" You... are aware that those statements are exactly the same, right?
  - Benjamin_Dobell 7y ago
    They're not. In fact, that's what this entire article is about.
    - thaumasiotes 7y ago
      I don't know what to say to this. They are exactly the same. It's not a controversial point. You could write an article on the theme "why apples fall upward in the winter", but that wouldn't make apples fall upward in the winter. See e.g. https://en.wikipedia.org/wiki/Universal_quantification#Negation https://en.wikipedia.org/wiki/Universal_quantification#Negat...
      - Benjamin_Dobell 7y ago
        > It's not a controversial point. I wouldn't have thought so personally, but alas, here we are ;)
        eru 7y ago
        Perhaps you two are not using precise enough language? The common definitions for 'all' and 'any' as used in math are certainly on thaumasiotes' side. But English as a natural, every-day language is a bit more fuzzy.

layoutIfNeeded 7y ago

Read up on DeMorgan’s law.

thaumasiotes 7y ago
De Morgan's law isn't the right one for this. You want the identity ∀x.P(x) ⟺ ¬∃x.¬P(x). ∀x.P(x) is obviously true when the universe is empty -- no counterexamples exist. ∃x.P(x) is obviously not true in that case -- no examples exist.
- deleted 7y ago
  [deleted]
- maweki 7y ago
  That is De Morgan if you expand the quantifiers.
  - thaumasiotes 7y ago
    You have to make some assumptions if you want to "expand the quantifiers". In particular, you have to assume that the universe is non-empty, which is a really bad idea if you're commenting in this thread.

pfortuny 7y ago

I think of it as: the minimum of an empty set is +inf as the min of a union must be the min of the mins. Similarly, the max of empty must be -inf.

thaumasiotes 7y ago
Those will get you the right result if you use them as an initial value in a fold and the set is not empty. They're not correct on their own; an empty set has no minimum or maximum.
- eru 7y ago
  It depends. You _can_ define minimum and maximum over empty sets exactly as described and get a consistent mathematical system. But eg Python's minimum and maximum functions don't do that. They throw an error by default. In mathematical terms, if you have a lattice https://en.wikipedia.org/wiki/Lattice_(order) https://en.wikipedia.org/wiki/Lattice_(order) you can always just arbitrarily introduce a least and greatest element, and all the relevant laws stay valid. Whether that's a good idea for your application or not, is a different question. In programming, types often give you trouble. Eg the integers don't have least or greatest element, but you want your minimum function over list of integers to return an integer. So throwing an error is the only choice, if you can't represent something like minus infinity in your return type.
  - thaumasiotes 7y ago
    > You _can_ define minimum and maximum over empty sets exactly as described and get a consistent mathematical system. You can define infimum and supremum that way. But I was under the impression that wherever the concept of a "minimum element" of a set is used, the minimum element of any set must be an element of that set. So e.g. the positive reals have an infimum, 0, but no minimum. The page you link doesn't do much to dispute this idea; it uses "minimum" and "maximum" to talk about the largest and smallest elements of the lattice, but never to talk about a property that a subset of the lattice might have.

catblast 7y ago

This is also consistent with Boolean algebra where the empty sum is 0 (any), and the empty product is 1 (all).