18 ms·

The 2,500 year old history of why Python’s all([]) returns True

189 points by earthboundkid 7y ago

celias 7y ago
all([]) returns True but any([]) returns False, which seems like a contradiction.
- 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).
deleted 7y ago
[deleted]
AllasAskBar 7y ago
lol when people forget the original intent behind words
haecceity 7y ago
Maybe it should throw an exception
- aivisol 7y ago
  Why? All unicorns are blue, aren't they?
  - kzrdude 7y ago
    I'm not sure, but all unicorns I've seen have been blue.
  - TimonKnigge 7y ago
    > All unicorns are blue, aren't they? Indeed they aren't! All unicorns are not blue.
    - aivisol 7y ago
      True
  - tzs 7y ago
    I’ve seen a lot of experimental evidence for that. "All unicorns are blue" is logically equivalent to "all non-blue things are not unicorns". Over the past few decades I’ve seen ten of thousands of non-blue things, and none of them were unicorns! https://en.wikipedia.org/wiki/Raven_paradox https://en.wikipedia.org/wiki/Raven_paradox
    - jerf 7y ago
      Contrapositives are one of my favorite things in simple logic to demonstrate the difference between rigorous logic and our human heuristic logic. Mathematically, contrapositives are identical to the original statement, but extremely frequently, if not almost always, they sound different to us humans. If more people understood them, there's a number of dumb internet debates that could finally die, where X -> Y isn't immediately obviously wrong to our human brains and may even sound correct but !Y -> !X is immediately obviously wrong.
wirrbel 7y ago
Works as expected I'd say.
TimonKnigge 7y ago
`all(x + y) = all(x) and all(y)` even when `x, y` can be the empty list.
syphilis2 7y ago
Epicycles. Experience leaves me inclined to believe the code precedes the definition. def all(iterable): for element in iterable: if not element: return False return True https://github.com/python/cpython/blob/master/Python/bltinmodule.c https://github.com/python/cpython/blob/master/Python/bltinmo...
- eru 7y ago
  But that doesn't tell you _why_ that choice is a good idea! My favourite explanation comes from property based testing. In general, you have the following property: For any lists xs and ys, all(xs) and all(ys) == all(xs + ys) If you want to keep that property as simple as possible, you have to define all([]) == True If you want to go with the opposite, your property becomes more complicated. Mathematical definitions are somewhat arbitrary. It's up to us to choose definitions that make sense in our contexts. A general desire to make the resulting systems simple and uniform worked out well for many, many context. Slight detour: that's also why defining 2 - 5 to have an answer is a good idea! Negative numbers were seen as a bit suspect, but they behave perfectly sensible. Same for complex numbers. But: still we generally leave 0 / 0 undefined, because no answer would lead to a satisfying system.
  - gridlockd 7y ago
    > But that doesn't tell you _why_ that choice is a good idea! That wasn't necessarily a choice, it may have just been an oversight not to deal with the "empty list" case. The fact that this blog post exists is a testament to this behavior being surprising. I don't think any of the arguments - philosophical or otherwise - are very good from a practical standpoint, that is: is this behavior is not more likely to cause harm? My gut feeling says that this behavior is somewhat unsafe, but then again Python is probably not the language to use when safety is a big concern. A hypothetical safer language might be better off to define "all/any" only for non-empty list.
    - eru 7y ago
      Haskell, the prototypical careful language, defines their equivalents for 'any' and 'all' exactly like Python does it. And that's not an accident. > That wasn't necessarily a choice, it may have just been an oversight not to deal with the "empty list" case. If your general code gives you a answer for a corner case, it's a good hint that this might be a reasonable answer. Not a guarantee, though.
chrismsimpson 7y ago
In Swift, I would image I could define this method as throwing an error in such a case, nixing the debate entirely. Why Swift specifically? This would be in the calling signature, implying there are inputs you can give said method that are nonsensical.
- eru 7y ago
  You'd just open another debate. Your client code has to work with the behaviour of your function. If you have a perfectly sensible answer for a corner case, just give that answer. Otherwise, you are forcing unnecessary extra case handling on your client code. And that principle also tells you which answer your code should be giving: whatever makes the client code simpler. Another example, perhaps more inspired from C conventions: Imagine you have some functions that take a timeout as an argument. After the time is up, they should fail, if they haven't produced an answer yet. Now, in these kinds of situations you often find that people choose 0 to mean an infinite timeout. That's a bad idea, because it violates simple invariants like: if you run two statements with timeouts of t0 and t1, after at most t0 + t1 seconds, you should either have an answer or get an error. (You can of course complicate the invariant by adding special cases for t0 or t1 being zero. But who likes special cases?)
deleted 7y ago
[deleted]
mgraczyk 7y ago
Another reason we must have `all([]) == True`, because `any([])` should obviously be `False`. `all(x) == not any([not v for v in x])` so `all([]) == not any([])` -> `True`
- eru 7y ago
  That's a strong hint that those definitions would make our lives easier. But it's not forcing anything? Also, I don't see why `any([]) == False` would be any more obvious than `all([]) == True`? I've seen not-so-carefully designed APIs that violate your 'obvious' logic for 'any': We had a system that you could send a list of topics, and it would return you all the datasets associated with those topics. The designer of the system decided that an empty list of topics would return all datasets, instead of nothing. I suspect their reasoning was that giving people an option to get all datasets was useful, and that predictably returning nothing was useless. But what they should have done in this situation for a clean API was to take an optional list of topics.
  - erik_seaberg 7y ago
    If you view any and all as reductions any([x, y]) == x or any([y]) == x or y or any([]) all([x, y]) == x and all([y]) == x and y and all([]) then any([]) must be false (otherwise x and y would never matter), and all([]) must be true. In the query API you're describing, does {topic1, topic2} find datasets on (topic1 OR topic2), or is it (topic1 AND topic2)? That's what determines whether more topics means more or fewer results, and whether {} should correctly find nothing or everything.
    - eru 7y ago
      > [...] then any([]) must be false (otherwise x and y would never matter), and all([]) must be true. Yes, I know. My problem is with: > Another reason we must have `all([]) == True`, because `any([])` should obviously be `False`. Argument is of the form 'A, because B'. But I don't see how B is any more obvious than A here. They seem about equally obvious.
enriquto 7y ago
Unfortunately, the min and the max of empty python lists are not +INFINITY and -INFINITY, as they should be for similar reasons.
- graup 7y ago
  Good point. I was a bit surprised when I found out that Javascript's `Math.min(...[]) ` and `Math.max(...[])` return +Infinity and -Infinity, respectively. But after thinking about it, it makes a lot of sense. It does the right thing when the argument is an empty list.
  - enriquto 7y ago
    Maybe the justification is that you do not know the type of an empty python list. But numpy at least could assume that the numbers are floats and give the correct result instead of raising an error (and thus complicating the interface).
    - throwaway_pdp09 7y ago
      > Maybe the justification is that you do not know the type of an empty python list. Excellent point, thanks!
- oefrha 7y ago
  That wouldn't make any sense. >>> min(['a', 'b']) 'a' >>> min(['a']) 'a' >>> min([]) float('-inf') # ??? An empty list is not a list of numbers. It's not a list of anything. (You can use typing hinting to indicate the type of an empty list, but type hints are ignored by the interpreter.)
  - enriquto 7y ago
    I'd rather argue that "min" only makes sense for numbers and not for other objects.
    - 7y ago
wyager 7y ago
The identity element of the conjunction (“and”) monoid is True. Any confusion here seems like a good reason we should teach students functional programming - this is straightforward if you think in terms of folds over algebraic objects. I can’t actually think of a coherent argument for returning anything besides true.
- eru 7y ago
  I'm in your camp. But the best argument I found is: "This is a confusing situation, and no boolean answer we could give would satisfy the principle of least surprise, so we should throw an error." I don't think there's a good argument to be made for returning False. As an aside: I don't think there's anything particularly related to 'functional programming' about the arguments used here. But, yet, experience with functional programming tends to make people more careful about finding general principles that give you answers for corner cases like this, too. The imperative code used in the Python standard library is just as compelling an argument for the Right Answer also being the simplest as any based in FP: def all(iterable): for element in iterable: if not element: return False return True In general, when I'm reviewing imperative code, I'm encouraging the authors to find ways to handle corner cases like empty lists organically within their code instead of with a special case check at the top. The organic handling seems to have a higher chance of producing the Right Answer.
  - wyager 7y ago
    > no boolean answer we could give would satisfy the principle of least surprise I think True follows the principle of least surprise. > I don't think there's anything particularly related to 'functional programming' about the arguments used here It imparts a better understanding of algebraic abstractions, including what it means to recursively reduce a data structure. I'm not sure how that python code is supposed to be especially simple or elucidating. I think the following Haskell code is reasonably elucidating, since it elides any need to manually define a special case or base case: all = getAll . foldMap All Where "All" is the conjunction ("and") monoid, as defined in Data.Monoid.
ummonk 7y ago
I suspect the Greeks are being mischaracterized here. Would they, for example, have considered the statement "all unicorns have a horn" to be false? In fact, the post mentions the statement "all stonemen are made of stone" which is assumed to be true under the greek logic, but according to the explanation should be false because there are no stonemen.
- eru 7y ago
  Your last example should be "all stonemen are made of wood". That would be true under one of the modern interpretations, but false under the Greek one? Your example ""all stonemen are made of stone" would be true under both modern and supposed Greek interpretations.
  - earthboundkid 7y ago
    I think Boethius would say all stonemen are made of stone is false.
    - eru 7y ago
      Hmm, I guess I have to re-read.
- earthboundkid 7y ago
  I believe the consensus literature today says Aristotle was open to indeterminate values (there’s a huge debate about the meaning of his “there will be a sea battle tomorrow” example which is taken to be indeterminate), but Boethius botched the Latin translation and said all unicorns have horns is false. I could be wrong though.
smitty1e 7y ago
Qualitatively, one is reminded of dead-beat controllers[1]. As a theoretical matter, "all unicorns are blue" is like a transfer function for a controller that can move an elevator from the bottom of the Empire State Building to the top in 0.01 seconds. Connecting words is like solving a math problem. Trying to locate that unicorn, or bringing that controller out of state space and into reality, one quickly realizes the non-existence of unicorns and that the energy applied to that elevator in order to meet the time requirement would vaporize the equipment. Requirements and metadata need not meet the realities that apply to data. [1]https://en.m.wikipedia.org/wiki/Dead-beat_control https://en.m.wikipedia.org/wiki/Dead-beat_control
- eru 7y ago
  That's intriguing, but I'm a bit confused and don't really see the connection. Could you expand?
  - smitty1e 7y ago
    My point was that as long as we're cranking formulas or stringing words together, much can seem plausible. Hard reality does not always agree. Nor do HN moderators, apparently.
    - Armisael16 7y ago
      They may have simply not understood. I’ve read your post half a dozen times and I’m still not sure what you’re trying to say.
      - smitty1e 7y ago
        Maybe I just suck like the blue unicorn.
    - eru 7y ago
      I'm not sure there's any reality involved here? But when you are building arbitrary systems, some design choices give you simpler and more applicable systems than others.
rmrfchik 7y ago
I think the very same is happening in scheme. Scheme's functions naturally works on lists: +, * , and, or. Applying it on empty lists gives us: > (and) #t > (or) #f > (+) 0 And most surprising (although it's very convenient on second thought): > (* ) 1 Thus multiplication on empty list gives 1.
- chewbacha 7y ago
  I believe that’s likely acting as a reduction with an initial value. When you sum you start with 0 and when you multiply you start with 1. These provide identity functions for the first addition and multiplication. 1 * x = x 0 + x = x
foxes 7y ago
Monoid morphism.
globular-toast 7y ago
The reason it's like this on python has nothing to do with philosophy and everything to do with algebra. The mathematical terminology sadly escapes me but essentially for each operation you want there to be a value such that application is a no-op. For addition this is 0, for multiplication 1, for and it is True and for or it is False. You want the n-ary versions of the operations to return those values for the 0 arity case. So sum([]) = 0, all([]) = True and if there was one product([]) = 1. This makes the mathematics very uniform and beautiful. Lispers know this implicitly. You know they say learning Lisp makes you a better programmer? This is an example of that. Raymond Hettinger and many of the Python authors are Lispers are heart and this is obvious to them.
- umanwizard 7y ago
  The identity element is the term you’re looking for
  - globular-toast 7y ago
    Yeah. Multiplicative identity, additive identity etc. Not sure what the name of the "andity" identity would be. Maybe just "identity of the and operation".
    - umanwizard 7y ago
      Logical "and" is also called "conjunction", so you would call it the "conjunctive identity". "False" would be the "disjunctive identity".
jhanschoo 7y ago
I'd like to note that Socrates' syllogisms only address a small fragment of predicate logic. It coexisted and competed with the propositional logic of the Stoics. Predicate logic did not achieve its power as we recognize it today until Frege. http://hume.ucdavis.edu/mattey/phi112/history.html http://hume.ucdavis.edu/mattey/phi112/history.html
cjfd 7y ago
In logic non-existing objects have all properties, including contradictory ones. This follows from the fact that in propositional calculus from a contradiction (or from False) everything can be concluded. I.e., P /\ ~ P -> Q. One could conclude that the definition of -> is not very logical but if one is to attach a formal meaning to -> it would seem hard to avoid this. One would need conditions like that when P -> Q we have to have that P and Q are related in some way but that does not sound like something that is very easy to formalize. It also does not matter whether one uses intuitionistic logic. P /\ ~ P -> Q still holds. In type theory False is the empty type and proving something about it can be done with case analysis. Since it is the empty type there are zero cases and one is immediately done and can prove anything.
sullyj3 7y ago
sum([1,1]) = 1 + 1 = 2 sum([1]) = 1 sum([]) = 0 0 + n = n + 0 = n Zero is the unit with respect to addition, so when we add together a list of no numbers, we ought to get back zero. you can `from math import prod` in python3.8 prod([2,2]) = 2*2 = 2 prod([2]) = 2 prod([]) = 1 1 * n = n * 1 = n The same way, one is the unit with respect to multiplication. So, multiplying no numbers together gets you one. all([True,True]) = True && True = True all([True]) = True all([]) = True True && x = x && True = x You get the idea.
- abathologist 7y ago
  I like the algebraic point of view as a way of spotting essential patterns like this :) The essential missing step here is to point out that conjunction is multiplicative, not additive, and this is why `all` gives the unit under conjunction, rather than the unit under disjunction. Corresponding to `sum` is `any`, which gives the unit under disjunction for the empty list, since disjunction is additive. That said, I do think there is something to the perspective presented in the article. Something which is not accidental to the algebraization of logic...
  - wyager 7y ago
    There's no need to think in terms of rings here ((+,*) and (|,&) together) - Monoids are precisely the most powerful algebraic object we need to consider here (only one binary operation at a time). All of these binary operations form a monoid.
- senthil_rajasek 7y ago
  Hmmm... An identity is something that does not change the left operand a * i = a 0 for + and 1 for x pass this test. But for Boolean && neither True nor False pass the identity test because, ( True as identity) False && True = False True && True = True ( False as identity) False && False False True && False = False Perhaps there is more to it....
  - furyofantares 7y ago
leetcrew 7y ago
idk why everyone is treating this like it's some complicated mystery. it's defined to be consistent with universal quantification (ie, ∀x) that most of us should have learned in intro to discrete. std::all_of works exactly the same way.
- capableweb 7y ago
  > most of us Who are "most of us"? People on HN? People who do programming? I've a professional programmer, but horrible at math. Don't have any formal education and even less education about discrete math. So for me this was educational and I thank the author for putting it down in writing and sharing the knowledge. I'm sure I'm not alone on HN or in the software industry with this. I'm also sure I'm sitting on bunch of knowledge you have no idea about, but when others share that, I don't shoot them down for it, I'm happy we're all helping each other understand things.
  - jakearmitage 7y ago
    You're not alone, don't worry with the gate keeping here.
  - leetcrew 7y ago
    the article itself is a decent intro explanation. I'm mainly talking about all the comments in this thread getting into monoids and abstract algebra when a sufficient explanation can be found in first-year cs material. it's a consequence of how all_of and any_of relate to each other.
    - capableweb 7y ago
      I see. Since you made a top-level comment, it seems you're commenting about the article itself. If you're replying to comments, I suggest you use the reply functionality and it all becomes a little bit clearer for everyone. I, for one, also like the comments here as they expand and dive into more topics that again, "some of us" have not read/heard about before so grateful for that.
- 7y ago
amai 7y ago
Shouldn't all() simply throw an exception in case of an empty list?
maest 7y ago
This is in no way Python-specific.
housecarpenter 7y ago
I may be blinkered by my mathematical training, but to me this seems like the obvious thing to do. Here's an attempt to justify it based on common sense, no math stuff required. Suppose you do something like if(all(requirements)) { proceed; } If there are no requirements that need to be satisfied, then you should be able to proceed.
- tprice7 7y ago
  Another way to make it seem more intuitive: "all of these are true" is the same as "none of these are false" (assuming values must be booleans), and clearly nothing in an empty list is false.
- earthboundkid 7y ago
  > I may be blinkered by my mathematical training Yes, precisely the point of the article. We mostly find it natural to think like moderns today, but civilization went along for thousands of years thinking differently.
tny 7y ago
Is there any language where this isnt true?
- earthboundkid 7y ago
  English.
sn41 7y ago
This is in fact the logically meaningful thing to do. All must be monotone decreasing in set inclusion. Other similar definitions are that min of an empty set is infinity and max of an empty set is minus infinity. Min is monotone decreasing over set inclusion hence min of empty set must be the maximum possible value. Max is montone increasing in ser inclusion hence max of empty set must be the smallest possible value.
co_dh 7y ago
True is the unit of logic and as a monoid. You know math is useful.
smabie 7y ago
The answer: otherwise the existential quantifier wouldn't work (since you can transform forall x into there does not exist a not x). When you use the existential quantifier, it makes sense. I'm not sure how this is relevant to python, this question is purely in the domain of first order predicate logic.

189 points by earthboundkid 7y ago

celias 7y ago

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

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

deleted 7y ago

[deleted]

AllasAskBar 7y ago

lol when people forget the original intent behind words

haecceity 7y ago

Maybe it should throw an exception

aivisol 7y ago
Why? All unicorns are blue, aren't they?
- kzrdude 7y ago
  I'm not sure, but all unicorns I've seen have been blue.
- TimonKnigge 7y ago
  > All unicorns are blue, aren't they? Indeed they aren't! All unicorns are not blue.
  - aivisol 7y ago
    True
- tzs 7y ago
  I’ve seen a lot of experimental evidence for that. "All unicorns are blue" is logically equivalent to "all non-blue things are not unicorns". Over the past few decades I’ve seen ten of thousands of non-blue things, and none of them were unicorns! https://en.wikipedia.org/wiki/Raven_paradox https://en.wikipedia.org/wiki/Raven_paradox
  - jerf 7y ago
    Contrapositives are one of my favorite things in simple logic to demonstrate the difference between rigorous logic and our human heuristic logic. Mathematically, contrapositives are identical to the original statement, but extremely frequently, if not almost always, they sound different to us humans. If more people understood them, there's a number of dumb internet debates that could finally die, where X -> Y isn't immediately obviously wrong to our human brains and may even sound correct but !Y -> !X is immediately obviously wrong.

wirrbel 7y ago

Works as expected I'd say.

TimonKnigge 7y ago

`all(x + y) = all(x) and all(y)` even when `x, y` can be the empty list.

syphilis2 7y ago

Epicycles. Experience leaves me inclined to believe the code precedes the definition. def all(iterable): for element in iterable: if not element: return False return True https://github.com/python/cpython/blob/master/Python/bltinmodule.c https://github.com/python/cpython/blob/master/Python/bltinmo...

eru 7y ago
But that doesn't tell you _why_ that choice is a good idea! My favourite explanation comes from property based testing. In general, you have the following property: For any lists xs and ys, all(xs) and all(ys) == all(xs + ys) If you want to keep that property as simple as possible, you have to define all([]) == True If you want to go with the opposite, your property becomes more complicated. Mathematical definitions are somewhat arbitrary. It's up to us to choose definitions that make sense in our contexts. A general desire to make the resulting systems simple and uniform worked out well for many, many context. Slight detour: that's also why defining 2 - 5 to have an answer is a good idea! Negative numbers were seen as a bit suspect, but they behave perfectly sensible. Same for complex numbers. But: still we generally leave 0 / 0 undefined, because no answer would lead to a satisfying system.
- gridlockd 7y ago
  > But that doesn't tell you _why_ that choice is a good idea! That wasn't necessarily a choice, it may have just been an oversight not to deal with the "empty list" case. The fact that this blog post exists is a testament to this behavior being surprising. I don't think any of the arguments - philosophical or otherwise - are very good from a practical standpoint, that is: is this behavior is not more likely to cause harm? My gut feeling says that this behavior is somewhat unsafe, but then again Python is probably not the language to use when safety is a big concern. A hypothetical safer language might be better off to define "all/any" only for non-empty list.
  - eru 7y ago
    Haskell, the prototypical careful language, defines their equivalents for 'any' and 'all' exactly like Python does it. And that's not an accident. > That wasn't necessarily a choice, it may have just been an oversight not to deal with the "empty list" case. If your general code gives you a answer for a corner case, it's a good hint that this might be a reasonable answer. Not a guarantee, though.

chrismsimpson 7y ago

In Swift, I would image I could define this method as throwing an error in such a case, nixing the debate entirely. Why Swift specifically? This would be in the calling signature, implying there are inputs you can give said method that are nonsensical.

eru 7y ago
You'd just open another debate. Your client code has to work with the behaviour of your function. If you have a perfectly sensible answer for a corner case, just give that answer. Otherwise, you are forcing unnecessary extra case handling on your client code. And that principle also tells you which answer your code should be giving: whatever makes the client code simpler. Another example, perhaps more inspired from C conventions: Imagine you have some functions that take a timeout as an argument. After the time is up, they should fail, if they haven't produced an answer yet. Now, in these kinds of situations you often find that people choose 0 to mean an infinite timeout. That's a bad idea, because it violates simple invariants like: if you run two statements with timeouts of t0 and t1, after at most t0 + t1 seconds, you should either have an answer or get an error. (You can of course complicate the invariant by adding special cases for t0 or t1 being zero. But who likes special cases?)

deleted 7y ago

[deleted]

mgraczyk 7y ago

Another reason we must have `all([]) == True`, because `any([])` should obviously be `False`. `all(x) == not any([not v for v in x])` so `all([]) == not any([])` -> `True`

eru 7y ago
That's a strong hint that those definitions would make our lives easier. But it's not forcing anything? Also, I don't see why `any([]) == False` would be any more obvious than `all([]) == True`? I've seen not-so-carefully designed APIs that violate your 'obvious' logic for 'any': We had a system that you could send a list of topics, and it would return you all the datasets associated with those topics. The designer of the system decided that an empty list of topics would return all datasets, instead of nothing. I suspect their reasoning was that giving people an option to get all datasets was useful, and that predictably returning nothing was useless. But what they should have done in this situation for a clean API was to take an optional list of topics.
- erik_seaberg 7y ago
  If you view any and all as reductions any([x, y]) == x or any([y]) == x or y or any([]) all([x, y]) == x and all([y]) == x and y and all([]) then any([]) must be false (otherwise x and y would never matter), and all([]) must be true. In the query API you're describing, does {topic1, topic2} find datasets on (topic1 OR topic2), or is it (topic1 AND topic2)? That's what determines whether more topics means more or fewer results, and whether {} should correctly find nothing or everything.
  - eru 7y ago
    > [...] then any([]) must be false (otherwise x and y would never matter), and all([]) must be true. Yes, I know. My problem is with: > Another reason we must have `all([]) == True`, because `any([])` should obviously be `False`. Argument is of the form 'A, because B'. But I don't see how B is any more obvious than A here. They seem about equally obvious.

enriquto 7y ago

Unfortunately, the min and the max of empty python lists are not +INFINITY and -INFINITY, as they should be for similar reasons.

graup 7y ago
Good point. I was a bit surprised when I found out that Javascript's `Math.min(...[]) ` and `Math.max(...[])` return +Infinity and -Infinity, respectively. But after thinking about it, it makes a lot of sense. It does the right thing when the argument is an empty list.
- enriquto 7y ago
  Maybe the justification is that you do not know the type of an empty python list. But numpy at least could assume that the numbers are floats and give the correct result instead of raising an error (and thus complicating the interface).
  - throwaway_pdp09 7y ago
    > Maybe the justification is that you do not know the type of an empty python list. Excellent point, thanks!
oefrha 7y ago
That wouldn't make any sense. >>> min(['a', 'b']) 'a' >>> min(['a']) 'a' >>> min([]) float('-inf') # ??? An empty list is not a list of numbers. It's not a list of anything. (You can use typing hinting to indicate the type of an empty list, but type hints are ignored by the interpreter.)
- enriquto 7y ago
  I'd rather argue that "min" only makes sense for numbers and not for other objects.
  - 7y ago

wyager 7y ago

The identity element of the conjunction (“and”) monoid is True. Any confusion here seems like a good reason we should teach students functional programming - this is straightforward if you think in terms of folds over algebraic objects. I can’t actually think of a coherent argument for returning anything besides true.

eru 7y ago
I'm in your camp. But the best argument I found is: "This is a confusing situation, and no boolean answer we could give would satisfy the principle of least surprise, so we should throw an error." I don't think there's a good argument to be made for returning False. As an aside: I don't think there's anything particularly related to 'functional programming' about the arguments used here. But, yet, experience with functional programming tends to make people more careful about finding general principles that give you answers for corner cases like this, too. The imperative code used in the Python standard library is just as compelling an argument for the Right Answer also being the simplest as any based in FP: def all(iterable): for element in iterable: if not element: return False return True In general, when I'm reviewing imperative code, I'm encouraging the authors to find ways to handle corner cases like empty lists organically within their code instead of with a special case check at the top. The organic handling seems to have a higher chance of producing the Right Answer.
- wyager 7y ago
  > no boolean answer we could give would satisfy the principle of least surprise I think True follows the principle of least surprise. > I don't think there's anything particularly related to 'functional programming' about the arguments used here It imparts a better understanding of algebraic abstractions, including what it means to recursively reduce a data structure. I'm not sure how that python code is supposed to be especially simple or elucidating. I think the following Haskell code is reasonably elucidating, since it elides any need to manually define a special case or base case: all = getAll . foldMap All Where "All" is the conjunction ("and") monoid, as defined in Data.Monoid.

ummonk 7y ago

I suspect the Greeks are being mischaracterized here. Would they, for example, have considered the statement "all unicorns have a horn" to be false? In fact, the post mentions the statement "all stonemen are made of stone" which is assumed to be true under the greek logic, but according to the explanation should be false because there are no stonemen.

eru 7y ago
Your last example should be "all stonemen are made of wood". That would be true under one of the modern interpretations, but false under the Greek one? Your example ""all stonemen are made of stone" would be true under both modern and supposed Greek interpretations.
- earthboundkid 7y ago
  I think Boethius would say all stonemen are made of stone is false.
  - eru 7y ago
    Hmm, I guess I have to re-read.
earthboundkid 7y ago
I believe the consensus literature today says Aristotle was open to indeterminate values (there’s a huge debate about the meaning of his “there will be a sea battle tomorrow” example which is taken to be indeterminate), but Boethius botched the Latin translation and said all unicorns have horns is false. I could be wrong though.

smitty1e 7y ago

Qualitatively, one is reminded of dead-beat controllers[1]. As a theoretical matter, "all unicorns are blue" is like a transfer function for a controller that can move an elevator from the bottom of the Empire State Building to the top in 0.01 seconds. Connecting words is like solving a math problem. Trying to locate that unicorn, or bringing that controller out of state space and into reality, one quickly realizes the non-existence of unicorns and that the energy applied to that elevator in order to meet the time requirement would vaporize the equipment. Requirements and metadata need not meet the realities that apply to data. [1]https://en.m.wikipedia.org/wiki/Dead-beat_control https://en.m.wikipedia.org/wiki/Dead-beat_control

eru 7y ago
That's intriguing, but I'm a bit confused and don't really see the connection. Could you expand?
- smitty1e 7y ago
  My point was that as long as we're cranking formulas or stringing words together, much can seem plausible. Hard reality does not always agree. Nor do HN moderators, apparently.
  - Armisael16 7y ago
    They may have simply not understood. I’ve read your post half a dozen times and I’m still not sure what you’re trying to say.
    - smitty1e 7y ago
      Maybe I just suck like the blue unicorn.
  - eru 7y ago
    I'm not sure there's any reality involved here? But when you are building arbitrary systems, some design choices give you simpler and more applicable systems than others.

rmrfchik 7y ago

I think the very same is happening in scheme. Scheme's functions naturally works on lists: +, * , and, or. Applying it on empty lists gives us: > (and) #t > (or) #f > (+) 0 And most surprising (although it's very convenient on second thought): > (* ) 1 Thus multiplication on empty list gives 1.

chewbacha 7y ago
I believe that’s likely acting as a reduction with an initial value. When you sum you start with 0 and when you multiply you start with 1. These provide identity functions for the first addition and multiplication. 1 * x = x 0 + x = x

foxes 7y ago

Monoid morphism.

globular-toast 7y ago

The reason it's like this on python has nothing to do with philosophy and everything to do with algebra. The mathematical terminology sadly escapes me but essentially for each operation you want there to be a value such that application is a no-op. For addition this is 0, for multiplication 1, for and it is True and for or it is False. You want the n-ary versions of the operations to return those values for the 0 arity case. So sum([]) = 0, all([]) = True and if there was one product([]) = 1. This makes the mathematics very uniform and beautiful. Lispers know this implicitly. You know they say learning Lisp makes you a better programmer? This is an example of that. Raymond Hettinger and many of the Python authors are Lispers are heart and this is obvious to them.

umanwizard 7y ago
The identity element is the term you’re looking for
- globular-toast 7y ago
  Yeah. Multiplicative identity, additive identity etc. Not sure what the name of the "andity" identity would be. Maybe just "identity of the and operation".
  - umanwizard 7y ago
    Logical "and" is also called "conjunction", so you would call it the "conjunctive identity". "False" would be the "disjunctive identity".

jhanschoo 7y ago

I'd like to note that Socrates' syllogisms only address a small fragment of predicate logic. It coexisted and competed with the propositional logic of the Stoics. Predicate logic did not achieve its power as we recognize it today until Frege. http://hume.ucdavis.edu/mattey/phi112/history.html http://hume.ucdavis.edu/mattey/phi112/history.html

cjfd 7y ago

In logic non-existing objects have all properties, including contradictory ones. This follows from the fact that in propositional calculus from a contradiction (or from False) everything can be concluded. I.e., P /\ ~ P -> Q. One could conclude that the definition of -> is not very logical but if one is to attach a formal meaning to -> it would seem hard to avoid this. One would need conditions like that when P -> Q we have to have that P and Q are related in some way but that does not sound like something that is very easy to formalize. It also does not matter whether one uses intuitionistic logic. P /\ ~ P -> Q still holds. In type theory False is the empty type and proving something about it can be done with case analysis. Since it is the empty type there are zero cases and one is immediately done and can prove anything.

sullyj3 7y ago

sum([1,1]) = 1 + 1 = 2 sum([1]) = 1 sum([]) = 0 0 + n = n + 0 = n Zero is the unit with respect to addition, so when we add together a list of no numbers, we ought to get back zero. you can `from math import prod` in python3.8 prod([2,2]) = 2*2 = 2 prod([2]) = 2 prod([]) = 1 1 * n = n * 1 = n The same way, one is the unit with respect to multiplication. So, multiplying no numbers together gets you one. all([True,True]) = True && True = True all([True]) = True all([]) = True True && x = x && True = x You get the idea.

abathologist 7y ago
I like the algebraic point of view as a way of spotting essential patterns like this :) The essential missing step here is to point out that conjunction is multiplicative, not additive, and this is why `all` gives the unit under conjunction, rather than the unit under disjunction. Corresponding to `sum` is `any`, which gives the unit under disjunction for the empty list, since disjunction is additive. That said, I do think there is something to the perspective presented in the article. Something which is not accidental to the algebraization of logic...
- wyager 7y ago
  There's no need to think in terms of rings here ((+,*) and (|,&) together) - Monoids are precisely the most powerful algebraic object we need to consider here (only one binary operation at a time). All of these binary operations form a monoid.
senthil_rajasek 7y ago
Hmmm... An identity is something that does not change the left operand a * i = a 0 for + and 1 for x pass this test. But for Boolean && neither True nor False pass the identity test because, ( True as identity) False && True = False True && True = True ( False as identity) False && False False True && False = False Perhaps there is more to it....
- furyofantares 7y ago

leetcrew 7y ago

idk why everyone is treating this like it's some complicated mystery. it's defined to be consistent with universal quantification (ie, ∀x) that most of us should have learned in intro to discrete. std::all_of works exactly the same way.

capableweb 7y ago
> most of us Who are "most of us"? People on HN? People who do programming? I've a professional programmer, but horrible at math. Don't have any formal education and even less education about discrete math. So for me this was educational and I thank the author for putting it down in writing and sharing the knowledge. I'm sure I'm not alone on HN or in the software industry with this. I'm also sure I'm sitting on bunch of knowledge you have no idea about, but when others share that, I don't shoot them down for it, I'm happy we're all helping each other understand things.
- jakearmitage 7y ago
  You're not alone, don't worry with the gate keeping here.
- leetcrew 7y ago
  the article itself is a decent intro explanation. I'm mainly talking about all the comments in this thread getting into monoids and abstract algebra when a sufficient explanation can be found in first-year cs material. it's a consequence of how all_of and any_of relate to each other.
  - capableweb 7y ago
    I see. Since you made a top-level comment, it seems you're commenting about the article itself. If you're replying to comments, I suggest you use the reply functionality and it all becomes a little bit clearer for everyone. I, for one, also like the comments here as they expand and dive into more topics that again, "some of us" have not read/heard about before so grateful for that.
7y ago

amai 7y ago

Shouldn't all() simply throw an exception in case of an empty list?

maest 7y ago

This is in no way Python-specific.

housecarpenter 7y ago

I may be blinkered by my mathematical training, but to me this seems like the obvious thing to do. Here's an attempt to justify it based on common sense, no math stuff required. Suppose you do something like if(all(requirements)) { proceed; } If there are no requirements that need to be satisfied, then you should be able to proceed.

tprice7 7y ago
Another way to make it seem more intuitive: "all of these are true" is the same as "none of these are false" (assuming values must be booleans), and clearly nothing in an empty list is false.
earthboundkid 7y ago
> I may be blinkered by my mathematical training Yes, precisely the point of the article. We mostly find it natural to think like moderns today, but civilization went along for thousands of years thinking differently.

tny 7y ago

Is there any language where this isnt true?

earthboundkid 7y ago
English.

sn41 7y ago

This is in fact the logically meaningful thing to do. All must be monotone decreasing in set inclusion. Other similar definitions are that min of an empty set is infinity and max of an empty set is minus infinity. Min is monotone decreasing over set inclusion hence min of empty set must be the maximum possible value. Max is montone increasing in ser inclusion hence max of empty set must be the smallest possible value.

co_dh 7y ago

True is the unit of logic and as a monoid. You know math is useful.

smabie 7y ago

The answer: otherwise the existential quantifier wouldn't work (since you can transform forall x into there does not exist a not x). When you use the existential quantifier, it makes sense. I'm not sure how this is relevant to python, this question is purely in the domain of first order predicate logic.