列表推导式

列表推导式(list comprehension),是程序设计语言的一类语法结构,用于基于描述创建一个列表(list)数据结构。相当于数学上的集合建构式符号。但不同于mapfilter函数。

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

概述

考虑下述集合建构式符号

 

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

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

列表推导式,与从一个输入列表迭代器,依次生成一个列表的表示,有相同的语法构件:

  • 代表输入列表的成员的一个变量。
  • 一个输入列表(或迭代器)。
  • 一个可选的谓词(判断)表达式。
  • 和从满足这个判断的,输入可迭代者的成员,产生输出列表的成员的一个表达式。

Haskell的列表推导式语法中,上述集合建造结构类似的写为如下:

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

这里的列表[0..]表示 x^2 > 3表示谓词,而2*x表示输出表达式。列表推导式,按一个确定次序,给出结果(不同于集合的成员);并且列表推导式,可以依次生成一个列表的成员,而非生成这个列表的全体,从而允许前面的对一个无穷列表的成员的Haskell定义。

历史

在术语“列表推导式”使用之前,就存在了有关的构造。集合论编程语言SETL(1969年),有类似列表推导式的一种形成构造。比如,这个代码打印从2N的所有素数:

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
}

参见

延伸阅读

  • 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].

参考文献

外部链接