列表推導式

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

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

概述

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

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

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

${\displaystyle 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{谓 词}}}\}}$

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

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

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

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

s = [ 2*x | x <- [0..], x^2 > 3 ]

這裡的列表[0..]表示${\displaystyle \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（英語：Axiom (computer algebra system)）（1973年），有處理串流的類似構造。

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

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語言的列表推導式和生成器表達式的語法示例：

>>> s = [2*x for x in range(10) if x**2 > 3]
>>> print(s)
[4, 6, 8, 10, 12, 14, 16, 18]
>>> from itertools import count, islice
>>> s = (2*x for x in count(0) if x**2 > 3)
>>> t = islice(s, 10)
>>> print([*t])
[4, 6, 8, 10, 12, 14, 16, 18, 20, 22]
>>> print([*t])
[]
>>> t = islice(s,10)
>>> print([*t])
[24, 26, 28, 30, 32, 34, 36, 38, 40, 42]

推廣

並行列表推導式

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

-- 常规列表推导式
a = [(x,y) | x <- [1..5], y <- [6..8]]
-- [(1,6),(1,7),(1,8),(2,6),(2,7),(2,8),(3,6),(3,7),(3,8),(4,6),(4,7),(4,8),(5,6),(5,7),(5,8)]

-- 拉链列表推导式
b = [(x,y) | (x,y) <- zip [1..5] [6..8]]
-- [(1,6),(2,7),(3,6)]

-- 并行列表推导式
c = [(x,y) | x <- [1..5] | y <- [6..8]]
-- [(1,6),(2,7),(3,8)]

Python語言的語法示例：

# 常规列表推导式
>>> [(x, y) for x in range(1, 6) for y in range(6, 9)]
[(1, 6), (1, 7), (1, 8), (2, 6), (2, 7), (2, 8), (3, 6), (3, 7), (3, 8), (4, 6), (4, 7), (4, 8), (5, 6), (5, 7), (5, 8)]

# 并行/拉链列表推导式
>>> s = zip(range(1, 6), range(6, 9))
>>> t = [x for x in s]
>>> print(t)
[(1, 6), (2, 7), (3, 8)]
>>> from operator import add
>>> [*map(add, range(1, 6), range(6, 9))] # 有二个实际参数列表的map相当于Haskell的zipWith
[7, 9, 11]
>>> from itertools import starmap, zip_longest
>>> [*starmap(add, t)]
[7, 9, 11]
>>> s = zip_longest(range(1, 6), range(6, 9))
>>> t = [*s]
>>> print(t)
[(1, 6), (2, 7), (3, 8), (4, None), (5, None)]
>>> [*zip(*t)]
[(1, 2, 3, 4, 5), (6, 7, 8, None, None)]

單子推導式

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

集合推導式

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

>>> s = {v for v in 'ABCDABCD' if v not in 'CB'}
>>> print(s)
{'A', 'D'}

字典推導式

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

>>> s = {key: val for key, val in enumerate('ABCD') if val not in 'CB'}
>>> print(s)
{0: 'A', 3: 'D'}

類似構造

C++

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

#include <algorithm>
#include <list>
#include <numeric>

using namespace std;

template<class C, class P, class T>
C comprehend(C&& source, const P& predicate, const T& transformation)
{
  // 初始化目标
  C d = forward<C>(source);

  // 元素过滤
  d.erase(remove_if(begin(d), end(d), predicate), end(d));

  // 应用变换
  for_each(begin(d), end(d), transformation);

  return d;
}

int main()
{
  list<int> range(10);  
      // range 是一个有10个元素的list, 全是0
  iota(begin(range), end(range), 1);
      // range 现在包含 1,2,...,10

  list<int> result = comprehend(
      range,
      [](int x){return x*x <= 3;},
      [](int &x){x *= 2;});
      // 结果现在包含 4,6,...,20
}

參見

• 程式語言的列表推導式比較（英語：Comparison of programming languages (list comprehension)）

延伸閱讀

• List Comprehension^[3] 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.

Haskell

• The Haskell 98 Report, chapter 3.11 List Comprehensions^[4].
• The Glorious Glasgow Haskell Compilation System User's Guide, chapter 7.3.4 Parallel List Comprehensions^[5].
• The Hugs 98 User's Guide, chapter 5.1.2 Parallel list comprehensions (a.k.a. zip-comprehensions)^[6].

OCaml

• OCaml Batteries Included^[7].
• Language extensions introduced in OCaml Batteries Included^[8].

Python

• The Python Tutorial, List Comprehensions^[9].
• Python Language Reference, List displays^[10].
• Python Enhancement Proposal PEP 202: List Comprehensions^[11].
• Python Language Reference, Generator expressions^[12].
• Python Enhancement Proposal PEP 289: Generator Expressions^[13].

Common Lisp

• Implementation of a Lisp comprehension macro^[14] by Guy Lapalme.

Clojure

• Clojure API documentation - for macro^[15].

Axiom

• Axiom stream examples^[16].

參考文獻

1. Turner, David. Some history of functional programming languages (PDF). International Symposium on Trends in Functional Programming, Springer, Berlin, Heidelberg: 1–20. 2012 [2020-09-10]. （原始內容存檔 (PDF)於2020-04-15）.
2. GHC User’s Guide － Monad comprehensions. [2021-03-16]. （原始內容存檔於2021-03-24）.
3. List Comprehension
4. 3.11 List Comprehensions （頁面存檔備份，存於網際網路檔案館）
5. 7.3.4 Parallel List Comprehensions
6. 5.1.2 Parallel list comprehensions (a.k.a. zip-comprehensions)
7. OCaml Batteries Included（頁面存檔備份，存於網際網路檔案館）
8. Language extensions introduced in OCaml Batteries Included （頁面存檔備份，存於網際網路檔案館）
9. List Comprehensions （頁面存檔備份，存於網際網路檔案館）
10. List displays （頁面存檔備份，存於網際網路檔案館）
11. PEP 202: List Comprehensions （頁面存檔備份，存於網際網路檔案館）
12. Generator expressions （頁面存檔備份，存於網際網路檔案館）
13. PEP 289: Generator Expressions （頁面存檔備份，存於網際網路檔案館）
14. Implementation of a Lisp comprehension macro （頁面存檔備份，存於網際網路檔案館）
15. Clojure API documentation - for macro （頁面存檔備份，存於網際網路檔案館）
16. Axiom stream examples

外部連結

• 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 （頁面存檔備份，存於網際網路檔案館）