python list comprehensions; compressing a list of lists?
Functional ProgrammingPythonList ComprehensionFunctional Programming Problem Overview
guys. I'm trying to find the most elegant solution to a problem and wondered if python has anything built-in for what I'm trying to do.
What I'm doing is this. I have a list, A
, and I have a function f
which takes an item and returns a list. I can use a list comprehension to convert everything in A
like so;
[f(a) for a in A]
But this return a list of lists;
[a1,a2,a3] => [[b11,b12],[b21,b22],[b31,b32]]
What I really want is to get the flattened list;
[b11,b12,b21,b22,b31,b32]
Now, other languages have it; it's traditionally called flatmap
in functional programming languages, and .Net calls it SelectMany
. Does python have anything similar? Is there a neat way to map a function over a list and flatten the result?
The actual problem I'm trying to solve is this; starting with a list of directories, find all the subdirectories. so;
import os
dirs = ["c:\\usr", "c:\\temp"]
subs = [os.listdir(d) for d in dirs]
print subs
currentliy gives me a list-of-lists, but I really want a list.
Functional Programming Solutions
Solution 1 - Functional Programming
You can have nested iterations in a single list comprehension:
[filename for path in dirs for filename in os.listdir(path)]
which is equivalent (at least functionally) to:
filenames = []
for path in dirs:
for filename in os.listdir(path):
filenames.append(filename)
Solution 2 - Functional Programming
>>> from functools import reduce # not needed on Python 2
>>> list_of_lists = [[1, 2],[3, 4, 5], [6]]
>>> reduce(list.__add__, list_of_lists)
[1, 2, 3, 4, 5, 6]
The itertools
solution is more efficient, but this feels very pythonic.
Solution 3 - Functional Programming
You can find a good answer in the itertools
recipes:
import itertools
def flatten(list_of_lists):
return list(itertools.chain.from_iterable(list_of_lists))
Solution 4 - Functional Programming
The question proposed flatmap
. Some implementations are proposed but they may unnecessary creating intermediate lists. Here is one implementation that's based on iterators.
def flatmap(func, *iterable):
return itertools.chain.from_iterable(map(func, *iterable))
In [148]: list(flatmap(os.listdir, ['c:/mfg','c:/Intel']))
Out[148]: ['SPEC.pdf', 'W7ADD64EN006.cdr', 'W7ADD64EN006.pdf', 'ExtremeGraphics', 'Logs']
In Python 2.x, use itertools.map
in place of map
.
Solution 5 - Functional Programming
You could just do the straightforward:
subs = []
for d in dirs:
subs.extend(os.listdir(d))
Solution 6 - Functional Programming
You can concatenate lists using the normal addition operator:
>>> [1, 2] + [3, 4]
[1, 2, 3, 4]
The built-in function sum
will add the numbers in a sequence and can optionally start from a specific value:
>>> sum(xrange(10), 100)
145
Combine the above to flatten a list of lists:
>>> sum([[1, 2], [3, 4]], [])
[1, 2, 3, 4]
You can now define your flatmap
:
>>> def flatmap(f, seq):
... return sum([f(s) for s in seq], [])
...
>>> flatmap(range, [1,2,3])
[0, 0, 1, 0, 1, 2]
Edit: I just saw the critique in the comments for another answer and I guess it is correct that Python will needlessly build and garbage collect lots of smaller lists with this solution. So the best thing that can be said about it is that it is very simple and concise if you're used to functional programming :-)
Solution 7 - Functional Programming
import itertools
x=[['b11','b12'],['b21','b22'],['b31']]
y=list(itertools.chain(*x))
print y
itertools will work from python2.3 and greater
Solution 8 - Functional Programming
subs = []
map(subs.extend, (os.listdir(d) for d in dirs))
(but Ants's answer is better; +1 for him)
Solution 9 - Functional Programming
You could try itertools.chain()
, like this:
import itertools
import os
dirs = ["c:\\usr", "c:\\temp"]
subs = list(itertools.chain(*[os.listdir(d) for d in dirs]))
print subs
itertools.chain()
returns an iterator, hence the passing to list()
.
Solution 10 - Functional Programming
This is the most simple way to do it:
def flatMap(array):
return reduce(lambda a,b: a+b, array)
The 'a+b' refers to concatenation of two lists
Solution 11 - Functional Programming
Google brought me next solution:
def flatten(l):
if isinstance(l,list):
return sum(map(flatten,l))
else:
return l
Solution 12 - Functional Programming
def flat_list(arr):
send_back = []
for i in arr:
if type(i) == list:
send_back += flat_list(i)
else:
send_back.append(i)
return send_back
Solution 13 - Functional Programming
You can use pyxtension:
from pyxtension.streams import stream
stream([ [1,2,3], [4,5], [], [6] ]).flatMap() == range(7)
Solution 14 - Functional Programming
If listA=[list1,list2,list3]
flattened_list=reduce(lambda x,y:x+y,listA)
This will do.