CODEWITHSUNDEEP
rust
Malice
Malice

Reputation: 1482

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

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?

Upvotes: 10

Views: 3019

Answers (3)

Test
Test

Reputation: 1720

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

Upvotes: 1

Guillaume Gris
Guillaume Gris

Reputation: 2270

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.

Upvotes: 7

Sebastian Redl
Sebastian Redl

Reputation: 71969

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.

Upvotes: 22

Related Questions