117

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?

4
  • 4
    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.
    – Radiodef
    May 13, 2015 at 19:08
  • 7
    Wikipedia says it is the convention: en.wikipedia.org/wiki/Universal_quantification#The_empty_set May 13, 2015 at 19:10
  • 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)
    – MattPutnam
    May 13, 2015 at 20:39
  • 2
    "This operation is used in an imperative way that departs the monad" - I doubt this factors into any decisions.
    – user253751
    May 14, 2015 at 0:18

6 Answers 6

165

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.

10
  • 6
    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.
    – tmn
    May 13, 2015 at 19:15
  • 14
    @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.
    – Bakuriu
    May 13, 2015 at 21:03
  • 10
    @ThomasN. anyMatch tests for the absence of positives, allMatch tests for the absence of negatives.
    – user253751
    May 14, 2015 at 0:19
  • 3
    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).
    – Hans
    Jun 19, 2017 at 18:50
  • 1
    @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. Oct 16, 2018 at 16:13
13

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.

7

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.

1
  • you probably meant if (!allMatch)
    – assylias
    May 13, 2015 at 20:02
3

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

1

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 enter image description here while

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

corresponds to enter image description here.

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)

0

Workaround not beautiful in some cases.

example:to verify if all requests are sent(but request list of some type can be empty)

public boolean isAllRequestsSent(String type){

        //empty request List
        var count = requestsList.stream().filter(Request::type).count();
        
        if(count <= 0) {
            return false;
        }
    
        return requestsList.stream().filter(Request::type).allMatch(RequestData::isSent);
        }

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.