Single-level list flattening in Python

July 13, 2010

I have been writing a bunch of Python code lately which involves turning lists of lists into plain lists. As it happens Python does not have a flatten() built-in, but people have come up with any number of ingenious ways to do this, some of which I actually like.

First, a stupid non-way that is worth writing down for posterity:

reduce(lambda x,y: x.extend(y), somelists, [])

This version is a classic mistake (one I made today, in fact). Your reward for trying this is the cryptic error "AttributeError: 'NoneType' object has no attribute 'extend'". What this really means is that you've forgotten that .extend() doesn't return anything (ie, it returns None), and the function that reduce() uses must return the accumulator variable. You can fix this by picking an equivalent list operation that does return a result:

reduce(lambda x,y: x+y, somelists, [])

This is both ugly and inefficient, although the inefficiency shouldn't bother you for small lists-of-lists. It is also equivalent to the simpler and slightly faster version:

sum(somelists, [])

All addition-based flatteners have the drawback that they only work on actual lists. If you have a list of tuples, or just a list of some sequence type that is not a list, you lose; list addition works only on two lists.

The best solution is a rare good use of a multi-level list comprehension:

[item for sublist in somelists for item in sublist]

This will work on any sequence type and for any mixture of sequence types (or iterables); you can have an iterable that returns a mixture of lists, tuples, and other iterables and everything will work out and you will get a list at the end.

The multi-level list comprehension approach is both the fastest and the most general, but it's kind of verbose and hard to follow if you're not completely up on list comprehensions. I want to like the sum() approach better, but it too is the kind of thing that makes me go 'oh, how clever', which is not necessarily a good idea in general code. All things considered, I'll probably use either the list comprehension approach or just the plain for loop one in future code.

PS: this is the kind of entry that I write in an attempt to make it all stick in my head. And in a demonstration that I repeat myself, the example I used in MultilevelListComps was for list flattening (although back in 2005 it appears that lists did not have .extend(), or at least it slipped my mind).

(I mined here and here for this information.)

Sidebar: the boring plain approach

The most verbose but straightforward approach is of course the classic for loop:

accum = []
for e in somelists:
    accum.extend(e)

Just as with the list comprehension version, this works with any sequence types or iterable types; it doesn't require lists. On advantage of this approach is that anyone (your future self included) can easily recognize what the code is doing.

Written on 13 July 2010.
« On (not) logging calculated statistics
Sun Support's habit of publicizing private bug reports »

Page tools: View Source, Add Comment.
Search:
Login: Password:
Atom Syndication: Recent Comments.

Last modified: Tue Jul 13 00:32:56 2010
This dinky wiki is brought to you by the Insane Hackers Guild, Python sub-branch.