How to flatten a list of lists in Python
Turning [[1, 2], [3, 4]] into [1, 2, 3, 4] has one obvious answer, one
tempting answer that gets slow, and one recursive answer that crashes on
strings if you write it the natural way.
The answer
flat = [x for sub in nested for x in sub]
nested = [[1, 2], [3, 4], [5, 6]]
[x for sub in nested for x in sub] : [1, 2, 3, 4, 5, 6]
The clause order that nobody gets right first time
The for clauses read left to right, outermost first — the same order you
would write them as statements:
result = []
for sub in nested: # outer first
for x in sub: # inner second
result.append(x)
Which is confusing because the expression at the front (x) is the innermost
thing. If you try it the other way round the reason becomes obvious:
[x for x in sub for sub in nested] -> NameError: name 'sub' is not defined
sub does not exist yet when the first clause runs. There is only one order
that can work.
The lazy version
from itertools import chain
flat = list(chain.from_iterable(nested))
list(chain.from_iterable(nested)) : [1, 2, 3, 4, 5, 6]
it is lazy : chain
chain.from_iterable
is the one I reach for when the result feeds straight into something else,
because it never builds the flat list at all:
next() twice : 1, 2
sum without materialising : 21
There is also chain(*nested), which does the same thing but unpacks the whole
outer list into arguments first — so it loses the laziness and will not work on
an infinite outer iterable.
The tempting one that gets slow
sum(nested, [])
It works, and it is quadratic. Every step builds a new list containing everything seen so far, so flattening n sublists copies roughly n²/2 elements.
Measured with 1000 sublists:
sum(data, []) : 0.0127 s
comprehension : 0.0005 s
chain.from_iterable : 0.0004 s
sum() is 24x slower than the comprehension
Now four times the input:
4000 sublists (4x the input), 5 runs each:
sum(data, []) : 0.0459 s
comprehension : 0.0005 s
ratio : 87x
The comprehension barely moved. The gap went from 24x to 87x. Quadratic behaviour is invisible on the small inputs you test with and unmissable on the real ones.
CPython feels strongly enough about this to refuse the string version outright:
sum(['ab','cd'], '') -> TypeError: sum() can't sum strings [use ''.join(seq) instead]
The error message names the fix, which is a nice touch. There is no equivalent guard for lists, so that case just runs slowly.
One level only
All three forms above flatten exactly one level:
deep = [1, [2, [3, [4]]]]
comprehension -> TypeError: 'int' object is not iterable
The integer 1 is not iterable, so the inner loop has nothing to do with it.
For arbitrary depth you need recursion:
def flatten(item):
for element in item:
if isinstance(element, (list, tuple)):
yield from flatten(element)
else:
yield element
recursive flatten : [1, 2, 3, 4]
The version that crashes
Here is the same function with what looks like a more general test — anything iterable gets flattened:
if hasattr(element, "__iter__"):
yield from naive_flatten(element)
On ["ab", ["cd"]]:
checking __iter__ -> RecursionError: maximum recursion depth exceeded
A string is iterable, so "ab" gets taken apart into "a" and "b". And
"a" is also iterable — iterating a one-character string yields that same
one-character string. The recursion never reaches a base case.
Checking isinstance(element, (list, tuple)) instead is not a stylistic
preference. It is the difference between working and a traceback:
checking isinstance(x, (list, tuple)) : ['ab', 'cd']
The general lesson is that “is it iterable” is almost never the question you
mean in Python, because str, bytes and dict all answer yes in ways you
did not intend.
A couple of variations
Ragged and empty sublists need no special handling:
[[1], [], [2, 3, 4], []] -> [1, 2, 3, 4]
And the same comprehension shape flattens a dict of lists, either to the values or to pairs:
values : [1, 2, 3]
pairs : [('a', 1), ('a', 2), ('b', 3)]
About Netcup (advertisement)
The German host Netcup offers, among other things, affordable and powerful web hosting packages, KVM-based root servers and dedicated servers. With our voucher codes you can save even more (6€ off your first order, 30% off all KVM-based root servers, ...).