查看“︁列表推导式”︁的源代码

'''列表推导式'''（list comprehension），是程序设计语言的一类语法结构，用于基于描述创建一个列表（list）数据结构。相当于数学上的[[集合建構式符號]]。但不同于[[map (高阶函数)|map]]与[[filter (高阶函数)|filter]]函数。

“list comprehension”没有统一的中文译法。有译作列表解析式、列表生成式、列表构建、列表理解等。

==概述==
考虑下述[[集合建構式符號]]：

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

可读作：“<math>S</math>是所有“<math>2</math>乘<math>x</math>”的数的集合，满足<math>x</math>是自然数<math>\mathbb{N}</math>，并且<math>x</math>的平方大于<math>3</math>。”

:<math>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{谓 词}}}\}</math>
* <math>x</math> 是表示输入集合的成员的变量。
* <math>\mathbb{N}</math> 表示输入集合，这里是[[自然数]]。
* <math>x^2>3</math> 是[[谓词]]表示式，用于从输入集筛选。
* <math>2\cdot x</math> 是输出表达式，用于产生新的集合。 
* <math>\{\}</math> 花括号表示输出值组成集合。
* <math>\mid</math> 竖杠读作“满足”，可以同冒号“:”互换使用。
* <math>,</math> 逗号分隔谓词，可以读作“并且”。

列表推导式，与从一个输入[[串列 (抽象资料型别)|列表]]或[[迭代器]]，依次生成一个列表的表示，有相同的语法构件：
* 代表输入列表的成员的一个变量。
* 一个输入列表（或迭代器）。
* 一个可选的谓词（判断）表达式。
* 和从满足这个判断的，输入可迭代者的成员，产生输出列表的成员的一个表达式。

在[[Haskell]]的列表推导式语法中，上述集合建造结构类似的写为如下：
<syntaxhighlight lang="haskell">
s = [ 2*x | x <- [0..], x^2 > 3 ]
</syntaxhighlight>
这里的列表<code>[0..]</code>表示<math>\mathbb{N}</math>，<code>x^2 > 3</code>表示谓词，而<code>2*x</code>表示输出表达式。列表推导式，按一个确定次序，给出结果（不同于集合的成员）；并且列表推导式，可以依次[[生成器 (计算机编程)|生成]]一个列表的成员，而非生成这个列表的全体，从而允许前面的对一个无穷列表的成员的Haskell定义。

==历史==

在术语“列表推导式”使用之前，就存在了有关的构造。[[集论编程|集合论编程]]语言[[SETL]]（1969年），有类似列表推导式的一种形成构造。比如，这个代码打印从<code>2</code>到<code>N</code>的所有素数：
:<pre>print([n in [2..N] | forall m in {2..n - 1} | n mod m > 0]);</pre>
[[计算机代数系统]]{{en-link|Axiom (计算机代数系统)|Axiom (computer algebra system)|AXIOM}}（1973年），有处理[[字串流|串流]]的类似构造。

首次对这种构造的使用术语“推导式”，是在1977年以后，{{en-link|Rod Burstall}}和John Darlington，用在他们的函数式编程语言[[NPL (编程语言)|NPL]]的描述之中。在{{en-link|David Turner|David Turner (computer scientist)|David Turner}}的回忆录《函数式编程语言的一些历史》中，他回想起<ref>{{cite conference | first = David | last = Turner | url = https://www.cs.kent.ac.uk/people/staff/dat/tfp12/tfp12.pdf | title = Some history of functional programming languages | booktitle = International Symposium on Trends in Functional Programming, Springer, Berlin, Heidelberg | pages = 1–20 | year = 2012 | access-date = 2020-09-10 | archive-date = 2020-04-15 | archive-url = https://web.archive.org/web/20200415053847/https://www.cs.kent.ac.uk/people/staff/dat/tfp12/tfp12.pdf | dead-url = no }}</ref>：
:[[NPL (编程语言)|NPL]]由Burstall用[[POP-2|POP2]]实现，并被Darlington用于程序变换的工作（Burstall & Darlington 1977）。这个语言，是一阶、强类型（但不多态）、纯函数式、传值调用的。它还有“集合表达式”比如：
:<pre>setofeven (X)  <=  <:x : x in X & even(x):></pre>

在给术语“列表推导式”附加的脚注中，Turner还记述了：
:我最初称其为“ZF表达式”，参照了[[策梅洛-弗兰克尔集合论|Zermelo-Frankel集合论]]，[[Philip_Wadler|Phil Wadler]]铸就了更好的术语“列表推导式”。

Burstall和Darlington关于NPL的工作，在1980年代影响了很多函数式编程语言，但并非全部都包括了列表推导式。其中最有影响的，是1985年发行的，Turner的惰性纯函数式编程语言[[Miranda (编程语言)|Miranda]]。后来开发的标准惰性纯函数式语言[[Haskell]]，包含了Miranda的很多特征，包括列表推导式。

==Python示例==
[[Python]]语言的列表推导式和[[生成器 (计算机编程)|生成器]][[生成器 (计算机编程)#生成器表达式|表达式]]的语法示例：
<syntaxhighlight lang="pycon">
>>> 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]
</syntaxhighlight>

==推广==
===并行列表推导式=== 
[[格拉斯哥Haskell编译器]]，拥有一个扩展叫作“并行列表推导式”（也叫做拉链推导式），它允许在列表推导式语法中，有多个独立分支的限定符<code><-</code>。用逗号<code>,</code>分隔的限定符，是依赖的（“嵌套的”）；而用管道符号<code>|</code>分隔的限定符，是并行求值的（这不涉及任何形式的多线程性，这只意味着这些分支是被{{en-link|卷绕 (计算机科学)|Convolution (computer science)|拉链}}合并的）。
<syntaxhighlight lang="haskell">
-- 常规列表推导式
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)]
</syntaxhighlight>

[[Python]]语言的语法示例： 
<syntaxhighlight lang="pycon">
# 常规列表推导式
>>> [(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)]
</syntaxhighlight>

===单子推导式===
在[[Haskell]]中，[[单子 (函数式编程)#语法糖do表示法|单子推导式]]将列表推导式，推广为适用于任何单子<ref>{{cite web |url=https://ghc.gitlab.haskell.org/ghc/doc/users_guide/exts/monad_comprehensions.html |title=GHC User’s Guide － Monad comprehensions |access-date=2021-03-16 |archive-date=2021-03-24 |archive-url=https://web.archive.org/web/20210324052253/https://ghc.gitlab.haskell.org/ghc/doc/users_guide/exts/monad_comprehensions.html }}</ref>。

===集合推导式===
[[Python]]语言用于生成集合的语法示例：
<syntaxhighlight lang="pycon">
>>> s = {v for v in 'ABCDABCD' if v not in 'CB'}
>>> print(s)
{'A', 'D'}
</syntaxhighlight>

===字典推导式===
[[Python]]语言用于生成字典（[[关联数组]]）的语法示例： 
<syntaxhighlight lang="pycon">
>>> s = {key: val for key, val in enumerate('ABCD') if val not in 'CB'}
>>> print(s)
{0: 'A', 3: 'D'}
</syntaxhighlight>

==类似构造==
=== C++ ===

[[C++]]没有直接支持列表推导的任何语言特性，但[[运算符重载]]（例如，重载|，>>，>> =）已成功用于为“嵌入式”查询[[领域特定语言]]提供表达式语法。 或者，可以使用[[erase–remove惯用法]]来构造列表推导以选择容器中的元素，并使用STL算法for_each来转换它们。

<syntaxhighlight lang="cpp">
#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
}
</syntaxhighlight>

==参见==
*{{en-link|编程语言的列表推导式比较|Comparison of programming languages (list comprehension)}}

==延伸阅读==
*List Comprehension<ref>[https://web.archive.org/web/20050125080818/http://ftp.sunet.se/foldoc/foldoc.cgi?list+comprehension List Comprehension]</ref> in The Free On-line Dictionary of Computing, Editor Denis Howe.
*{{cite conference | first = Phil | last = Trinder | url = http://portal.acm.org/citation.cfm?coll=GUIDE&dl=GUIDE&id=135271 | title = Comprehensions, a query notation for DBPLs | booktitle = Proceedings of the third international workshop on Database programming languages: bulk types & persistent data, Nafplion, Greece | pages = 55–68 | year = 1992}}
*{{cite conference | first = Philip | last = Wadler | url = http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.33.5381 | title = Comprehending Monads | booktitle = Proceedings of the 1990 ACM Conference on LISP and Functional Programming, Nice | year = 1990 | conference =  | access-date = 2021-03-16 | archive-date = 2020-11-11 | archive-url = https://web.archive.org/web/20201111215332/http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.33.5381 }}
*{{cite conference | first = Limsoon | last = Wong | url = http://portal.acm.org/citation.cfm?id=351241&dl=ACM&coll=portal | title = The Functional Guts of the Kleisli Query System | conference = International Conference on Functional Programming | booktitle = Proceedings of the fifth ACM SIGPLAN international conference on Functional programming | pages = 1–10 | year = 2000}}
{{div col|2}}
;Haskell
*The Haskell 98 Report, chapter 3.11 List Comprehensions<ref>[http://haskell.org/onlinereport/exps.html#list-comprehensions 3.11 List Comprehensions] {{Wayback|url=http://haskell.org/onlinereport/exps.html#list-comprehensions |date=20201111163830 }}</ref>.
*The Glorious Glasgow Haskell Compilation System User's Guide, chapter 7.3.4 Parallel List Comprehensions<ref>[https://web.archive.org/web/20051129140339/http://www.haskell.org/ghc/docs/latest/html/users_guide/syntax-extns.html#parallel-list-comprehensions 7.3.4 Parallel List Comprehensions]</ref>.
*The Hugs 98 User's Guide, chapter 5.1.2 Parallel list comprehensions (a.k.a. zip-comprehensions)<ref>[https://web.archive.org/web/20140515114545/http://cvs.haskell.org/Hugs/pages/users_guide/hugs-ghc.html#ZIP-COMPREHENSION 5.1.2 Parallel list comprehensions (a.k.a. zip-comprehensions)]</ref>.

;OCaml
* OCaml Batteries Included<ref>[http://batteries.forge.ocamlcore.org/ OCaml Batteries Included]{{Wayback|url=http://batteries.forge.ocamlcore.org/ |date=20110626022306 }}</ref>.
* Language extensions introduced in OCaml Batteries Included<ref>[http://batteries.forge.ocamlcore.org/doc.preview:batteries-alpha3/html/extensions.html Language extensions introduced in OCaml Batteries Included] {{Wayback|url=http://batteries.forge.ocamlcore.org/doc.preview:batteries-alpha3/html/extensions.html |date=20160303172057 }}</ref>.

;Python
* The Python Tutorial, List Comprehensions<ref>[https://docs.python.org/tutorial/datastructures.html#list-comprehensions List Comprehensions] {{Wayback|url=https://docs.python.org/tutorial/datastructures.html#list-comprehensions |date=20121027080239 }}</ref>.
* Python Language Reference, List displays<ref>[https://docs.python.org/reference/expressions.html#list-displays List displays] {{Wayback|url=https://docs.python.org/reference/expressions.html#list-displays |date=20121026064102 }}</ref>.
* Python Enhancement Proposal PEP 202: List Comprehensions<ref>[https://www.python.org/peps/pep-0202.html PEP 202: List Comprehensions] {{Wayback|url=https://www.python.org/peps/pep-0202.html |date=20080516011158 }}</ref>.
* Python Language Reference, Generator expressions<ref>[https://docs.python.org/reference/expressions.html#generator-expressions Generator expressions] {{Wayback|url=https://docs.python.org/reference/expressions.html#generator-expressions |date=20121026064102 }}</ref>.
* Python Enhancement Proposal PEP 289: Generator Expressions<ref>[https://python.org/peps/pep-0289.html PEP 289: Generator Expressions] {{Wayback|url=https://python.org/peps/pep-0289.html |date=20080906210014 }}</ref>.

;Common Lisp
* Implementation of a Lisp comprehension macro<ref>[http://rali.iro.umontreal.ca/rali/?q=en/node/886 Implementation of a Lisp comprehension macro] {{Wayback|url=http://rali.iro.umontreal.ca/rali/?q=en%2Fnode%2F886 |date=20200626230800 }}</ref> by Guy Lapalme.

;Clojure
* Clojure API documentation - ''for'' macro<ref>[https://clojuredocs.org/clojure.core/for Clojure API documentation - ''for'' macro] {{Wayback|url=https://clojuredocs.org/clojure.core/for |date=20201111214557 }}</ref>.

;Axiom
* Axiom stream examples<ref>[https://web.archive.org/web/20051018040438/http://page.axiom-developer.org/zope/mathaction/Streams Axiom stream examples]</ref>.
{{div col end}}

== 参考文献 ==
{{Reflist|2}}

==外部链接==
* SQL-like set operations with list comprehension one-liners in the [http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/159974 Python Cookbook]{{Wayback|url=http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/159974 |date=20080702210432 }}
* [http://lambda-the-ultimate.org/classic/message11326.html Discussion on list comprehensions in Scheme and related constructs] {{Wayback|url=http://lambda-the-ultimate.org/classic/message11326.html |date=20200728004619 }}
* [http://langexplr.blogspot.com/2007/02/list-comprehensions-across-languages_18.html List Comprehensions across languages] {{Wayback|url=http://langexplr.blogspot.com/2007/02/list-comprehensions-across-languages_18.html |date=20201109035921 }}

{{编程范型}}
[[Category:程序架构]]
[[Category:带有代码示例的条目]]