In clojure, (every? pred coll) returns true if coll is empty, could this be a design flaw?

Question

From the example and the comment on Clojuredoc for function every?

user> (every? true? '())    ;empty is true? 
true

user> (every? false? '())    ;empty is false? 
true

This is indeed weird and possibly illogical, as I would expect false for both above. Could somebody shed some light on rationale behind this?

Answer 1

In mathematics, particularly in the field of predicate logic, it is accepted that every universal predicate about the empty set is true. For example, the following statement is true:

Every integer in the empty set is even.

Similarly, the following statement is also true:

Every integer in the empty set is odd.

Therefore, the following bizarre statement is also true:

Every integer in the empty set is simultaneously even and odd.

Think about it: can you give a counter-example to any of the above?

A more formal explanation would be the following. When you have a universal predicate, which can be formally written as ∀x∈XP(x) (for all x element of X, P(x)), it is equivalent to an implication of the form x∈X ⇒ P(x) (x element of X implies P(x)). Since the left-hand side of this implication is false for the empty set (ie, there are no elements x such that x∈Ø, which is simply the definition of the empty set), the implication is true (ie, false ⇒ whatever evaluates to true; check the truth table here).

This is exactly what you are seeing in the code you've shown: Clojure is evaluating the universal predicate (every? pred) on the empty list '() as true, which is correct and perfectly logical according to predicate logic.

Finally, you can expect to see the exact same behavior on every functional language or functional library, with the synonyms all, forall and maybe others. If you explore the implementation of these functions, you will notice a common pattern: the function will return true unless it finds a counter-example, ie, an element for which the predicate is false; if it doesn't find such an element (which includes not finding any element at all -- the empty set) then it cannot prove the predicate to be false, and returns true. This is done either with loops or folds, depending on the language or framework, but the idea is always the same.

For example, check:

• Google Guava's Iterables.all (and, more specifically, Iterators.all); or
• Functional Java's List.forall; or
• Scala's forall; or
• Haskell's Data/List all; or
• ECMAScript 5's Array.every; or
• Underscore.js's every; or
• F#'s Seq.forall; or
• C#'s Enumerable.All; or
• C++'s all_of; or
• Python's all; or
• Ruby's all?

(they all do exactly the same thing as (every? pred coll) in Clojure; and feel free to edit and add your favorite language or library!).

For more information, be sure to read Wikipedia's articles on Universal Quantification and Vacuous truth.