列表推导式

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

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

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

可读作：“是所有“乘”的数的集合，满足是自然数，并且的平方大于。”

  是表示输入集合的成员的变量。
  表示输入集合，这里是自然数。
  是谓词表示式，用于从输入集筛选。
  是输出表达式，用于产生新的集合。 
  花括号表示输出值组成集合。
  竖杠读作“满足”，可以同冒号“:”互换使用。
  逗号分隔谓词，可以读作“并且”。

列表推导式，与从一个输入列表或迭代器，依次生成一个列表的表示，有相同的语法构件：
 代表输入列表的成员的一个变量。
 一个输入列表（或迭代器）。
 一个可选的谓词（判断）表达式。
 和从满足这个判断的，输入可迭代者的成员，产生输出列表的成员的一个表达式。

在Haskell的列表推导式语法中，上述集合建造结构类似的写为如下：
s = [ 2*x | x <- [0..], x^2 > 3 ]
这里的列表[0..]表示，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]);
计算机代数系统（1973年），有处理串流的类似构造。

首次对这种构造的使用术语“推导式”，是在1977年以后，和John Darlington，用在他们的函数式编程语言NPL的描述之中。在的回忆录《函数式编程语言的一些历史》中，他回想起：
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编译器，拥有一个扩展叫作“并行列表推导式”（也叫做拉链推导式），它允许在列表推导式语法中，有多个独立分支的限定符<-。用逗号,分隔的限定符，是依赖的（“嵌套的”）；而用管道符号|分隔的限定符，是并行求值的（这不涉及任何形式的多线程性，这只意味着这些分支是被合并的）。
-- 常规列表推导式
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中，单子推导式将列表推导式，推广为适用于任何单子。

集合推导式
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 idiom来构造列表推导以选择容器中的元素，并使用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
}

参见

延伸阅读
List Comprehension in The Free On-line Dictionary of Computing, Editor Denis Howe.

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

OCaml
 OCaml Batteries Included.
 Language extensions introduced in OCaml Batteries Included.

Python
 The Python Tutorial, List Comprehensions.
 Python Language Reference, List displays.
 Python Enhancement Proposal PEP 202: List Comprehensions.
 Python Language Reference, Generator expressions.
 Python Enhancement Proposal PEP 289: Generator Expressions.

Common Lisp
 Implementation of a Lisp comprehension macro by Guy Lapalme.

Clojure
 Clojure API documentation - for macro.

Axiom
 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 

程序架构
带有代码示例的条目