Why does IQueryable.All() return true on an empty collection?
.net, linq, logic
Solution
If my driveway is empty, I cannot assert that all cars parked there are red.
Consider the following statements.
`S1`: My driveway is empty.
`S2`: All the cars parked in my driveway are red.
I claim that `S1` implies `S2`. That is, the statement `S1 => S2` is true. I will do this by showing that its negation is false. In this case, the negation of `S1 => S2` is `S1 ^ ~S2`; this is because `S1 => S2` is false only when `S1` is true and `S2` is false. What is the negation of `S2`? It is
`~S2`: There exists a car parked in my driveway that is not red.
What is the truth value of `S1 ^ ~S2`? Let's write it out
`S1 ^ ~S2`: My driveway is empty and there exists a car parked in my driveway that is not red.
The only way that `S1 ^ ~S2` can be true is if both `S1` and `~S2` are true. But `S1` says that my driveway is empty and `S2` says that there exists a car in my driveway. My driveway can not be both empty and contain a car. Thus, it is impossible for `S1` and `~S2` to both be true. Therefore, `S1 ^ ~S2` is false so its negation `S1 => S2` is true.
Therefore, if your driveway is empty you can assert that all cars parked there are red.
So now let's consider an `IEnumerable<T> elements` and a `Predicate<T> p`. Let us suppose that `elements` is empty. We wish to discover the value of
bool b = elements.All(x => p(x));
Let's consider its negation
bool notb = elements.Any(x => !p(x));
For `notb` to be true, there must be at least one `x` in `elements` for which `!p(x)` is true. But `elements` is empty so it is impossible to find an `x` for which `!p(x)` is true. Therefore `notb` can not be true so it must be false. Since `notb` is false, its negation is true. Therefore `b` is true and `elements.All(x => p(x))` must be true if `elements` is empty.
Here's one more way to think of this. The predicate `p` is true if for all `x` in `elements` you can not find any for which it is false. But if there are no items in `elements` then it is impossible to find any for which it is false. Thus, for an empty collection `elements`, `p` is true for all `x` in `elements`
Now, what about `elements.Any(x => p(x))` when `elements` is an empty `IEnumerable<T>` and `p` is a `Predicate<T>` as above? We already know the result will be false because we know its negation is true, but let's reason through it anyway; the intuition is valuable. For `elements.Any(x => p(x))` to be true there must be at least one `x` in `elements` for which `p(x)` is true. But if there aren't any `x` in `elements` it is impossible to find any `x` for which `p(x)` is true. Therefore, `elements.Any(x => p(x))` is false if `elements` is empty.
Finally, here's a related explanation on why `s.StartsWith(String.Empty)` is true when `s` is a non-null instance of `string`:
Problem
So I ran into a situation today where some production code was failing precisely because a method performed exactly as documented in MSDN. Shame on me for not reading the documentation. However, I'm still scratching my head as to why it behaves this way, even if "by design", since this behavior is exactly opposite what I would have expected (and other, known behaviors) and therefore seems to violate the principle of least surprise. The `All()` method allows you to supply a predicate (such as a lambda expression) to test an `IQueryable`, returning a Boolean value that indicates whether all collection members match the test. So far so good. Here's where it gets weird. `All()` also returns `true` if the collection is empty. This seems completely backwards to me, for the following reasons: - If the collection is empty, a test like this is, at best, undefined. If my driveway is empty, I cannot assert that all cars parked there are red. With this behavior, on an empty driveway all cars parked there are red AND blue AND checkerboard - all of these expressions would return true. - For anyone familiar with the SQL notion that NULL != NULL, this is unexpected behavior. - The `Any()` method behaves as expected, and (correctly) returns false because it does not have any members that match the predicate. So my question is, why does `All()` behave this way? What problem does it solve? Does this violate the principle of least surprise? I tagged this question as .NET 3.5, though the behavior also applies to .NET 4.0 as well. EDIT Ok, so I grasp the logic aspect to this, as so excellently laid out by Jason and the rest of you. Admittedly, an empty collection is something of an edge case. I guess my question is rooted in the struggle that, just because something is logical doesn't mean it necessarily makes sense if you're not in the correct frame of mind.