List_comprehension

**列表推導式**（list comprehension），是程序設計語言的一類語法結構，用於基於描述創建一個列表（list）資料結構。相當於數學上的集合建構式符號。但不同於 map 與 filter 函數。

「list comprehension」沒有統一的中文譯法。有譯作列表解析式、列表生成式、列表構建、列表理解等。

## 概述

考慮下述集合建構式符號：

　
: $S=\{2\cdot x\mid x\in \mathbb {N} ,\ x^{2}>3\}$

可讀作：「 $S$ 是所有「 $2$ 乘 $x$ 」的數的集合，滿足 $x$ 是自然數 $\mathbb {N} $ ，並且 $x$ 的平方大於 $3$ 。」

　
: $S=\{\underbrace {2\cdot x} _{\color {Violet}{\text{输 出 表 达 式}}}\mid \underbrace {x} _{\color {Violet}{\text{变 量}}}\in \underbrace {\mathbb {N} } _{\color {Violet}{\text{输 入 集 合}}},\ \underbrace {x^{2}>3} _{\color {Violet}{\text{谓 词}}}\}$

 * $x$ 是表示輸入集合的成員的變量。
* $\mathbb {N} $ 表示輸入集合，這裡是自然數。
* $x^{2}>3$ 是謂詞表示式，用於從輸入集篩選。
* $2\cdot x$ 是輸出表達式，用於產生新的集合。
* $\{\}$ 花括號表示輸出值組成集合。
* $\mid $ 豎槓讀作「滿足」，可以同冒號「:」互換使用。
* $,$ 逗號分隔謂詞，可以讀作「並且」。

列表推導式，與從一個輸入列表或迭代器，依次生成一個列表的表示，有相同的語法構件：

* 代表輸入列表的成員的一個變量。
* 一個輸入列表（或迭代器）。
* 一個可選的謂詞（判斷）表達式。
* 和從滿足這個判斷的，輸入可迭代者的成員，產生輸出列表的成員的一個表達式。

在 Haskell 的列表推導式語法中，上述集合建造結構類似的寫為如下：

這裡的列表 `[0..]` 表示 $\mathbb {N} $ ，`x^2 > 3` 表示謂詞，而 `2*x` 表示輸出表達式。列表推導式，按一個確定次序，給出結果（不同於集合的成員）；並且列表推導式，可以依次生成一個列表的成員，而非生成這個列表的全體，從而允許前面的對一個無窮列表的成員的 Haskell 定義。

## 歷史

在術語「列表推導式」使用之前，就存在了有關的構造。集合論編程語言 SETL（1969 年），有類似列表推導式的一種形成構造。比如，這個代碼列印從 `2` 到 `N` 的所有素數：

　
: ```
print([n in [2..N] | forall m in {2..n - 1} | n mod m > 0]);
```

計算機代數系統 AXIOM（1973 年），有處理串流的類似構造。

首次對這種構造的使用術語「推導式」，是在 1977 年以後，Rod Burstall 和 John Darlington，用在他們的函數式程式語言 NPL 的描述之中。在 David Turner 的回憶錄《函數式程式語言的一些歷史》中，他回想起：

　
: NPL 由 Burstall 用 POP2 實現，並被 Darlington 用於程序變換的工作（Burstall & Darlington 1977）。這個語言，是一階、強類型（但不多態）、純函數式、傳值調用的。它還有「集合表達式」比如：

　
: ```
setofeven (X)  <=  <:x : x in X & even(x):>
```

在給術語「列表推導式」附加的腳註中，Turner 還記述了：

　
: 我最初稱其為「ZF 表達式」，參照了 Zermelo-Frankel 集合論，Phil Wadler 鑄就了更好的術語「列表推導式」。

Burstall 和 Darlington 關於 NPL 的工作，在 1980 年代影響了很多函數式程式語言，但並非全部都包括了列表推導式。其中最有影響的，是 1985 年發行的，Turner 的惰性純函數式程式語言 Miranda。後來開發的標準惰性純函數式語言 Haskell，包含了 Miranda 的很多特徵，包括列表推導式。

## Python 示例

Python 語言的列表推導式和生成器表達式的語法示例：

## 推廣

### 並行列表推導式

格拉斯哥 Haskell 編譯器，擁有一個擴展叫作「並行列表推導式」（也叫做拉鏈推導式），它允許在列表推導式語法中，有多個獨立分支的限定符 `<-`。用逗號 `,` 分隔的限定符，是依賴的（「嵌套的」）；而用管道符號 `|` 分隔的限定符，是並行求值的（這不涉及任何形式的多執行緒性，這隻意味著這些分支是被拉鏈合併的）。

Python 語言的語法示例：

### 單子推導式

在 Haskell 中，單子推導式將列表推導式，推廣為適用於任何單子。

### 集合推導式

Python 語言用於生成集合的語法示例：

### 字典推導式

Python 語言用於生成字典（關聯數組）的語法示例：

## 類似構造

### C++

C++ 沒有直接支持列表推導的任何語言特性，但運算符重載（例如，重載 |，>>，>> =）已成功用於為「嵌入式」查詢領域特定語言提供表達式語法。 或者，可以使用 erase-remove idiom 來構造列表推導以選擇容器中的元素，並使用 STL 算法 for\_each 來轉換它們。

## 參見

* 程式語言的列表推導式比較

## 延伸閱讀

* List Comprehension in The Free On-line Dictionary of Computing, Editor Denis Howe.
* Trinder, Phil. Comprehensions, a query notation for DBPLs. Proceedings of the third international workshop on Database programming languages: bulk types & persistent data, Nafplion, Greece: 55–68. 1992.
* Wadler, Philip. Comprehending Monads. Proceedings of the 1990 ACM Conference on LISP and Functional Programming, Nice. 1990 [2021-03-16]. （原始內容存檔於 2020-11-11）.
* Wong, Limsoon. The Functional Guts of the Kleisli Query System. Proceedings of the fifth ACM SIGPLAN international conference on Functional programming. International Conference on Functional Programming: 1–10. 2000.

## 參考文獻

## 外部連結

* SQL-like set operations with list comprehension one-liners in the Python Cookbook（頁面存檔備份，存於網際網路檔案館）
* Discussion on list comprehensions in Scheme and related constructs （頁面存檔備份，存於網際網路檔案館）
* List Comprehensions across languages （頁面存檔備份，存於網際網路檔案館）