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

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

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

I was going to write unit in my comment, but unit is the wrong word. The word unit applies only to multiplication. In the natural numbers there is only one unit: 1. Some other fields have multiple units. The integers have 1 and -1 and the rationals contain infinitely many units (every element is a unit).

The correct term is an identity.

I was going to comment this, but you got here before me. So, I would just like to ramble about type theory and constructive logic a bit.

According to the Curry-Howard correspondence and the BHK interpretation of logic, there is a syntactic correspondence between types and logical formulas and between terms and proofs.

Here, the unit type corresponds with truth because it is trivially inhabited with a single inhabitant. The product type A * B is interpreted as logical conjunction because you need a proof of A and a proof of B to inhabit it.

The unit type (true) is the identity of the product type (and). Unit * A = A * Unit = A from an isomorphism perspective. From the category theory point of view, a Cartesian monoidal category is a monoidal category where the tensor product is the categorical product and the unit object is the terminal object. It's no coincidence that the terminal object is written as 1.

So, an n-ary sequence of propositions connected by ANDs is like an n-ary tuple type, and an empty sequence of propositions connected by ANDs is like the nullary tuple type, or in other words the trivially inhabited unit type.

You could also look at it like this:

We want this general property to hold:

sum([ sum(x[0:n]), sum(x[n:]) ]) == sum(x)

define sum([]) (n = 0) so that it holds

It works the same for prod, all, and any, and gives a hint as to what the answer should be if there were things like union(sets) (the empty set) or intersection(sets) (the universe, or union of all sets)

That should be:

  prod([2,2]) = 2*2 = 4

Right?

An alternative way of viewing this is: find the recursive definition of that function, and think of its base case. For sum, it is something like sum([Head:Tail]) = Head + sum(Tail), which works only if sum([]) is 0. For prod, we have prod([Head:Tail]) = Head * prod(Tail), which again works only if prod([]) is 1. And for all, we have all([Head:Tail]) = Head && all(Tail), which again works only if all([]) is True.

In mathematics in binary operations this element is called neutral element or idendity element. https://en.wikipedia.org/wiki/Identity_element?wprov=sfla1

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.

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

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.

This was definitely not accidental. Here is the commit that introduces `all` and `any`: https://github.com/python/cpython/commit/96229b19181

It includes a test for the empty case: `self.assertEqual(all([]), True)`. They knew what they were doing.

What do you mean by "Epicycles"? Are you suggesting the code is written like this by random?

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.

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.

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

It really just goes to show how far you can get without knowing the fundamentals these days.

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

Lewis Carroll didn't know this, and treated universally quantified statements over an empty domain as false. Of course that's wrong; but I think it's over-specialising to claim that this is something obvious, or that everyone knows.

(Also, as others have said, if someone learns from this, then that's great! That's a positive impact, whereas saying "you should have known it already" is purely negative, so why bother?)

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.

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.

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.

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

The min() function doesn't know the type. The minimum possible value for a list of strings is "", for example.

To get what you want, use min(lst, default=-math.inf) .

Interesting point. You got me thinking and opened a wormcan in my mind. I guess True and False are in the set of Booleans, but infinities are, very strongly arguably, not in the domain of numbers. But still, but still.

`min` and `max` operate on semigroups, not on monoids. They don't have to have a default value, and any nicely strongly typed language should prevent them from acting on empty lists.

You could invent a monoid instance of `float` for `<` which includes `inf` as an empty element and, if you ignore NaN, it kinda sorta works in isolation. However, adding infinity breaks a lot of other nice properties to the numbering system.

For example, the following identity of `min` is valid in the finite numbers.

``` n < min A ⟺ (∀ a ∈ A) n < a ```

The right part of the equation is always true if `A = ∅`, and according to our new monoid the left part is true if and only if `n ≠ ∞`.

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

The identity element is the term you’re looking for

English.

That's intriguing, but I'm a bit confused and don't really see the connection. Could you expand?

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

Why? All unicorns are blue, aren't they?

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

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

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.

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

Read up on DeMorgan’s law.

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.

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