Using recursion with map in python

Question

I am trying to learn functional programming concepts. An exercise, Flatten a nested list using map/reduce. My code.

lists = [ 1 , 2 , [ 3 , 4, 5], 6, [7, 8, 9] ]
def flatten(lists):
      return map(lambda x: flatten(x) if isinstance(x,list) else x, lists)

print flatten(lists)

I get output same as input. What did i do wrong ? How recursion works with map() ?

Answer 1

You can't solve this problem with map(). The recursive calls return a list, so for a list in the input you replaced the result with another list. map() always has to produce the same number of elements in the output as it was given in the input, after all.

With reduce() you can append more elements to an existing list:

def flatten(lists):
    return reduce(lambda res, x: res + (flatten(x) if isinstance(x, list) else [x]), lists, [])

This starts with an empty list, and appends elements to that for each element in lists. If that element is a list itself, recursion is used.

This produces the expected output:

>>> def flatten(lists):
...     return reduce(lambda res, x: res + (flatten(x) if isinstance(x, list) else [x]), lists, [])
...
>>> lists = [ 1 , 2 , [ 3 , 4, 5], 6, [7, 8, 9] ]
>>> flatten(lists)
[1, 2, 3, 4, 5, 6, 7, 8, 9]

Answer 2

Here's a solution that uses both map and reduce:

def flatten(seq):
    return reduce(operator.add, map(
        lambda x: flatten(x) if isinstance(x,list) else [x],
        seq))

As Martijn said, map produces the same number of items out as it receives on its input, so the outer step needs to be the reduce call that produces a single output for all of the inputs. map can be used here instead to make all of the input consistent: i.e. a sequence of lists.

Answer 3

Alternate solution with just recursion:

lists = [ 1 , 2 , [ 3 , 4, 5], 6, [7, 8, 9] ]
def flatten(lists):
    return (flatten(lists[0]) + flatten(lists[1:]) if isinstance(lists[0],list) else [lists[0]]+flatten(lists[1:])) if len(lists)>0 else []

Answer 4

Since you are using map in your function it returns a list even when you call call the function in recursively.

So instead of using map or reduce which are not pythonic ways for flattening a nested list you can use a generator function:

>>> def flatten(lists):
...     for sub in lists:
...         if isinstance(sub,list):
...            for i in sub:
...                 yield i
...         else:
...            yield sub
... 
>>> 
>>> list(flatten(lists))
[1, 2, 3, 4, 5, 6, 7, 8, 9]

If you still want to sue map function you can use following approach:

>>> def flatten(lists,total=[]):
...       map(lambda x: total.extend(x) if isinstance(x,list) else total.append(x), lists)
...       return total
... 
>>> flatten(lists)
[1, 2, 3, 4, 5, 6, 7, 8, 9]