列表推导式
列表推导式(list comprehension),是程序设计语言的一类语法结构,用于基于描述创建一个列表(list)数据结构。相当于数学上的集合建構式符號。但不同于map与filter函数。
“list comprehension”没有统一的中文译法。有译作列表解析式、列表生成式、列表构建、列表理解等。
概述
考虑下述集合建構式符號:
可读作"是所有"2乘"的数的集合,满足是自然数()且的平方大于."
- 是输入集合的变量
- 表示输入集合,这里是自然数
- 是谓词表示式用于从输入集筛选
- 是输出表达式,用于产生新的集合
- 花括号表示输出值组成集合
- 竖杠与逗号为分隔符
列表推导式与从一个输入列表或迭代器依次生成一个列表的表示有相同的语法构件:
- 代表输入列表的成员的一个变量。
- 一个输入列表(或迭代器)。
- 一个可选的谓词(判断)表达式。
- 和从满足这个判断的输入可迭代者的成员产生输出列表的成员的一个表达式。
在Haskell的列表推导式语法中,这个集合建造结构类似的写为如下:
s = [ 2*x | x <- [0..], x^2 > 3 ]
这里的列表[0..]
表示,x^2>3
表示谓词,而2*x
表示输出表达式。列表推导式按一个确定次序(不同于集合的成员)给出结果;并且列表推导式可以依次生成一个列表的成员,而非生成这个列表的全体,因此允许先前的无穷列表的成员的Haskell定义。
Python语言用于生成列表的语法示例:
>>> s = [x**2 for x in range(10) if x % 2 ]
>>> print(s)
[1, 9, 25, 49, 81]
>>> type(s)
<class 'list'>
>>>
历史
在术语“列表推导式”使用之前就有了有关构造的存在。SETL编程语言(1969年)有类似列表推导式的一种形成构造。比如,这个代码答应从2到N的所有素数:
print([n in [2..N] | forall m in {2..n - 1} | n mod m > 0]);
计算机代数系统AXIOM(1973年)有处理串流的类似构造。
对这种构造的首次使用术语“推导式”是在Rod Burstall和John Darlington自从1977年后对他们的函数式编程语言NPL的描述中。David Turner在他的回顾《函数式编程语言的一些历史》中回忆道[1]:
NPL由Burstall用POP2实现并被Darlington用于程序变换的工作(Burstall & Darlington 1977)。这个语言是一阶、强类型的(但不多态)、纯函数式、传值调用的。它还有“集合表达式”比如:
setofeven (X) <= <:x : x in X & even(x):>}}
类似构造
集合推导式
Python语言用于生成集合的语法示例:
>>> s = {v for v in 'ABCDABCD' if v not in 'CB'}
>>> print(s)
{'A', 'D'}
>>> type(s)
<class 'set'>
>>>
字典推导式
>>> s = {key: val for key, val in enumerate('ABCD') if val not in 'CB'}
>>> s
{0: 'A', 3: 'D'}
>>>
并行列表推导式
Python语言的语法示例:
# regular list comprehension
>>> a = [(x, y) for x in range(1, 6) for y in range(3, 6)]
[(1, 3), (1, 4), (1, 5), (2, 3), (2, 4), ...
# parallel/zipped list comprehension
>>> b = [x for x in zip(range(1, 6), range(3, 6))]
[(1, 3), (2, 4), (3, 5)]
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
}
注释与引用
- Turner, David. (PDF). : 1–20. 2012 [2020-09-10]. (原始内容存档 (PDF)于2020-04-15).
- List Comprehension in The Free On-line Dictionary of Computing, Editor Denis Howe.
- Trinder, Phil. . : 55–68. 1992.
- Wadler, Philip. . . 1990 [2020-09-10]. (原始内容存档于2008-03-29).
- Wong, Limsoon. . . International Conference on Functional Programming: 1–10. 2000.
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
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
Axiom
外部链接
- 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 页面存档备份,存于