flattenProblem.py

import collections

def _flatten(L, M, i):
    if i == len(L):
        return
    if isinstance(L[i], collections.Iterable):
        _flatten(L[i], M, 0)
    else:
        M.append(L[i])
    _flatten(L, M, i+1)

# recursive
def flatten(L):
    M = []
    _flatten(L, M, 0)
    return M

# iterative
def flatten(L):
    M = []
    Q = [iter(L)]
    while Q:
        L = Q[-1]
        for x in L:
            if isinstance(x, collections.Iterable):
                Q.append(iter(x))
                break
            M.append(x)
        else:
            Q.pop()

    return M

if __name__=="__main__":
    assert(flatten([])==[])
    assert(flatten([[]])==[])
    assert(flatten([0])==[0])
    assert(flatten([0,[1]])==[0,1])
    assert(flatten([0,[1],2])==[0,1,2])
    L=[0,1,[2,3],4,[5]]
    import copy
    M=copy.deepcopy(L)
    assert(flatten(L)==[0,1,2,3,4,5])
    assert(L==M) # input unchanged?