Why does Stream.allMatch() return true for an empty stream?

Question

My colleague and I had a bug that was due to our assumption that an empty stream calling allMatch() would return false.

if (myItems.allMatch(i -> i.isValid()) { 
    //do something
}

Of course, it is kind of our fault for assuming and not reading documentation. But what I don't understand is why the default allMatch() behavior for an empty stream returns true. What was the reasoning for this? Like the anyMatch() (which contrarily returns false), this operation is used in an imperative way that departs the monad and probably used in an if statement. Considering those facts, is there any reason why having allMatch() default to true on an empty stream be desirable for majority of uses?

Merocrine

That is a bit weird. We would expect that if allMatch returns true then so should anyMatch. Additionally, for the empty case, allMatch(...) == noneMatch(...) which is also weird. – Vulgarian

Wikipedia says it is the convention: en.wikipedia.org/wiki/Universal_quantification#The_empty_set – Doordie

Just a quick aside about syntax: instead of writing your predicate as i -> i.isValid(), you can write Foo::isValid (where Foo is whatever class you're streaming, of course) – Noetic

"This operation is used in an imperative way that departs the monad" - I doubt this factors into any decisions. – Rumania

Answer 1

This is known as vacuous truth. All members of an empty collection satisfy your condition; after all, can you point to one that doesn't?

Similarly, anyMatch returns false, because you can't find an element of your collection that does match the condition. This is confusing to a lot of people, but it turns out to be the most useful and consistent way to define "any" and "all" for empty sets.

Interact

Geez, I hate boolean logic. I think I get the idea of what you are saying. The absence of negatives is a positive, but the absence of positives is not negative. – Merocrine

@ThomasN. In the same way the value the product of an empty set of numbers is 1 while the sum of an empty set of numbers is 0. They are the neutral elements for multiplication/addition. In the case of booleans you have that True and x = x and False or x = x hence if you generalize and and or to sequences (that's what all and any are) you end up with True and False for the empty case, i.e. they respective neutral elements. – Undercoating

@ThomasN. anyMatch tests for the absence of positives, allMatch tests for the absence of negatives. – Rumania

Note that this way you can do nice things like De Morgan's law: stream.allMatch(predicate) is the same as !stream.anyMatch(predicate.negate()). Similarly, !stream.allMatch(predicate.negate()) is the same as stream.anyMatch(predicate). – Gobo

"can you point to one that doesn't?"... I can say the same thing for the opposite, "can you point to one that does?" I accept the concept of vacuous truth may be useful sometimes, but that argument is based on a fallacy (Affirming the consequent) – Austral

@PatrickBard: You can say "can you point to one that does", and that is completely valid, but what it means is that all members of the collection fail to satisfy the condition. All members of the collection satisfy the condition, and all members of the collection fail to satisfy the condition. These are different statements from "it is false that all members of the collection satisfy the condition". Like I said, it's confusing. – Interact

As for affirming the consequent, if you have a specific definition of "all" in mind for which "all satisfy condition -> nonexistence of element that fails to satisfy condition" is a one-way implication, then the post may seem like affirming the consequent. From a formal logic point of view, it's a bidirectional implication due to the definitions of "all" and "any" and De Morgan's laws for quantifiers. – Interact

Ah, the statement "All elephants in the room are pink" is almost always true. – Chaeta

Works exactly as expected. Otherwise many business logic cases will fail. I came here just to make sure that it works as I thought it should be. – Richardo

Can you point element which satisfy? it turns out to cases when for empty collection both methods working wrong. – Kyoko

Answer 2

Here's another way to think about this:

allMatch() is to && what sum() is to +

Consider the following logical statements:

IntStream.of(1, 2).sum() + 3 == IntStream.of(1, 2, 3).sum()
IntStream.of(1).sum() + 2 == IntStream.of(1, 2).sum()

This makes sense because sum() is just a generalization of +. However, what happens when you remove one more element?

IntStream.of().sum() + 1 == IntStream.of(1).sum()

We can see that it makes sense to define IntStream.of().sum(), or the sum of an empty sequence of numbers, in a particular way. This gives us the "identity element" of summation, or the value that, when added to something, has no effect (0).

We can apply the same logic to Boolean algebra.

Stream.of(true, true).allMatch(it -> it) == Stream.of(true).allMatch(it -> it) && true

More generically:

stream.concat(Stream.of(thing)).allMatch(it -> it) == stream.allMatch(it -> it) && thing

If stream = Stream.of() then this rule still needs to apply. We can use the "identity element" of && to solve this. true && thing == thing, so Stream.of().allMatch(it -> it) == true.

Gobo

Answer 3

When I call list.allMatch (or its analogs in other languages), I want to detect if any items in list fail to match the predicate. If there are no items, none might fail to match. My following logic would pick items and expect them to have matched the predicate. For an empty list, I'll pick no items and the logic will still be sound.

What if allMatch returned false for an empty list?

My straightforward logic would fail:

 if (!myList.allMatch(predicate)) {
   throw new InvalidDataException("Some of the items failed to match!");
 }
 for (Item item : myList) { ... }

I'll need to remember to replace the check with !myList.empty() && !myList.allMatch().

In short, allMatch returning true for an empty list is not only logically sound, it also lies on the happy path of execution, requiring fewer checks.

Frasquito

you probably meant if (!allMatch) – Tressietressure

Answer 4

It looks like the base of it is mathematical induction. For computer science an application of this could be a base case of a recursive algorithm.

If the stream is empty, the quantification is said to be vacuously satisfied and is always true. Oracle Docs: Stream operations and pipelines

The key here is that it is "vacuously satisfied" which, by nature, is somewhat misleading. Wikipedia has a decent discussion about it.

In pure mathematics, vacuously true statements are not generally of interest by themselves, but they frequently arise as the base case of proofs by mathematical induction. Wikipedia: Vacuous Truth

Zincography

Answer 5

While this question has already been answered correctly multiple times, I want to bring in a more mathematical approach.

For that I want to consider the stream as a Set (in the mathematical sense). Then

emptyStream.allMatch(x-> p(x))

corresponds to while

emtpyStream.anyMatch(x -> p(x))

corresponds to .

That the second part is false is quite obvious since there are no elements in the empty set. The first one is a bit more tricky. You can either accept it to be true by definition or look into the other answers for some of the reasons why it should be that way.

An example to illustrate this difference are propositions like "All humans living on Mars have 3 legs" (true) and "There is a human living on Mars with 3 legs" (false)

Fugate

Answer 6

Workaround:

!myItems.isEmpty() && myItems.allMatch(i -> i.isValid())

Otte

Answer 7

In my opinion the default behavior is not quite correct.

It makes sense for complex logical operations, I agree. But for very simple conditions it is just wrong or misleading.

A classic example: a check that all orders of a customer have a total of more than N dollars means that

a) there are some orders in the first place

b) all of them have a total of more than N dollars

Assuming that customers with no orders should be included in the result set by this check seems not correct - just imagine the silly case where 90% of our user base have not made any orders just yet.

Again, an absurd examples like "All humans living on Mars have 3 legs" or "All elephants in the room are pink" are not true, they are undefined (like 0 / 0 or Infinity / Infinity). In JavaScript there is even a special value for undefined values, while in Java we could probably return null or throw a special exception in this case.

But I agree that some cases can really benefit from the currently implemented behavior (fewer checks needed and no exceptions thrown).

Garibaldi