6

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() ?

s007
  • 728
  • 6
  • 12

4 Answers4

8

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.

Duncan
  • 92,073
  • 11
  • 122
  • 156
5

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]
Martijn Pieters
  • 1,048,767
  • 296
  • 4,058
  • 3,343
1

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]
Mazdak
  • 105,000
  • 18
  • 159
  • 188
  • 3
    But the *exercise* was to use `map()` and `reduce()`. Yup, using a generator makes this easy enough, but *that's not what the OP is learning*. – Martijn Pieters Nov 24 '15 at 08:24
  • @MartijnPieters You are right about learning. ButI just said that it's not pythonic, and demonstrate the correct way.Any way I updated the answer with a `map` based approach. – Mazdak Nov 24 '15 at 08:32
  • 1
    @Kasramvd Isn't passing total=[] as parameter against function programming principle ? As it makes it mutable. – s007 Nov 24 '15 at 08:42
  • @s007 List objects are mutable in python. – Mazdak Nov 24 '15 at 09:09
  • 2
    Yes, but that's at best a comment, with a link to the canonical post on the subject: [Flatten (an irregular) list of lists in Python](http://stackoverflow.com/q/2158395) – Martijn Pieters Nov 24 '15 at 09:14
0

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 []
Akshay Hazari
  • 3,186
  • 4
  • 48
  • 84
  • Well I would have posted a reduce answer that is what directly comes to mind when flattening a list . This was because reduce was already posted as an answer. – Akshay Hazari Nov 24 '15 at 09:22