`iter().all()` that does not return `true` for empty iterators

1

Hi everyone, just pitching an idea here - The current implementation of iter().all() returns true if the iterator is empty. This makes sense against the behaviour of iter().any(), which returns false if the iterator is empty. Here, "any" -> at least one element -> if no elements, false. Along the same lines, "all" -> every single element -> if no elements, ...false? I feel this also makes sense, but we cannot alter the behaviour of iter().all() at this point in such a breaking manner. Would it make sense to introduce another function that does the exact same thing as iter().all() but returns false if the iterator is empty? Maybe it can be called all_non_empty() or something like that.

2

It doesn't. This is called "vacuous truth". If our job is to satisfy a set of conditions, and there are no conditions, then we have done our job. Hence the answer is true.

This is related to the empty product being 1. If you consider true=1, false=0, then all() is the product. iter::empty().all(|x| x) == true corresponds to x.pow(0) == 1.

32 Likes
3

Do you have a use case in mind for this? It's a fairly simple thing to construct if you need it: (you could do so via peekable, or via any and De Morgan's laws, or very explicitly as:

fn all_or_empty<Iter, F>(iter: &mut Iter, mut f: F) -> bool
where
    Iter: Iterator + Sized,
    F: FnMut(Iter::Item) -> bool,
{
    (match iter.next() {
        None => false,
        Some(item) => f(item),
    }) && iter.all(f)
}

In general, though, as @tczajka pointed out, it's rarely algorithmically needed - usually, if you're using all or any, you want all to return true if the iterator is empty, and any to return false if the iterator is empty.

4

Another argument is that by de Morgan,

 forall x: p = not exists x: not p

And when x is the empty set, this identity reduces to

lhs = not rhs = not false = true.

Of course, this also matches the most common real-world use cases: if the user can filter some data such that all enabled filters are ANDed together, then it’s surely the case that if no filters are set, all the data should be displayed.

3 Likes
5
5 Likes
6

Thank you all for the info, my predicate logic was faulty :slight_smile: cheers

2 Likes
7

Because I found it interesting, another way to write this:

fn all_non_empty<Iter: Iterator>(mut iter: Iter, mut f: impl FnMut(Iter::Item) -> bool) -> bool {
    iter.next().map_or(false, &mut f) && iter.all(f)
}

Not that open-coding Option::map_or is a particularly bad thing to do, but it does make the function body a little cleaner, as does taking the iterator by-value (which also accepts by-mut-ref).

4 Likes
8

I keep forgetting about Option::map_or, because it didn't exist when I first learnt Rust. It's one that I use when Clippy reminds me of it, then forget about after a few days.

4 Likes
9

And map_or(false, _) can be replaced with its special case is_some_and(_), which might read better in this case:

iter.next().is_some_and(&mut f) && iter.all(f)
7 Likes
10

The above posts cover why "every single element -> if no elements, ...false?" is considered incorrect in standard boolean logic, but it's also worth at least a little argument that "standard boolean logic" is how we want our programs to behave.

Consider the following:

let numbers = vec![Ok(1), Ok(2), Err("???"), Ok(4)];

if numbers.iter().any(|n| n.is_err()) {
    println!("Invalid number found, skipping expensive_op");
    return;
}
println!("All numbers valid, doing expensive_op");
expensive_op(numbers.iter().map(|n| n.unwrap()));

and

if numbers.iter().all(|n| n.is_ok()) {
    println!("All numbers valid, doing expensive_op");
    return expensive_op(numbers.iter().map(|n| n.unwrap()));
}
println!("Invalid number found, skipping expensive_op");

Today, these are two ways of writing the same thing. But if numbers was an empty vector, and .all() were changed to return false on empty iterators, then the 2nd way of writing this would print "Invalid number found" even though no invalid number was found.

While you do sometimes need special cases for empty sequences, in my experience this sort of code where empty and non-empty sequences "just work" the same way is very typical. I believe .all() returning false on empty iterators (or the equivalent in any other programming language) would lead to far more subtle bugs in practice than the current behavior of producing "vacuous truth" like standard logic does.

3 Likes
11

This example could be rewritten such that one wants expensive_op to run when `numbers is empty, or that you don't, and the printed text could be valid or invalid for empty either way. The reason we want code and libraries to conform to various logics is so the code can be reasoned about. Someone familiar with boolean logic could figure out what any/all do without even looking at the docs, and is less likely to make a mistake with this edge case.

1 Like