Why does Iterator::all return true for an empty iterator?

Question

The following code

fn main() {
    {
        let a: Vec<i32> = vec![1, 2, 3, 4];
        print!("{}\n", a.into_iter().all(|x| x > 1));
    }
    {
        let a: Vec<i32> = vec![];
        print!("{}\n", a.into_iter().all(|x| x > 1));
    }
}

gives me the output

false
true

Surprisingly, a.into_iter().all(|x| x > 1) returned true when a is empty.

Looking at the docs for Iterator::all, I see that it is explicitly stated:

An empty iterator returns true.

Why was it chosen to be this way?

Answer 1

This is the typical convention of the all function in pretty much all programming languages, except those that get it wrong. Conversely, any returns false for empty sequences.

The reason is that it is more useful for typical scenarios. If you have a list of requirements and a value must fulfill all of these to pass through a filter. If your list is actually empty, should the value get through? The answer that usually makes the most sense is yes. Therefore, conditions.all(|value| condition.fulfilled(value)) returns true for the empty list.

It is also a natural consequence of the reformulation of the all definition as, "no item is false", and the default if you implement all in the intuitive way:

fn all<F>(&mut self, f: F) -> bool
where
    F: FnMut(Self::Item) -> bool,
{
    for v in self {
        if !f(v) {
            return false;
        }
    }
    return true;
}

There might even be a basis in mathematics for this, but I couldn't find something quickly.

Answer 2

If you are interested in the mathematical basis, here is a short proof:

The statement A => B (A implies B) is logically equivalent to !A | B (not A or B).

The statement S: for each x in X, P(x) is true (where P is a predicate) is a shorthand for for each x: x in X implies P(X) is true.

This statement is hence equivalent to: For each x: P(x) is true or x is not in X

If X is empty, the statement x is not in X is always true so the statement S is true.

Answer 3

It is useful in mathematics for composability:

any(x + y) == any(x) or any(y)

all(x + y) == all(x) and all(y)

These conditions hold for all non-empty x, y. The values for empty x and y are chosen to maintain this property:

all([]) == true

any([]) == false