How do I flatten a python list? Inputs are lists, strings or integers

Question

Below is my code to flatten a python list. I've tried to use the concept of recursion to do the same. The inputs are either of integers, strings or lists. What I'm struggling with is I'm unable to follow as to why is my return giving me a list with repeated values? How do I rectify the same?

copyList = []
def flatten(aList):
    for char in aList:
        if isinstance(char,int) or isinstance(char,str):
            copyList.append(char)
        else:
            char_pos = aList.index(char) + 1
            return  flatten(char) + flatten(aList[char_pos:len(aList)]) 
    print copyList
    return copyList

My output is correct in terms of getting the right output but the return seems to be giving me the list repeated several times. Unable to understand what went wrong!!

Sample output here: flatten([1,'a',2,[['alpha']],3,4])

[1, 'a', 2, 'alpha'] [1, 'a', 2, 'alpha'] [1, 'a', 2, 'alpha', 3, 4]

Out[2]: [1, 'a', 2, 'alpha', 1, 'a', 2, 'alpha', 1, 'a', 2, 'alpha', 3, 4]

score 2 · Answer 1 · answered Jul 12 '16 at 14:24

def flatten_list(a, result=None):
    """ Flattens a nested list. """
    if result is None:
        result = []

    for x in a:
        if isinstance(x, list):
            flatten_list(x, result)
        else:
            result.append(x)
    return result

print flatten_list([1,'a',2,[['alpha']],3,4])

score 1 · Accepted Answer · answered Jul 12 '16 at 14:29

1

You implemented the recursion incorrectly. You must initialize the copyList inside the function, then append to it inside the else clause:

def flatten(aList):
    copyList = []
    for char in aList:
        if isinstance(char,int) or isinstance(char,str):
            copyList.append(char)
        else:
            char_pos = aList.index(char) + 1
            return copyList + flatten(char) + flatten(aList[char_pos:len(aList)]) 
    return copyList

answered Jul 12 '16 at 14:29

Selcuk

57,004
12
102
110

Thanks a lot for the edit. The code works fine now. One question though, I tried a lot by putting print statements in the program but couldn't wrap my head around why m recursion implementation is incorrect when I initialize copyList outside the function and didn't add copyList in my return. Could you explain that intuitively? – Pradyut Vatsa Jul 12 '16 at 17:42
@PradyutVatsa Basically by initializing the return value outside the function you make it a global variable. Then you keep appending already processed elements to it over and over in each recursion. – Selcuk Jul 13 '16 at 03:05
@Selchuk While intuitively I know this, can't wrap my head around. I tried breaking down my original code to understand this. Step I: When I call flatten([1,'a',2,[['alpha']],3,4], the if statement is executed till 2 is encountered and copyList is initialized to [1,'a',2]. Then as it encounters [['alpha']], it goes to the else loop, and returns flatten([['alpha']] + flatten([3,4]). flatten([['alpha']]) evaluates to returning flatten(['alpha']) + flatten([]) which appends 'alpha' to copyList and flatten([]) does nothing. – Pradyut Vatsa Jul 14 '16 at 18:45
Now my copyList is [1,'a',2,'alpha'] and we evaluate flatten([3,4] which returns me a value of [1,'a',2,'alpha',3,4]. Now coming back to the environment of the first return call, I get the answer for return as [1,'a',2,'alpha'] + [1,'a',2,'alpha',3,4] which should give me an output of [1,'a',2,'alpha',1,'a',2,'álpha',3,4] which isn't the output generated. So, in practice what went wrong is still unclear to me. – Pradyut Vatsa Jul 14 '16 at 18:46
Above is based on my incorrect version of the code – Pradyut Vatsa Jul 14 '16 at 18:47

score 0 · Answer 3 · answered Jul 12 '16 at 16:38

Without manually messing about with lists:

def iflatten(seq):
    for item in seq:
        if isinstance(item, list):
            for subitem in iflatten(item):
                yield subitem
        else:
            yield item

def flatten(seq):
    return list(iflatten(seq))

Like the other solutions on the page at the moment of writing, it only handles non-cyclic lists.

Edit: the print statement clued me in that OP is using Python 2, so I replaced the yield from expression by a nested for-loop.

How do I flatten a python list? Inputs are lists, strings or integers

3 Answers3