為什麼函數式語言中all odd [] 得到True?

Clojure:

(every? odd? [])
true


Haskell

all odd []
True


Python

all([])
True


剛發現時覺得非常反人類...做練習排一個bug才發現的.

剛想了想..好像是初始值的緣故..為了避免檢查是否為空,直接初始為True.碰到False再返回False.

為了性能考慮?還是說歷史原因..

私以為這種違反語義的行為有悖函數式貼近思維.站在更高抽象的理念.

StackOverflow上有說這是數學邏輯上的原因:Why Python built in "all" function returns True for empty iterables?

This comes from the mathematical logic.

"everything is true of the elements of the empty set" (Empty set)

但我仍然覺得這有悖語義..

---

List().forall(f)


f 是一個謂詞，為 T =&> Boolean 類型。

一階謂詞邏輯就是 . 由於前件 永遠為假，故該表達式永真。

所以返回真才是不違反語義的，返回假反而是不對的。

如果還是覺得不符合語義的話，考慮兩個列表 A 和 B。

應該有

(A ++ B).forall(f) 恆等於 A.forall(f) B.forall(f)


設 . 有

A.forall(f) 恆等於 A.forall(f) B.forall(f)


則顯然必須有 B.forall(f) == true 才能滿足條件。

---

我覺得其他答案里提到的 Vacuous truth 已經很簡單地回答這個問題

True x -- =&> x
x True -- =&> x


True是單位元

與all 大概的等價的實現是 :

all" f = foldr (x y -&> f x y) True


實際是這樣:

-- | Determines whether all elements of the structure satisfy the predicate.
all :: Foldable t =&> (a -&> Bool) -&> t a -&> Bool
all p = getAll #. foldMap (All #. p)


https://hackage.haskell.org/package/base-4.8.0.0/docs/src/Data-Foldable.html#all

根據foldr的定義:

foldr f z [] = z


也就是說對空表來說肯定是返回單位元的

好像也沒解釋得很清楚, 大概的想法是因為all可以轉化為等價的fold形式, 然後fold遵循某個定律, 所以all也遵循, 一旦不遵循不是all了, 這裡面需要些理論工具, 可能是Free theorem, 可惜不會, 就是這樣...

---

「所有元素都是奇數」等價於「沒有一個元素不是奇數」。

空集中一個元素都沒有，自然也就沒有「不是奇數的元素」。所以，空集中沒有一個元素不是奇數，亦即，空集的所有元素都是奇數。

如果一個集合的元素全都是奇數，那麼他的子集，其元素也應該全都是奇數。

{1} 顯然是「唯奇數集」，所以其子集 {} 也應當是「唯奇數集」。

初次見到 Vacuous truth 這一概念者往往會覺得不合常理、很難理解。但如果仔細考慮考慮，就會發現這是唯一符合常理的解釋。

---

@祖與占 說的「單位元」一語中的。

維基百科上Empty product這一篇解釋得也很好。

---

設x1 x2為兩個數組，

按照常理應該有odd(x1:::x2)=odd(x1)odd(x2)

取x1=[] x2非空 得到 odd([])=true

---

all f xs 所表達的語義為：

xs中的所有元素都滿足條件f

也即：

xs中不存在 不滿足條件f 的元素

所以，[]中不存在...的元素，當然是True

語義上的原因如此，@Geek.cs已經說得很清楚了，實現上的細節 @祖與占 也已經說得很清楚了，

所以如果你設計標準庫，設計一個通用的all函數，那麼基本上不會是另外一種樣子的。

當然如果你的具體應用場景中需要特殊處理空集，你可以再包裝一個特化的all自己用，比如可以在接受[]的時候返回Nothing，當然那樣返回值類型就是Maybe的了。 標準庫里的實現，在不用返回Maybe的情況下，也能做到邏輯的自洽，那自然是不會選擇實現成用起來這麼麻煩的東西的。

---

從程序實現角度來看，滿足全部是的最簡單邏輯是存在一個不滿足要求就返回非（循環判斷），最後默認情況就是真，類似快速失敗的策略，所以對於空集合結果為真。偽代碼如下

for x in xs
if x is not odd
return false
return true


另外一種策略是遞歸來實現全元素判斷，這裡仍舊會碰到空集合的臨界條件。除非你限制輸入不能為空，否則你必須得設定空集合的forall操作為真。

def forall(xs) =
xs match {
case nil =&> true
case x :: tail =&> x is odd and forall tail
}


直觀上來說空集合全不是奇數因為沒有數字而不是數字不是奇數，但是從實現上來說設定空集合forall操作結果為空是必然的副作用，類似你必須設置0的階乘結果一樣，所以如果認為空集合forall結果不符合預期大可在forall之前判斷，而不是在forall中判斷。至於其他答主的數學分析，也可以參考。

---

如果你自己用遞歸寫判斷一個數組是否為奇的方法

Head(x) x去掉最後一個元素

Tail(x) x的最後一個元素

odd(x)=odd(head(x)) (tail(x)%2==1)【對不起語法有點忘了。。

於是當x只有一個元素時就是

odd(空集) (tail(x)%2==1)

此時odd(空集)就只能為true

---

但我仍然覺得這有悖語義..

那麼說明你對語義的理解弱……

干一行就要學一行的思維方式。如果你搞編程若干年，你對語義的理解還停留在你日常生活里的那一套理解中，那才是悲劇。

要注意日常生活中的語義本來就是有很多約定俗成的，反邏輯的地方。比如說黑人英語里「People ain"t no good」，意思是「People are not good」（雙重否定表否定），我們以正常英語和正常漢語的邏輯都是揣度不了的。更不要說「曬太陽」為什麼和「曬東西」形式對不上，「我們打敗了」為什麼和「我們打敗了敵人」意思相反，等等……

所以說，要是我們的數學尤其是邏輯學是建立在日常語言這套鬼東西上的，我們就完了。好在雖然古人確實遇到了這個坑（什麼白馬非馬啦，什麼法國的國王是禿子啦，等等），但是現代的邏輯學終於通過精確的手段解決了這裡的大部分語言上的問題。程序語言也是建立在這種語義清晰的邏輯學上的，自然也繼承了它的想法。而且你沒有別的選項，要不然就按邏輯辦事，要不然就是一鍋粥……

---

short ver: 那你覺得應該返回啥？False？error ？ Maybe Bool ?

---

數學上叫做vacuous truth: Vacuous truth 很久以前上拓撲課時經常用到

這個很符合直覺啊，為何題主會覺得反人類。就像wiki中的例子，如果一個人問「這個房間里所有的手機都關了嗎？」 如果剛好房間里所有人都沒帶手機，正常人都不會回答否吧。

或許按逆否命題更好理解：array中沒有偶數

---

這和編程沒有關係，單純是邏輯上的問題，翻譯到邏輯語言就是

forall x in {}, x is odd

這個等價於一個前提為假的命題，也就是 False -&> ?, 而前提False的命題任何時候都為真

---

推薦閱讀：