1. 32
  1. 27

    Rather than go off the deep end into predicate logic or identities or similar concepts, I’ve traditionally explained it as follows. Imagine you have two lists, list1 and list2, but you don’t know what’s in them. Should all(list1) and all(list2) return the same result as all(list1 + list2)?

    Most people intuitively say yes, those should always give the same result because they see that checking the combination of the two lists should be the same as checking each one individually and combining the results. But that’s only possible if all([]) is True.

    1. 2

      Okay yeah this is the best explanation by far

    2. 15

      A related concept: identity elements, such as these for integers;

      • the multiplicative identity, 1 (because x * 1 = x), and
      • the additive identity, 0 (because x + 0 = x).

      For booleans, there’s

      • the “and” identity, True (because x and True = x), and
      • the “or” identity, False (because x or False = x).

      We know all([x, y, z]) is equivalent¹ to x and y and z, i.e. it’s the “and” operator applied to a list of elements. When there’s no elements, you get the identity for the “and” operation, namely True. You could imagine the invocation was equivalent to all([True, x, y, z]), so that when there’s no elements in the argument list you get all([True]) = True.

      ¹ There’s so many little details omitted, but let’s ignore those. This isn’t a Python primer.

      Here’s another way you can build an intuition for this. I’ll use Ruby here because I’m more familiar, but the concepts apply anywhere.

      Ruby’s equivalent of fold is called inject. You can pass a block which is applied repeatedly to the elements, starting with the first two elements, and then applying the result to each next element. Here’s an example:

      > [1, 2].inject {|a,b| a+b}
      => 3
      > [1, 2, 3, 4].inject {|a,b| a+b}
      => 10

      Here’s some added printf debugging showing what gets added to what:

      > [1, 2, 3, 4].inject {|a,b| puts "adding #{a} and #{b}"; a+b}
      adding 1 and 2
      adding 3 and 3
      adding 6 and 4
      => 10

      You can also supply a starting value as an argument to inject, in which case it’ll use that and the first element for the first operation:

      > [1, 2, 3, 4].inject(777) {|a,b| puts "adding #{a} and #{b}"; a+b}
      adding 777 and 1
      adding 778 and 2
      adding 780 and 3
      adding 783 and 4
      => 787

      So, what happens if we don’t have any elements in the list?

      > [].inject {|a,b| puts "adding #{a} and #{b}"; a+b}
      => nil

      Nothing happens. You get nil because there’s nothing useful to produce.

      If you supply a starting value, you get that:

      > [].inject(0) {|a,b| puts "adding #{a} and #{b}"; a+b}
      => 0

      Note the binary operation isn’t called here, because there isn’t two values.

      So here we see that supplying 0 gives us 0, which makes sense when you consider that the binary operation is adding two numbers. We can also see that keeping 0 as the starting value works for this case:

      > [1, 2, 3, 4].inject(0) {|a,b| puts "adding #{a} and #{b}"; a+b}
      adding 0 and 1
      adding 1 and 2
      adding 3 and 3
      adding 6 and 4
      => 10

      But, say, for multiplication, it doesn’t:

      > [1, 2, 3, 4].inject(0) {|a,b| puts "multiplying #{a} and #{b}"; a*b}
      multiplying 0 and 1
      multiplying 0 and 2
      multiplying 0 and 3
      multiplying 0 and 4
      => 0

      We need 1 for that—because it’s the multiplicative identity:

      > [1, 2, 3, 4].inject(1) {|a,b| puts "multiplying #{a} and #{b}"; a*b}
      multiplying 1 and 1
      multiplying 1 and 2
      multiplying 2 and 3
      multiplying 6 and 4
      => 24

      So we can see why true is the right identity for a function like Python’s all:

      > [true, true].inject(true) {|a,b| puts "ANDing #{a} and #{b}"; a&&b}
      ANDing true and true
      ANDing true and true
      => true
      > [true, true, false, true].inject(true) {|a,b| puts "ANDing #{a} and #{b}"; a&&b}
      ANDing true and true
      ANDing true and true
      ANDing true and false
      ANDing false and true
      => false

      And why false is not:

      > [true, true].inject(false) {|a,b| puts "ANDing #{a} and #{b}"; a&&b}
      ANDing false and true
      ANDing false and true
      => false

      Here’s a Ruby equivalent of all([]), showing it demonstrating the same identity:

      > [].all?
      => true

      And the any([]) equivalent (because false is the “or” identity):

      > [].any?
      => false
      1. 6

        One major reason this is “intuitive” (for certain definitions of intuitive) is that the statement ¬(∀x∈P: F(x)) (not all x are F) is equivalent to the statement ∃x∈P: ¬F(x) (there exists an x that is not F). And “exists” is tautologically false for empty sets, mean “all” must be true for empty sets to preserve the natural statement.

        1. 3

          This reminds me of having to explain to a novice programmer why you can’t write if (a & b == 0) to mean “if both a and b are zero”. It’s hard for me to think that it should return anything else. It’s the same reason why we use the conventions that the sum of an empty set is zero and the product of an empty set is one. It is the identity with respect to the operation we’re performing (all() basically performs a logical and operation, which has true as its identity).

          1. 2

            In a strongly typed language, there’s no reason you couldn’t have a&b == 0 mean ‘a and b are both 0’ (assuming & is the logical and operator and a and b are integers); the alternative is a type error. Indeed that exact usage is supported in raku.

            1. 1

              Now you mention this, in C you could write (a | b) == 0 to mean the same thing, which is quite funny since it’s the same thing but with or instead of and.

              Random remark: a good addition to some programming languages may be an ‘implies’ operator ->. Then a -> b would be equivalent to !a || (a && b), just like in math. This can be used to encode a condition that says “when a is true, then b should also be true”. This would make for more understandable code, in my opinion.

              1. 2

                This is again something you can do pretty easily in raku:

                sub infix:<implies>($premise, $conclusion) {
                        (!$premise) || ($premise && $conclusion)
                say True  implies True;
                say True  implies False;
                say False implies True;
                say False implies False;

                Prints out:


                As you would expect.

          2. 3

            Aside from aligning with predicate logic, I have found that this behaviour ends up being what I want in practice for most problems I encounter. Most of the time if I’m checking that all elements of a list are true, or that all of them match some predicate, then what I’m doing can be thought of as a validation problem, and an empty set of validations should always pass.

            1. 2

              I’ve always thought of it like this: do all the things in collection satisfy the predicate bool(thing)? Well, when collection is empty, then Yes, of course… all the things in collection that we can test with bool(thing) do indeed satisfy the predicate… we just never have to actually run bool(thing). The notion of all doesn’t imply that there must be at least one thing that satisfies the predicate, it only implies that at most 0 things can not satisfy the predicate.

              Conversely, any does imply that at least one thing in collection must satisfy the predicate for any(collection) to be True, hence why it’s False when collection is empty.

              Which leads us to why any(collection) and all(collection) can only be True in the case that there’s at least one thing and all things satisfy the predicate.