CODEWITHSUNDEEP
pythonpython-2.7
sid597
sid597

Reputation: 1019

Flatten an irregular list of lists in Python recursively

I searched and found question with same heading is also (here here here here here) but I am not asking that. I came across the problem:

To write a function to flatten a list. The list contains other lists, strings, or ints.

And my code for the same is

t=[]
def flatten(aList):
    for i in aList:
        if type(i) !=list:
             t.append(i)
        else:
             flatten(i)

    return t

But when I check the code for test cases:

  1. flatten([[1], [1]]) : The checker tells me the output is[1, 1, 1, 1] but in codeskulptor I get the correct output which is [1, 1] .
  2. flatten([[[1]], [[[5]]]]): The checker tells the output is [1, 1, 1, 1, 1, 2, 3, 3, 2, 1, 0, 4, 5, 6, 7, 1, 5] but in codeskulptor tells [1, 5].

This problem exists with many test cases. Then I checked my code in python tutor and found out that after the if statement is executed each time the list t is returned and at-last when the function comes to halt it returns the last edited list t.

How can I resolve this issue please help me with this and yes I am new to python and do not know anything about itertools, lambda function usage, generators etc. so please tell me in the context in which I can understand.

Upvotes: 1

Views: 6740

Answers (1)

Martijn Pieters
Martijn Pieters

Reputation: 1122242

Your code is relying on a global; if the checker calls your function twice, it'll receive a longer list than expected:

>>> t = []
>>> def flatten(aList):
...     for i in aList:
...         if type(i) !=list:
...              t.append(i)
...         else:
...              flatten(i)
...     return t
...
>>> flatten([1, 1])
[1, 1]
>>> flatten([1, 1])
[1, 1, 1, 1]
>>> t  # your global, still holding all those values:
[1, 1, 1, 1]

Don't use globals. Use a local list, and and extend it with the result of recursive calls:

def flatten(aList):
    t = []
    for i in aList:
        if not isinstance(i, list):
             t.append(i)
        else:
             t.extend(flatten(i))
    return t

Note that I switched to using isinstance() to test for the type. This version doesn't suffer from shared state leaking into the next call:

>>> def flatten(aList):
...     t = []
...     for i in aList:
...         if not isinstance(i, list):
...              t.append(i)
...         else:
...              t.extend(flatten(i))
...     return t
...
>>> flatten([1, 1])
[1, 1]
>>> flatten([1, 1])
[1, 1]
>>> flatten([[[1]], [[[5]]]])
[1, 5]
>>> flatten([1, 1, [42, 81]])
[1, 1, 42, 81]

Upvotes: 6

Related Questions