如何将嵌套列表展开为一维

文章说明
文章作者：鴻塵
参考资料：

• How to make a flat list out of a list of lists?
• Right Foot In: More on python flatten（有缘人才能打开）
• Flatten an irregular list of lists
• How Not to Flatten a List of Lists in Python

文章链接：https://hwame.top/20210610/flatten-a-nested-list.html

1.引言

闲来无事逛Stack Overflow，发现了一个挺有意思的问题：How to make a flat list out of a list of lists?。

# 怎样快速优雅地将src转换成dst？
src = [[1, 2, 3], [4, 5, 6], [7], [8, 9]]
dst = [1, 2, 3, 4, 5, 6, 7, 8, 9]

乍一看，对于所给的二维数组，for循环是最容易想到的思路，但是有没有some cool “one-liner”的办法呢？顺着这个问题往下看，还挺有意思。

说明：此处仅讨论各方法的正确性，至于性能和效率可自行测试。

2.解决方案

2.1.方法一：functools.reduce

该问题的提出者Emma提供了一个思路，利用标准库函数reduce：

from functools import reduce
src = [[1, 2, 3], [4, 5, 6], [7], [8, 9]]
#reduce(lambda x, y: x.extend(y), src)
reduce(lambda x, y: x + y, src)

这个方法是可行的，但为何不能用x.extend(y)呢？原因是列表的extend方法不返回值（返回None），故在下一轮次的reduce过程中会导致None.extend，从而raise AttributeError: 'NoneType' object has no attribute 'extend'。而列表加法则会返回「extended」列表。

如果非要用extend呢？既然返回None，我们是否可以人为给返回赋值？LBarret给出了一个方案：reduce(lambda x, y : x.extend(y) or x, src, [])，或者省略initial参数：reduce(lambda x, y : x.extend(y) or x, src)。其中x.extend(y) or x实现了x + y并返回x，因为bool(x.extend(y)) = False。

Greg Hewgill提到，extend()方法会修改列表x，而不是返回一个functools.reduce()所期望的「有用的」值，因此x + y优于x.extend(y)。

需要指出的是，这种reduce方法只能解决二维数组，多层嵌套或非列表元素将抛错，例如：

src1 = [[1], [], [2, 3, 4], 5]           # 含有非列表元素5
src2 = [[1], [], [2, 3], [[4], [5, 6]]]  # 多层嵌套
reduce(lambda x, y: x + y, src1)
# TypeError: can only concatenate list (not "int") to list

reduce(lambda x, y: x + y, src2)
# [1, 2, 3, [4], [5, 6]]
# 只能展开一层，若再reduce一次则含非列表元素

2.2.方法二：列表生成式

列表生成式也是很容易想到的办法，因为它本质上就是for循环：

# 列表生成式
dst = [item for sublist in src for item in sublist]

# for循环等价写法
dst = []
for sublist in src:
    for item in sublist:
        dst.append(item)

# lambda表达式
flatten = lambda t: [item for sublist in t for item in sublist]
dst = flatten(src)

两层for循环写成列表生成式不太直观，借用John Mee的例子会更容易理解和应用：[leaf for tree in forest for leaf in tree]。表达式中「叶 → 树 → 林」的关系很清晰地表现了内外循环的层级。

当然也有不同的观点，例如Eric Duminil和Davos。尽管John Mee的写法与for循环相同，但顺序杂乱不易理解（直观仅限于leaf、tree和forest），Davos更推荐使用leaf for leaf in tree for tree in forest这种「递进式写法」。

2.3.方法三：itertools.chain

itertools.chain先将二维数组解包为一维然后连接为迭代器，再转化为列表；itertools.chain.from_iterable则无需先解包：

import itertools
src = [[1, 2, 3], [4, 5, 6], [7], [8, 9]]

dst = list(itertools.chain(*src))
dst = list(itertools.chain.from_iterable(src))

借用该回答下Tim Dierks的评论，*将列表解包为多个参数传递给chain，导致将顶级列表（最外层）扩展为参数，再将这些可迭代对象连接在一起而不会进入更深层级。在这种情况下，列表生成式将比链式用法的可读性更好。

2.4.方法四：sum

这种方法既不直观也不高效，但是很有趣，计算机科学中的monoids定义如下：

Monoids in computer science【来自维基百科】

在计算机科学中，许多抽象数据类型（Abstract Data Types，ADT）都具有monoid结构。在一个常见的模式中，monoid的一系列元素被「折叠)」或「累积」以产生最终值。例如，许多迭代算法需要在每次迭代时更新某种「运行总数」；这种模式可以通过monoid运算优雅地表达。或者，monoid运算的关联性确保可以通过使用前缀和或类似算法来并行化运算，以便有效地利用多个内核或处理器。
给定一系列「$M$类型」且具有「标识元素$\varepsilon$」和「关联操作$\bullet$」的值，折叠操作定义如下：

$$\displaystyle \mathrm {fold:} M^{*}\rightarrow M=\ell \mapsto {\begin{cases}\varepsilon &{\mbox{if }}\ell =\mathrm {nil} \\m\bullet \mathrm {fold}\,\ell '&{\mbox{if }}\ell =\mathrm {cons} \,m\,\ell '\end{cases}}$$

此外，如果给定其元素的序列化，任何数据结构都可以以类似的方式「折叠」。例如，「折叠」二叉树的结果可能会因遍历方式（前序遍历pre-order与后序遍历post-order）的不同而不同。

代码如下：

src = [[1, 2, 3], [4, 5, 6], [7], [8, 9]]
dst = sum(src, [])

这只是对第一个参数中传递的iterable元素进行求和，而将第二个元素视为总和的初始值。sum函数的声明为sum(iterable, start=0, /)，在上例中如果不传仅限位置参数start，将取默认值0，在这种情况下将抛出TypeError：不能将整数和列表相加。

毫无疑问，这种方法是所有答案中最「简洁」、最「聪明」的，答案评论区争论的焦点之一就是低效，原因是列表连接时产生了大量不必要的复制，时间复杂度高达$O(n^2)$。当然，这并非本文重点，有兴趣可移步Mathieu Larose的文章：How Not to Flatten a List of Lists in Python。

同时，该方法仅用于二维嵌套列表，对于更深层级的嵌套，则需寻求其他方法。

2.5.方法五：现有的轮子

有这么句话，Do not reinvent the wheel!，即不要重复造轮子。Max Malysh可谓是贯彻了这一理念，很多第三方库甚至是python自带的库或函数，都提供了相应的方法：

src = [[1, 2, 3], [4, 5, 6], [7], [8, 9]]
# Django
from django.contrib.admin.utils import flatten
dst = flatten(src)

# Pandas
from pandas.core.common import flatten
dst = list(flatten(src))

# Numpy
from numpy import concatenate
dst = list(concatenate(src))

# Matplotlib
from matplotlib.cbook import flatten
dst = list(flatten(src))

# Unipath
from unipath.path import flatten
dst = list(flatten(src))

# Setuptools
from setuptools.namespaces import flatten
dst = list(flatten(src))

pandas提供的flatten函数不仅能解决多层嵌套，还能连接整数和列表，这或许是终极答案了。

关于造轮子的说法，使用别人造好了的轮子固然可以提高效率，但是自己造轮子难道不是一种更好的学习方式吗？正如Nathan Chappell所言：

All these great libraries reinvented the wheel, why shouldn’t I?

2.6.方法六：operator

operator模块中提供了很多方法，例如concat、add等，需要配合functools.reduce一起使用：

from functools import reduce
import operator
src = [[1, 2, 3], [4, 5, 6], [7], [8, 9]]

reduce(operator.concat, src)
reduce(operator.add, src)

2.6.方法七：map

Daniel Braun给出的map方法，个人认为不是很好（可能这也是vote数比较少的原因吧）：

def flatten(src):
    dst = []
    tmp = list(map(dst.extend, src))
    return dst

flatten([[1, 2, 3], [4, 5, 6], [7], [8, 9]])

3.其他问题

上述各种方法都有一定的局限性，最大的问题就是对于数据类型的制约以及嵌套深度的限制，pylang给出了一种适用于数字、字符串、嵌套列表及其复合体的通用方法，该方法参考了Cristian的在Flatten an irregular list of lists的回答：

from typing import Iterable 
def flatten(items):
    for x in items:
        if isinstance(x, Iterable) and not isinstance(x, (str, bytes)):
            yield from flatten(x)
            # *注：上句可展开为
            # for sub_x in flatten(x):
            #     yield sub_x
        else:
            yield x

list(flatten([[1, 2, 3], [4, 5, 6], [7], [8, 9]]))   # 简单情况
list(flatten([[1, [2]], (3, 4, {5, 6}, 7), 8, "9"])) # 复杂情况