Why does all() return True if the iterable is empty?

https://blog.carlmjohnson.net/post/2020/python-square-of-opposition/

by vikrum • 3 years ago

134 194 3 years ago

blog.carlmjohnson.net

rightbyte3• 3 years ago

   > all([])
   True
   > any([])
   False

Not very consistent philosophy in that case. Surely if 'all' is True then 'any' got to be too?

orf• 3 years ago

Going by the example in the post, "all unicorns are blue" seems truthy whereas "are any unicorns blue" seems falsey in a world with no unicorns?

JadeNB• 3 years ago

Surely if 'all' is True then 'any' got to be too?

No. `any([])` means "some element of [] is true", which is false because there aren't any elements. `all([])` means "all elements of [] are true", which is true because it's (classically, anyway) got to be true or false, and being false would require that there be some element of [] that isn't true, which there isn't.

More generally, `!all([!x for x in xs])` (or whatever the syntax is; I'm not a Python programmer)—meaning "it's not the case that the negation of every element of xs is true"—is `any(xs)`, so `!all([])` is `any([])`.

CJefferson2• 3 years ago

It is consistent, and in practice this is the only definition that ends up being sensible, if you play with lots of examples. I have done this as a, I believe, surprisingly fun thing with older school children, where we think about all the things we want to be true about all, and any, and then figure out what the answers are.

Some examples are "if something is true for 'all students', it should be true for any group of students", and if "all students have a hat" is true, then it should not be true that "any student had no hat", etc.

thewakalix• 3 years ago

`any` corresponds to the existential quantifier, not the universal.

Arnavion• 3 years ago

any(collection, predicate) == not(all(collection, not(predicate))). Or in English, "It is true that there is an even number in this list." is the same as "It is false that all the numbers in this list are odd."

zem• 3 years ago

think of "any" as "we can find an element for which this is true", and "all" as "we cannot find an element for which this is false"

knappa• 3 years ago

I would read all more formally as: for each element in this list, the element is true. Then you get a vacuous truth. (Think about the negation: there is an element in the list which is false. That's obviously false.)

Any would be more formally: there is an element of the list which is true. But the list doesn't have any elements, so that's false.

Looks logical to me. Plus you get that `not any( map(lambda x: not x, l) )` is the same as `all(l)` for any list `l`.

rightbyte3• 3 years ago

Any would be more formally: there is an element of the list which is true. But the list doesn't have any elements, so that's false.

It is just a matter of convention and I see no logic behind why any convention would be worse or wrong. But I believe if 'any' implies 'at least one' so should 'all' otherwise they use different conventions.

In practice I get it was arbitrary choices and this is just how you end up when doing the obvious implementation.

   def all(l):
      for e in l:
         if not e:
            return False
      return True

   def any(l):
      for e in l:
         if e:
            return True
      return False

petesergeant• 3 years ago

To prove “do all x satisfy y” you need to find an example that is not.

In order to satisfy “does any x satisfy y” you need find an example that does.

shawnz2• 3 years ago

How could they both have the same answer? They must have opposite answers because of De Morgan's law: asking "is any item true" is the same as asking "are NOT all items NOT true"

Sohcahtoa82• 3 years ago

Think of it this way...

You're logging incoming web requests and then gathering statistics in 5 minute intervals.

During one interval, you get no requests.

You check to see...did "all" of the requests get processed without errors? The answer is Yes, because to say No would imply there were errors.

Did "any" of the requests cause an error? The answer is No, because to say Yes would imply at least one error.

mrkeen2• 3 years ago

No need for philosophy.

    any (<5)  [6,7,8]
    any (<5) ([6,7,8]  ++           [])
   (any (<5)  [6,7,8]) || (any (<5) [])
    False              || True
    True

earthboundkid6• 3 years ago

No need for philosophy, we can just use whatever assumptions underlie our technology without any reflection on what they are or how they got their.

rgovostes• 3 years ago

    all([x]+x)

Minor49er• 3 years ago

Why try to reduce assertions made against something that doesn't exist down to a boolean result? Clearly the answer is undefinable

neuromanser5• 3 years ago

The assertion is against the set (list in the TFA).

rwmj• 3 years ago

It makes recursion easier. For example:

  ∀(head::tail) = head ∩ ∀(tail)

if ∀([]) is defined as true then this works for the single element list.

IshKebab• 3 years ago

It's easily definable. all(x) is true iff none of the elements in x are false. This is really the only sane option. To do anything else would be a weird special case for []. Like defining len([]) == None. There's no point; it just makes everything more complicated and worse.

neuromanser5• 3 years ago

In logic, this is called the principle of bivalence: there are only two values that a proposition can have, true or false. But Python has None, many other programming languages have null or nil, and Zen has mu. Maybe adding another value would help?

Hoare labeled his invention of null a "billion dollar mistake". SQL NULL can't be far behind. Boolean logic has 4 unary and 16 binary operators, ternary logic has 27 and 19683, respectively. That's not helpful, that's intractable!

I cannot recommend C. J. Date's books enough.

jewel• 3 years ago

SQL NULL can't be far behind.

SQL's NULL is far more useful though, since NULL != NULL. That lets you do things like join two tables with a column and not have the NULLs match.

Consider, for example:

    select * from users where id = null;

That will give 0 results, even if somehow you have a user with a null id.

It's also really nice for non-ID, non-reference fields to represent N/A. For example, user.birthdate can be NULL if the birthdate is not known.

SQL also lets you choose when you want NULL to be allowed for a column, so it's less likely to be a gotcha.

tomp• 3 years ago

For anyone wondering how to fix the above query so that it works for arbitrary X (which can be NULL or non-NULL):

    SELECT * FROM users WHERE status IS NOT DISTINCT FROM $x

neuromanser5• 3 years ago

SQL's NULL is far more useful though, since NULL != NULL.

That's not true! (Nor is it false.) NULL = NULL IS NULL, NULL != NULL IS NULL. I can't overstate this: as soon as either (or both) operand of any binary relational operator is NULL, the whole expression is NULL!

I'm not being an asshole, this is the exact mistake that makes SQL NULL the other billion dollar sink!

This is really funny, because i wasn't aware of laying such a beatiful trap.

neuromanser5• 3 years ago

Consider, for example: select * from users where id = null; That will give 0 results, even if somehow you have a user with a null id.

Why is it useful? Can you elaborate?

Smaug1235• 3 years ago

The mistake of `null` is _not_ that it exists at all - it's often the case that you can't answer a question, and it's extremely useful to be able to model your inability to answer a question! The mistake of `null` is instead that it forces every reference type to be an optional. This is a mistake because some things can in fact be known. In practice, when everything is optional, it's so boilerplate-heavy to enforce the condition "this is known" at runtime for every property that everyone inevitably ends up not enforcing that condition most of the time; the bugs arise when one side of a boundary assumes for expediency that the other side has enforced it.

It is in general very reasonable for a function to return an optional bool; think of `List.tryHead [false, true, false]`. What is unreasonable is for all boolean functions to return optional bools.

dkersten• 3 years ago

“Are there any items in this list that are true? No? Ok, then False”

I don’t care about any fancy philosophy. What’s important is what kind of operation you want for when implementing algorithms, and False is what I always want in cases where I do “all”.

kadoban• 3 years ago

“Are there any items in this list that are true? No? Ok, then False”

There's no particular reasoning that this is any more compelling than: “Are there any items in this list that are false? No? Ok, then True”

jamilton• 3 years ago

"is any item in this list true" is any(), which is different from all().

CJefferson2• 3 years ago

Can you give a couple of examples where you want False for an empty all? I'd be interested to see them, as I've found I always want True.

robot_no_4212• 3 years ago

What’s important is what kind of operation you want for when implementing algorithms, and False is what I always want in cases where I do “all”.

Why would you want "all" to produce results that are inconsistent with logic and mathematics? Consider this tautology, which is a result of De Morgan's laws: for any list L, we have that

all(L) == ~any([~x for x in L]).

In other words, if all([]) == False, then you would also logically need to accept that:

False == all([]) == ~any([~x for x in []]) == ~any([])

which means that we'd require any([]) == True. And that's definitely an illogical result.

stop50• 3 years ago

You can define all() as "is there any False item?" Which is False for an empty list, but true for any list with an false item. all(list) == anyfalse(list)

shawnz2• 3 years ago

You're describing the "any" function, which actually does return false in that case already.

edflsafoiewq2• 3 years ago

  all = foldr and True
  any = foldr or False

hiAndrewQuinn• 3 years ago

So glad I know this language

xcdzvyn• 3 years ago

Man I love Haskell.

aportnoy• 3 years ago

1 is the multiplicative identity

0 is the additive identity

all([]) is True

any([]) is False

kubb• 3 years ago

Every one (all) of the set of zero elements is true. It's not counterintuitive or inconsistent, this is the only way that makes sense.

The complement is also consistent. None of the set of zero elements are true. So there aren't any true's.

They're symmetrical cases, and negation turns them into each other. Not-any-true is equivalent to all-false, and not-all-true is equivalent to any-false.

aib• 3 years ago

It's the identity element of the monoid, no?

Similarly, the product of an empty list should be 1.

tromp• 3 years ago

If all marbles in a bag are black, and you take one marble out, are all marbles in the bag still black?

The only logical answer is yes. It would be rather absurd to make an exception for the case where you start with one marble in the bag. That would make logical reasoning extremely cumbersome, for no benefit whatsoever.

Eldt• 3 years ago

That's not an exception, that's a different situation...

jackbrookes• 3 years ago

not really

    marbles = (BlackMarble() for _ in range(random.randint(0, 10)))
    all(isinstance(m, BlackMarble) for m in marbles)

Surely should always be true

cedilla• 3 years ago

Is it?

If that case is so different, than the case with two marbles is also different - because removing the second-to-last marble will change will change the bag to be in that situation. But then, the case with three marbles is also different, and by induction you are left with only special cases.

On the other hand, see the related statement "If all marbles in a bag are black, adding a red marble will result in a mixed bag" clearly fails for the empty bag.

This isn't really a question of logic or mathematics. Mathematicians just use systems which are useful. And predicate logic, which has proven invaluable, would allow OP's claim.

bowsamic2• 3 years ago

If all marbles in a bag are black, and you take one marble out, are all marbles in the bag still black?
The only logical answer is yes.

The only "logical answer" is "there are no marbles in the bag". If this must be cast to a boolean somehow, the only "logical answer" is no. There should be a discontinuity as the last black marble is removed. That isn't absurd at all

jimmaswell• 3 years ago

Look into formal boolean logic, specifically the "therefore" operator. (T->T)=T,(T->F)=F, but starting with a false premise always results in true. There's good reason for it and it makes other things work out how you'd expect.

A marble is in the bag -> the marble is black = True, even if there are no marbles in the bag. You can consider the "all" method as asking for the truth value of "A marble is in the bag -> the marble is black"

wan23• 3 years ago

Without knowing how many marbles are in the bag, if you say that not all the marbles in the bag are black, then I'm going to ask you to show me a non-black marble to prove it. Alternatively, I can prove that all the marbles are black by showing you n marbles that are black where n is the number of marbles in the bag. Here you go, zero black marbles!

dragonwriter5• 3 years ago

If all marbles in a bag are black, and you take one marble out, are all marbles in the bag white?

The only logical answer is no. It would be rather absurd to make an exception for the case where you start with one marble in the bag... and yet:

  marbles = ["black"]
  marbles.pop()
  all(m=="white" for m in marbles) # => True

bandyaboot2• 3 years ago

Though it feels strange to write this, the fact that all the marbles are white doesn't change the fact that they're all black...and transparent, and not marbles at all, etc...

p1mrx• 3 years ago

If all marbles in a bag are black, and you take one marble out, are all marbles in the bag white?

The logical answer is "maybe."

neves• 3 years ago

my pragmatic view is that it should be false.

A common error would be a programming mistake in the selection of the list element return an empty list. The returned list would, unexpectedly, comes empty. Trying to check if everything is black would return True and the code would follow on. It would be very hard to debug

chongli• 3 years ago

The mistake you’re making here is by treating the statement “all marbles are white” as the negation of “all marbles are black” and claiming that this violates the law of the excluded middle.

But we are operating under predicate logic. The negation of “all marbles in the bag are black” is “there is a marble in the bag which is not black”. Then, clearly the latter statement is false in the case of an empty bag.

In fact, we can confidently claim falsity for any given statement of the form “there is a marble in the bag such that…” when the bag is empty. Therefore, by the law of the excluded middle, its negation is true, so statements of the form “all marbles in the bag are…” are vacuously true when the bag is empty.

fasterik4• 3 years ago

Your proposal would break all of logic and mathematics.

"All marbles in the bag are white" is equivalent to "For all x, if x is a marble and x is in the bag, then x is white". Since the antecedent is false if the bag is empty, the statement is true by material implication.

bandyaboot2• 3 years ago

Ultimately I agree with the conclusion, but the logic of how you're getting there seems flawed in that the question you're asking doesn't add any value. The fundamental question is whether all marbles in a bag of n black marbles are black for all values of n including 0. If the answer to that question is yes, then the answer to your question is yes. If the answer is no, then the answer to your question is "yes except if it results in n=0".

saurik2• 3 years ago

The point was (explicitly) that it would be awkward to add the n=1->0 corner case.

Someone• 3 years ago

An alternative way to see why that’s the most logical viewpoint is, that, if you assume not all marbles in an empty bag are black, you can have the following:

- Take a bag for which “all marbles in this bag are black” is false

- Add a black marble to that bag

- After that, “all marbles in the bag are black” becomes true

As is often the case in mathematics/logic [1] with these kind of things, you can hold an alternative view where “are all marbles in this bag black” doesn’t make sense for an empty bag or one where it has the answer “yo”, but if you do that, you’ll find that many proofs get more cumbersome because you have to handle that case differently from all other cases.

[1] other examples are the convention that 0⁰ = 1 and the convention that 1 isn’t a prime number (that’s an example where mathematicians (eventually) decided that having 3 kinds of positive integers (prime numbers, composite numbers, and 1) is the better choice)

marktani2• 3 years ago

edit: totally misunderstood parent, my bad. disregard the following.

- Take a bag for which “all marbles in this bag are black” is false
- Add a black marble to that bag
- After that, “all marbles in the bag are black” becomes true

This reasoning is not correct. If the bag contains exactly a red marble at the start, "all marbles in this bag are black" is false as you required, but it breaks the claim at the end that "all marbles in the bag are black".

There is in fact no bag that fulfills your reasoning, even the empty bag wouldn't (when starting to write my reply I had erroneously assumed so)

NoThisIsMe• 3 years ago

That's not the question. The question is: If there are no marbles in a bag, are all marbles in the bag black?

Smaug1235• 3 years ago

I think you've misunderstood. The question you posed has an answer implied by the parent's question with n=1.

twiceaday• 3 years ago

Sounds weird when you ask the question that way, but if you ask "is there a non-black marble in the bag?" the answer is clearly no. So the question is more like: Should "all marbles in the bag are black" be exactly equal to "not(is there a non-black marble in the bag)".

jayd162• 3 years ago

Isn't this like complaining about division by zero? Why make an exception? Well...because its exceptional.

So it's consistent to say that a bag can contain all red and all black marbles at the same time?

dkarl• 3 years ago

Translating it to idiomatic natural language makes it less clear, because the natural language statement "all marbles in the bag are black" implies that there are marbles in the bag. The question is, why do we interpret it differently in a logical/mathematical context?

As with anything mathematical, we picked the way that yields useful and elegant mathematics. The notion of "all" would be awkward to work with if it did not apply to the empty set (bags without marbles) so we extended it in a way that is consistent with what it means over non-empty sets (bags with marbles.)

One very nice thing about this definition of "all" is that it gives this simple relationship between logical "all" and logical "none":

"for all x, P(x) is true" is equivalent to "there is no x for which P(x) is false"

I.e., if there is no marble in the bag that is not black, then all marbles in the bag are black... so to speak.

This yields elegant and useful mathematics, and (as you would expect) that tends to mean elegant and useful code as well.

For example, suppose you had an enormous dataset of records that included zip codes and wanted to know: "Are all the zip codes in this dataset in the continental United States?" One approach would be to split the data into smaller shards, answer the question for each shard, and "and" all the answers together. What if you chose a bad way of sharding the data and one of the shards was empty? What result would you want returned for that shard?

SkyPuncher• 3 years ago

The answer should be no. Though, it’s understandably ambiguous.

Black is a property of a marble. Without a marble, black cannot evaluate to true. Therefore zero marbles equals “no”

feoren6• 3 years ago

All cell phones must be turned off before the movie will begin.

Oh wait, nobody in the audience has a cell phone. Can the movie begin?

Without a marble, black cannot evaluate to true. Therefore zero marbles equals “no”

"Is_Black" cannot evaluate to false either, therefore zero marbles equals "yes". But that's wrong too, because it is never evaluated, because there are no marbles to evaluate it on. TRUE is the identity of AND, and ALL is the aggregation of AND, so ALL([]) == TRUE. Put another way:

If you start from a bag with N black marbles and split it up between M bags, can you say that for each new bag, all the marbles in it must be black? Yes, you can. That is, if you find a marble in the bag, it will be black. This still holds even if one bag doesn't happen to get any marbles.

fasterik4• 3 years ago

Your proposal would break all of logic and mathematics.

"All marbles in the bag are black" is equivalent to "For all x, if x is a marble and x is in the bag, then x is black". Since the antecedent is false if the bag is empty, the statement is true by material implication.

pharrington• 3 years ago

There are zero marbles. All zero of the marbles are black. All zero of the marbles are white. There are zero marbles.

Salgat• 3 years ago

"all" and "none" are simultaneously true, which makes this a tricky edge case that needs to be explicitly accounted for.

dragonwriter5• 3 years ago

Its necessary that all and none are both true of empty lists, if they are both defined for empty lists, because otherwise the invariant that all(xs) == none(not x for x in xs) [0] would not hold.

[0] yes, “none()” doesn’t actually exist in Python, but we can imagine that it did, and see that if it did, it should have this relationship.)

hoosieree• 3 years ago

A man walks into a shop and asks, "You wouldn't happen to have any fish, would you?" The shop assistant replies, "You've got it wrong – ours is a butcher's shop. We don't have any meat. You're looking for the fish shop across the road. There they don't have any fish!"

schubart• 3 years ago

“I’d like a coffee, please. Without milk.”

“Apologies, we’re out of milk. Could I offer you a coffee without sugar instead?”

manlobster• 3 years ago

Given:

    all(xs + ys) == (all(xs) and all(ys))

And:

    xs == xs + []

We have:

    all(xs) == all(xs + []) == all(xs) and all([])

Which implies:

    all([]) == True.

toxik• 3 years ago

I like this variant, it also works to show why any([]) is False.

Smaug1235• 3 years ago

Although it's presumably much less controversional that `any([])` is false. After all, most people presumably think of an existential statement as being satisfied precisely when there's a witness to that statement, and of course an empty list contains no witnesses to any statement.

whoopdedo• 3 years ago

    def all(L):
        for i in L:
            if not L:
                return False
        return True

Seems quite clear when presented that way. Same with `any`.

In logic, this is called the principle of bivalence: there are only two values that a proposition can have, true or false. But Python has None, many other programming languages have null or nil, and Zen has mu. Maybe adding another value would help?

If `all` were in Python v1 it would have thrown an exception when called with an empty list. (Said jokingly, or is it?)

Buttons840• 3 years ago

We could have just used: all(L) if L else True

ajross3• 3 years ago

This is the essence of the issue. All the pontification about (sigh) periods of western logic is missing the point.

The object isn't question isn't a statement of philosophical logic[1]. It's a computer program. And, yeah, it's implemented by iterating over the list and returning false if it finds anything false. If it gets to the end, it returns true. And that is all that needs to be said, because it is an algorithm and not a statement about the world. Maybe it's wrong. In which case, file a bug. But the bug isn't about philosophy either, it's about "I want to solve a problem and all() is giving me the wrong answer".

[1] Not to be confused with actual mathematics, of course. Math doesn't have semantic arguments like this because it starts from a stance of defining terms and axioms such that no one gets confused over words. Sigh, again.

cpgxiii• 3 years ago

This and the parent are mistaking the "how" all([]) is True for the why. The code is the "how", but it doesn't just exist. It could just as easily end in

  return len(L) > 0

instead, which would obviously have different behavior. The code is the embodiment of a particular design, the "why", which has a more complex history.

dragonwriter5• 3 years ago

Yes, that's an implementation of all() that produces the current result.

What the article explains is why the thing that produces the current result has the name “all()”.

While both can be answers to different senses of “Why does all() behave the way it does?”, they are fundamentally answers to very different questions that English, being ambiguous in the way natural language tends to be, allows to be expressed in the same words, the implementation explanation is not a clearer answer to the same question answered by the examination of the history of philosophy and predicate logic, and presenting it as if it were is fundamentally misunderstanding the question being answered by the longer piece.

mabbo• 3 years ago

I think a key point is that (correct me if I'm wrong here) in predicate logic you can rewrite

   ∀x Fx

   Not ∃x (not Fx)

Ie: "for all x, f(x)" implies the opposite of "there exists an x where not F(x)".

People seem to have less of a problem with

   Not ∃x (not Fx)

when the universe is x is empty.

I usually explain it to junior developers by telling them to imagine it's a for loop over a list that returns true/false if it finds a value that doesn't match what's expected, and the opposite of it reaches the end of the list.

dylan604• 3 years ago

In any discussion on languages like this, I feel the Wat discussion is always appropriate: https://www.destroyallsoftware.com/talks/wat

H8crilA2• 3 years ago

This video is over 10 years old. I felt very old all of a sudden. (BTW, it's hilarious, go watch it)

travisjungroth• 3 years ago

Think often when people want/expect this to be false, they’re combining two checks: that there’s an item and all items are true. This covers doing an operation on “ready” items. Instead:

    if items and all(items):

Nevermark8• 3 years ago

The sum of no numbers is 0.

The product of no numbers is 1.

The union of no areas (sets, …) is the empty area.

The intersection of no areas (sets, …) is the universal area.

The commonality here, is what element z can you add or remove from a list which won’t change the result?

We call the element that makes no change to the result, the “identity element”.

For y = sum of {x1,x2, … Xn, z},

We know z must be 0, if it has no impact on y. So the identity element for sum is 0.

So if y = sum of {}, we know we can insert the identity element without changing the result, and we know the sum of {0} is 0. The identity element itself.

So operations applied across lists return that operation’s identity element for an empty list.

—-

Ergo:

the identity element of “all” is “true”.

The identity element of “any” is “false”.

——

More fun:

The identity element for the resistance sum across parallel resistors, is the infinite ohm resister.

The identity element for the vector distance sum of a child making a sequence of jumps is the in-place jump.

—-

Getting meta with, oh hell, monads:

The identity element for C, the concatenation operator over lists, is the empty list {}.

Since all lists are concatenations of lists (down to empty & unitary lists), we can view any operation Q over lists also as an operation over the concatenation of lists.

So any Q acts like a monad over list concatenation operations.

If Q = sum, then it is the monad that transforms concatenations of lists of numbers into the sum of those numbers.

If Q = all, then it is the monad that transforms concatenations of lists of truth values to the conjunction of the truth values in those lists.

With that view in place, we can see another reason why the identity of any operation Q is Q on an empty list Q{}

Because as a monad, Q applies over C, the concatenation of lists. The identity of C is {}, so the identity of Q must be Q{}.

Voila!

So we really shouldn’t define sum{} as 0, but define 0 as sum{}.

“0” is just a symbol. Sum{} is what it is.

0 is the sum of nothing.

So “True” IS the conjunction of nothing. It’s meaning IS all{}. It is the truth of “no requirements”.

layer82• 3 years ago

One corollary is that a zero-dimensional array has exactly one element, whereas a 1-dimensional array can have zero elements (can have length zero). It took me a while to wrap my head around this.

Nevermark8• 3 years ago

Yes! Dimensions are multipliers on each other.

The cross points, over multiple points on segments in different dimensions is a product.

And the product across an empty list is 1.

The number of ways you can roll a dice “no” times is also 1.

Cross combinations of all kinds are products.

rain12• 3 years ago

I don't understand this. Please can you point me to information about it?

evertedsphere• 3 years ago

monoid, not monad

---

a monoid is a set A with an associative binary operator @ on it: that is, for any a, b, c

a @ (b @ c) = (a @ b) @ c

and it also has an "identity" element I, that is, for any a:

a @ I = I @ a = a

common monoids: integers under addition (i.e. @ is addition, the identity is 0), nonzero real numbers under multiplication, lists under concatenation, booleans under AND (identity is True), booleans under OR (what's the identity?), ...

now, when you have a mathematical structure, you often want to study functions between two of them. so you might ask what a reasonable notion of functions between monoids is

one nice way is if, given two monoids, M with operation @ and unit I, and N with operation ^ and unit J, we had a function f for which:

f(I) = J

f(a @ b) = f(a) ^ f(b)

this is loosely described as the function "respecting the structure" of the monoids, and such functions are called monoid homomorphisms or just homomorphisms if the context is clear

with that background, we see that `all` should really be be a homomorphism from the monoid of lists (under concatenation, with the empty list as the identity element) to the monoid of booleans under AND (with True as the identity)

this means that

all(concat(list1, list2)) = and(all(list1), all(list2))

or, in python,

all(a + b) = all(a) and all(b)

and, of course, all([]) = True!

the value here is that now you can reason about the all() of two lists by thinking about the all() of sublists, and the conditions required for a homomorphism guarantee that the empty list is not an edge case:

all([T, F]) = all([]) and all([T, F]) = all([T]) and all([F]) = ...

and that it doesn't matter how you cut up a list into sublists and what order you apply the concatenations in to reconstruct it

Nevermark8• 3 years ago

I was referring to monad, as used in programming, as a transform that can be applied to the elements of a structure.

For instance, a transform that wraps each joining operator, in an expression tree, with a new operator that applies the original operator if all its inputs are defined, but returns a null if any input is null.

The expression tree structure hasn’t changed, but it now consistently (anvoiding error) responds to null values by propagating them.

In my example, a monad converts the list combining operation of concatenation into other list combining operations.

The result was that the identity of concatenation (the empty list) formed the basis for the new list operator’s identity.

—

Both concepts are indeed relevant.

A “monoid-to-aggregator” monad could convert 2-element operations into recursively applied list operations (which also return the single element for unitary lists, and the identity element for empty lists).

Then a structure of monoids processing pairs of values could be transformed into a structure that processes lists.

slaymaker1907• 3 years ago

You could also argue that any({}) is really not defined because first order logic generally excludes empty sets. The reason for said exclusion is because weird stuff starts to happen when you allow an empty domain when talking about if a formula is true in all domains. For example, "exists x, P(x) or !P(x)" is true for every domain unless you allow an empty domain since "exists x ..." is always false. The same is true of all({}) because you have an equivalent weirdness in the form of "!(forall x, P(x) and !P(x))". These seem innocuous, but there are many rules of inference that are excluded once you allow the empty domain.

schoen• 3 years ago

Maybe I'm too used to Coq's higher-order theory now, but I think it's not really that bad to say that we have to be careful about whether statements have existential import.

https://en.wikipedia.org/wiki/Syllogism#Existential_import

Nevermark8• 3 years ago

If we are defining ANY as an n-element LIST operator, in a programming language, which recursively applies the 2-operand AND taking literal Boolean values, there are no ambiguities.

Note that this is inherently a constructible relation, which avoids many pratfalls of more general mathematics.

But if ANY & ALL are being defined as general mathematical relations over all EXISTING members of a class (whose members’ construction, consistency or completeness, may be unknown or even unattainable), then there are other issues.

feoren6• 3 years ago

To be pedantic:

TRUE is the identity element of "and", not "all". "All" is not a binary operator, it is the (unary) aggregation of "and". That is, S.all() == S.aggregate((prev, next) => prev && next, TRUE).

FALSE is the identity element of "or". "any"/"some" is the aggregation of "or". S.any() == S.aggregate((prev, next) => prev || next, FALSE).

0 is the identity element of addition, and "sum" is the aggregation of addition. S.sum() == S.aggregate((prev, next) => prev + next, 0).

1 is the identity element of multiplication, with "product" the aggregation.

Given a monoid M<T> { combine(a: T, b: T) => T, identity: T }, you can define an aggregation operation the same way:

    S.aggregate((prev, next) => M.combine(prev, next), M.identity)

Nevermark8• 3 years ago

TRUE can be the identity element both for the conjunction of 2 Boolean values, and of an operator that extends 2-value Boolean operations to lists of N-elements.

Being an identity is a property. A given mathematical object can be an identity for more than one relation.

It can also be the identity element for general logical propositions or relations.

The reason being, the former is just a special case of the Boolean relations of AND and ALL.

So TRUE can consistently be the identity for many classes of logical operations of varying generality or complexity.

The raw identity relation and concept of identity element form the “tops” of ladders, whose specializations can hold over large classes of relations.

black_knight• 3 years ago

To be even more pedantic! Unit elements are not limited to binary operators. In fact, in a monoid (or group) there is naturally an n-ary operation for each n. Or if you want a single operation from lists of elements to a single element. It is just that we usually present it using a unit and a binary operation + associativity. But one can split that cake in other ways. Thus, in some sense any and all are even more natural or "objective" (as Lawvere would put it) than and and or.

klysm• 3 years ago

The identity element for the resistance sum across parallel resistors, is the infinite ohm resister.

I really like this example, because it has an intuitive physical analog and is more tangible than than the example I typically reach for: lists.

bjourne• 3 years ago

Continuing the same line or reasoning, for integers, max([]) should be -inf and min([]) should be +inf. For positive numbers max([]) should be 0 and min([]) should be +inf. But that's not how these operations are defined in most languages.

edflsafoiewq2• 3 years ago

It's certainly how they're defined in math. In fact all is just min and any is just max over the poset {True, False} with True > False.

I think the reason we don't usually use those definitions is we like to maintain the fiction we're working with actual integers or reals, which don't have a min/max.

xigoi• 3 years ago

min and max are in fact defined this way in JavaScript.

billpg• 3 years ago

I posted in a political thread once...

"Re-joining the EU would give the UK all the benefits of EU membership as well as all the benefits of Brexit too."

gizajob3• 3 years ago

True

gizajob3• 3 years ago

The present king of France is bald.

ptx3• 3 years ago

Does that work, though? If you're talking about a set of kings, then the set can be empty. But "the king" – isn't that more like Kotlin's single() method, which throws an exception if the number of elements is not 1?

gizajob3• 3 years ago

It's a Bertrand Russel joke, and an issue that caused him to want to fix and rebuild formal logic from top to bottom, to differentiate statements like that which aren't really part of reality from functionally identical statements that are part of reality.

rickboyce• 3 years ago

I think the analysis is really interesting, but I suspect it’s quite possible that this behaviour is just a result of optimising the implementation than GVR taking sides in a 2,500 year old philosophical debate.

Both implementations of all() and any() short-circuit by returning as soon as a fasly element in all or a truthy element in any is iterated over.

The origin of these two functions seems to be this post: https://www.artima.com/forums/flat.jsp?forum=106&thread=9819...

Guido makes no comment on empty iterables, but does comment on the final implementation needing to be efficient. It’s possible this behaviour is just the engineering trade off made for a slightly more efficient implementation.

The initial commit of these two functions - https://github.com/python/cpython/commit/96229b191814556622b... - is exactly as Guido’s suggestion, but does include a test case for empty iterables for both functions so we know it wasn’t overlooked.

justin_oaks• 3 years ago

Regardless of whether you thing the return value should be True or False, this behavior violates the Principle of Least Astonishment [0] for a significant number of people.

Such violations in software inevitably lead to bugs that could have been avoided. The real question in my mind isn't what the return value should be. The question is "How can this problem be wholly avoided?"

Some have suggested requiring a default return value when the iterator argument is empty. Others have suggested throwing an error. Perhaps others will suggest the all() function shouldn't exist, although that may be throwing the baby out with the bathwater.

[0] https://en.wikipedia.org/wiki/Principle_of_least_astonishmen...

H8crilA2• 3 years ago

What's an example realistic problem/piece of code that could be buggy because of this definition of all()?

kstrauser4• 3 years ago

I disagree.

  lst = [True, True]; all(lst) is True

is True, and

  lst = [True]; all(lst) is True

is True, I'd be very surprised by

  lst = []; all(lst) is False

Basically, all(lst) is the same as `not any(not item for item in lst)`. If we inverted the value of `all([])`, I'd argue that we'd also have to invert the value of `any([])`, which today evaluates as False. `any([]) is True` would be beyond bizarre to me.

rain12• 3 years ago

The people that are astonished by this just need to learn why.

It's not the function that is wrong, it's those people.

gouggoug• 3 years ago

I'm a bit confused by this:

“All stonemen are made of stone” is true by definition, but “no men are made of stone” is also true and seems to contradict it.

I don't see how “no men are made of stone” contradicts “All stonemen are made of stone”.

"stonemen" are not the same as "men".

English isn't my first language so maybe I don't know what a stoneman is (and google failed me), but I assumed it is a statue?

assbuttbuttass• 3 years ago

I'm guessing, a stoneman means a man made out of stone

Smaug1235• 3 years ago

The originator of that quote was writing in the 12th century. The quote is cited without a source at https://en.wikipedia.org/wiki/Square_of_opposition , where the phrase is "Omnis homo qui lapis est" ("every man who is a stone"). I haven't dug any further than that. But the phrase literally is intended to indicate a contradiction.

Jtsummers2• 3 years ago

A stoneman would be a man made of stone, not a stone shaped like a man.

It comes down to a philosophy of logic issue. A universal quantifier ("for all x P(x)") is ambiguous when there are no x's. You can take it as false, true, or indeterminant, your system of logic will determine which interpretation should be used.

In modern predicate logic, that statement is true if there are no x's. In syllogistic logic it's considered false because there's a second presumption which must be satisfied: That there are any x's to talk about.

ptx3• 3 years ago

Shouldn't this question fail at the parsing stage then, before it has even been asked?

  Q: All stonemen are ...

  A: ERROR: Undefined operation. Stonemen do not exist.

Waterluvian• 3 years ago

I feel like I’d just make a poll and pick the least surprising option if there’s a clear winner.

But maybe that’s why I’m not a language developer.

shadowgovt2• 3 years ago

FTA:

But it is interesting how even extremely practical twenty-first century programming can get drawn into millennia old philosophical controversies, intentionally or not.

This turns out to happen a lot. I can't find the source right now, but there was a good essay I read ages ago about how questions that are abstract and hand-waveable in day-to-day life become cornerstones of architecture rapidly in computer science and software engineering. The cow in the field epistemological puzzle [http://www.philosophical-investigations.org/2021/09/the-cow-...] maps directly to the nature of proving code is "correct" by testing (and any practicing coder has a story of false-positive or false-negative tests, as well as times they identified one of those by a "gut check" telling them "That result... doesn't feel right; I should investigate further"). Similarly, the philosophical question of "sameness" or "equality" ends up concretized over and over again in language design; there's a reason languages end up with so many ways to say 'equals', and it's because the underlying question of what it means for two things to be the same thing is legitimately philosophically complicated!

earthboundkid6• 3 years ago

Here’s a real Gettier question from my actual life:

In college, my future ex-wife rented a video from the video store called “Kama Sutra” on my card and returned it late. The late fee was sent to my parents’ house. My dad discreetly told me later that it was not a problem that we got a late fee, which means he read the letter and thinks we had watched a porno together and was trying to let me know and be cool about it.

However, https://en.wikipedia.org/wiki/Kama_Sutra:_A_Tale_of_Love is a “historical erotic romance film” and not a porno. But my ex-wife and I did in fact see a different porno together.

So then, does my dad know that we saw a porno together?

feoren6• 3 years ago

Humans have trouble with this because our brains cannot let go of the context surrounding a question. For example, a logician may find it funny to walk up to a police officer and say "all of the hookers in my trunk are dead." That is technically true, even though there are no bodies in his trunk. But the brain of the police officer is awash with why someone would be talking about dead hookers at all. Surely something is going on! I would not expect that logician to have a great day.

So we read things about bags with no marbles and bearded kings of France and pink goblins and we think someone is taking the piss out of us, because we can't let go of the context behind those statements. Why are we talking about goblins at all?

All models are wrong. Some models are useful. If you're getting hung up on how it just doesn't make sense that "A -> B" is always true when A is false (which is really the same issue), you have to realize that it's not meant to be intuitive, it's meant to be useful. And the theory of predicate logic where ALL([]) == TRUE is much more useful than the one where it's FALSE or even NULL. It's more useful because TRUE is the identity element of the monoid AND and ALL is the unary set-aggregation of AND. There really cannot be any other choice if you want your theory to fit in with the rest of mathematics and logic, which a useful theory must. It's internally consistent, useful, and really does make deep sense if you are able to let go of context-laden real-world examples.

You should not rely on English sentences making sense to be a good metric of whether a model is useful or not. Consider:

    Dogs must be carried on escalators.

You don't have a dog. Are you allowed on the escalator? Of course you are. This is, in fact, a perfect example of why Your_Dogs.All(is_carried) must be TRUE if Your_Dogs is empty.

    Hard hats must be worn in work areas.

You don't have a hard hat. Are you allowed in the work area? No! How can you tell the difference between these two situations? Only from context. Yet you can see how easy it would be to form the 2nd sentence as an (erroneous) example of "Enforce(HardHats.All(are_worn))", but it's not that. It's more like "Enforce(People.Where(in_work_areas).All(have_hard_hat_on))" -- if there is someone in a work area, then they must have a hard hat on. But if there's nobody in the work area, no rule is being broken! Again we actually see ANY([]) having to be true here.

When you come up with weird-sounding examples where you're sure All([]) must be False, you're just poisoning your intuition with unhelpful context.

msie2• 3 years ago

I'm studying this comment many times. I do have a hang up with A->B being true when A is false.

Nevermark8• 3 years ago

A->B, given A is False, simplifies to:

False->A

Since in this implication, we are starting from a false assumption, we have already left the guardrails of consistency. So we can say whatever we want.

False -> A

False -> not A, as well!

The simplest way to look at it is, having a false assumption is the same thing as saying:

Assume contradictions, then …

Or,

Assume (False = True), then …

Given a false assumption, anything can be implied.

Because if False equals True, then whether A is True or False, it is also the other.

—-

To take the antipode of feoren’s prosaic warnings against colorful context, let’s pile on context like it’s cake!

If we start in a false world, if the physics we live in are already a contradiction, then anything can happen!

Several impossible things before breakfast! Alice and wonderland!

You can have your cake (C) and eat it (not C) too!

michaelteter2• 3 years ago

The problem isn't with all([]) -> True, the problem is the if [] -> False.

[] exists. It happens to be empty, but it is neither a False nor a None. Therefore it should be a True if applying truthiness to it. IMO, any expression which does not result in an actual False or None should be judged as True.

- edit -

On second thought, all([]) -> True is also a poor choice, same in Ruby. The idea of judging an empty collection as having all items being any value is flawed, since there are no items to measure. It is on par with 1 / 0.

This is fun: in both Ruby and Python...

[].all? -> true

all([]) -> True

[].any? -> false

any([]) -> False

So both languages agree that all elements of any empty collection are true, but if you ask them if any of the elements are true, they deny it. So they are all true while also not having any true elements.

x3n0ph3n3• 3 years ago

That's exactly how Ruby behaves.

michaelteter2• 3 years ago

Ruby and Python agree on the all/any functions, but they disagree on the if. And in the "if", I think the Ruby result is better.

kstrauser4• 3 years ago

I disagree. An empty string is False. Any empty set is False. An empty dict is False. Basically, in Python emptiness implies falseness. This has practical benefits:

  users = database.fetch_users()
  if not users:
      print("Didn't find anyone.")

and

  name = input()
  if not name:
      print("You didn't enter a name.")

Of course you could work around those like `if len(users) == 0` or `if not len(users)` or `if name != ""`, but each of those is uglier.

`if not users` translates very nicely to English: "if there are not any users...". I'm glad Python defined `bool(list)` that way.

robot_no_4212• 3 years ago

I'm a Python dev who uses this feature frequently. But the more I use Python (and the more I use Rust in my spare time), the more I realize that I use it only because it's what Python expects me to do. If it was up to me I'd much rather use

  if my_container.empty():
      # do stuff

than

  if not my_container:
      # do stuff

The second implementation behaves the same if either my_container is None or if my_container is empty (or if my_container is 0 or ""...), whereas the first implementation allows me to handle those cases differently. The first implementation is also more explicit and easier to understand on a first read.

It's also easier to debug. Is users supposed to be None in your example? Possibly, but your code doesn't give me any hints. Is my_container supposed to be None in my example? Probably not based on the way I explicitly used the .empty() method.

Delk• 3 years ago

The idea of judging an empty collection as having all items being any value is flawed, since there are no items to measure. It is on par with 1 / 0.

Not really. Those Python functions follow definitions from set theory and predicate logic, and in predicate logic e.g. "for all x, P(x)" is defined as being true if there are no x.

The reason for it being defined that way in mathematics is that it actually leads to consistent rules and definitions without the need to define lots of special cases, even if some of those definitions aren't how most people would use some of the same words in everyday language.

Similarly, the reason division by zero is considered undefined instead of e.g. equaling infinity is that if it were not considering undefined, that would lead to inconsistency. If we had 1 / 0 = a, with any valid result a, that would mean a * 0 would need to equal 1.

Programming languages could of course define their APIs to follow some other (hopefully internally consistent) logic, and I guess you could consider mathematical definitions based on predicate logic or set theory as being a somewhat arbitrary choice. But I disagree that the definition used in Python is on par with division by zero.

mrkeen2• 3 years ago

I like `all = foldr and True` as others have pointed out.

But I think I have a more convincing example of why it can't be the other way around:

    all (>5) [6,7,8]
    all (>5) ([6,7,8] ++ [])
    (all (>5) [6,7,8]) && (all (>5) [])
    (True              && False)
    False

waffletower• 3 years ago

I miss using the Midje testing library for Clojure, as it has the 'truthy' and 'falsey' functions. It reduced these variously bivalent and trivalent conditions into binary in a way that would do Stephen Colbert proud (https://web.archive.org/web/20150121223555/http://www.merria...) Of course you or I can add such to what ever language we are using that supports actual functions -- or smash some abstraction of truthiness into those that don't.

ptx3• 3 years ago

in the new logic, you can’t soundly argue that “all dogs are mammals; all mammals have fur; therefore, all dogs have fur” because one person shaving their dog suddenly makes “all mammals have fur” untrue.

Isn't this just a problem with an unclear definition of "having fur"? Is the article saying that the old logic would hand-wave this problem away because it's about "universals and essences"?

earthboundkid6• 3 years ago

Yes. “All dogs have fur” is untrue. “Dogs have fur” is true. The former is modern; the latter is classical.

devmunchies• 3 years ago

I actually used this in my F# code yesterday. The forall function does the same and it was exactly what I needed.

https://fsharp.github.io/fsharp-core-docs/reference/fsharp-c...

adameasterling• 3 years ago

I had to deal with this problem in our product, which has a visual programming language. I opted to throw an exception if, for whatever reason, "all()" receives an empty list! I had forgotten I'd done that. There's no explanation for it in the code.

As I sit here justifying my own reasoning, though, it sort of makes sense. For ordinary people (for whom this product is supposed to be for), I figure if they put in nothing, that was probably just a mistake.

cheald• 3 years ago

It helps to think in terms of `any` first:

  any([], predicate) => false

This is plainly obvious, because it is illogical to say "the predicate is true for at least one member of the empty set".

If we can agree on that, then all([], predicate) must be true, because the complement of all(list, predicate) is any(list, predicate')

The naive assumption is that the complement of all(list, p) is all(list, p'), but this is demonstrably false, because in the case of an empty list: all([], e => e) and all([], e => !e) would both return the same value.

    > [[], [true], [false]].map(s => s.every(e => e) == !s.every(e => !e))
    [ false, true, true ]

Instead, its proper complement is any(list, p'), which means that all(list, p) = !any(list, p')

    > [[], [true], [false]].map(s => s.every(e => e) == !s.some(e => !e))
    [ true, true, true ]

So, for all([], p) to be false, any([], p') would have to be true, which makes even less sense than all([], p) => true.

the-alchemist• 3 years ago

Clojure does the same thing:

  > clj                                                                                                                                                           
  Clojure 1.11.1
  user=> (every? true? [])
  true
  user=> (every? false? [])
  true
  user=> (every? true? nil)
  true
  user=>

Also:

  user=> (true? [])
  false

In English, an empty list is `false`, but any predicate on an empty list is `true`.

So I believe the logic is the same as Python.

Logic article on this in Wikipedia: https://en.wikipedia.org/wiki/Vacuous_truth

NoToP• 3 years ago

A man goes into court not sure how he got there or what he's accused of. The judge starts saying the opening formalities. "If and only if every member of the jury is convinced you are guilty then this court will convict you." The man looks around. "Your honor, there are no members of the jury." The judge slams the gavel hard. "Guilty". That's the trivial case.

nwah1• 3 years ago

The codebase of Apache Kafka must be littered with this.

junon• 3 years ago

I remember explaining this rather simply, the same question actually. Look at the implementation.

    def all(it):
      for v in it:
        if not v:
          return False
      return True

If there are no items, it returns True.

    def any(it):
      for v in it:
        if v:
          return True
      return False

If there are no items, it returns False.

There's no need for fancy mathematical or "marbles in a bag" explanations here. Just look at the code.

earthboundkid6• 3 years ago

(2020)

earthboundkid6• 3 years ago

Incidentally I wrote the post. Please don’t AMA. It’s all in the post. No further questions.

nighthawk4542• 3 years ago

claims on empty sets can be vacuously true.

"All elephants in my pocket are made of dark matter". Sure, all _zero_ of them, so it's 'technically correct'.

https://en.wikipedia.org/wiki/Vacuous_truth?useskin=vector

aftbit• 3 years ago

Sorry for the meta comment, but ?useskin=vector is game changing. I thought I had just lost the old readable Wikipedia.

Akronymus2• 3 years ago

Not the gp: I have redirector with a regex url rewriter that gets me the skin on all wiki pages. (it is somewhat complex, due to anchors and such) Writing this comment so that I can find it again later so I can post it here, if yoou want to have it.

nighthawk4542• 3 years ago

There's actually 5 skins! If you sign in you can also set your preferred skin in preferences. Check them out below:

https://en.wikipedia.org/wiki/Wikipedia:Skin?useskin=vector

https://en.wikipedia.org/wiki/Wikipedia:Skin?useskin=vector-...

https://en.wikipedia.org/wiki/Wikipedia:Skin?useskin=monoboo...

https://en.wikipedia.org/wiki/Wikipedia:Skin?useskin=timeles...

https://en.wikipedia.org/wiki/Wikipedia:Skin?useskin=minerva

nobody0• 3 years ago

The empty set is vacuously true for any properties with elements.

pharmakom• 3 years ago

In logic class, these were axiomatically equivalent

    for all x. P(x)

    not (exists x. not P(x))

nurettin• 3 years ago

Because of this http://en.m.wikipedia.org/wiki/Vacuous_truth

kazinator• 3 years ago

If you have some set S and predicate P(x) is true for every x in S, ∀x∈S:P(x), then you can partition the set into pieces S₁ ∪ S₂ ∪ ... u Sₙ. such that ∀x∈S₁:P(x) ∧ ∀x∈S₂:P(x) ∧ ... ∧ ∀x∈Sₙ:P(x).

If the quantified predicate were to be false for an empty set, then the above breaks if any of the partitions are empty. A property can then be true when quantified over a set such that it's not true over subsets, which is inconsistent.

A similar problem occurs with products. We can use Lisp:

  (* 2 3 4) -> 24

We would like to be partition that into partial products. Here, we have a partition of length 1:

  (* (* 2 3) (* 4)) -> 24

So we want (* N) -> N. And empty partitions:

  (* (*) (* 2 3) (*) (* 4))  -> 24

For that to work we need:

  (*) -> 1

kaleidawave• 3 years ago

Case of the “Vacuous truth”

Why does all() return True if the iterable is empty?

Related Stories