Fast, recursion depth safe, list flattening for Python

I've been using Python at work a lot recently (yeah, I know, took me long enough) and finding it to be fantastically useful for all sorts of things.

Anyway, I found myself needing a mechanism for flattening nested container objects and a quick google search led me to a Right Foot In article on various flatten algorithms. Seeing as I needed something to work on containers that aren't tuples or lists and I'm not very good at leaving well enough alone, I went about trying to come up with my own method.

Here's what I've got so far:

def flatten_to_list(something):
    if not hasattr(something, '__iter__'):
        return [something]
    retlist = list(something)
    i = 0
    while i < len(retlist):
        while hasattr(retlist[i], '__iter__'):
            if not retlist[i]:
                retlist.pop(i)
                i -= 1
            else:
                retlist.insert(i, retlist[i].pop(0))
        i += 1
    return retlist

In at least one test case, my method appears to be faster than the best method in the Right Foot In article. I'm still wrestling with namespace issues relating to the use of timeit but I'll try to get some actual speed numbers and test cases up later.

UPDATE: I am an idiot. My code was faster because my test case exploited a degenerate case for the algorithm; the code below, which is much closer to the original at Right Foot In, is faster.

def flatten_to_list(something):
    if not hasattr(something, '__iter__'):
        return [something]
    retlist = list(something)
    i = 0
    while i < len(retlist):
        while hasattr(retlist[i], '__iter__'):
            if not retlist[i]:
                retlist.pop(i)
                i -= 1
            else:
                retlist[i:i + 1] = retlist[i]
        i += 1
    return retlist

Comments

1) That code isn't right -- unbalanced parens at least, and I don't see how it's supposed to work anyway (since "something" never changes, your "while hasattr(something...") loop will never end.

2) list.insert is O(n), and you call it O(n) times, so your flatten is O(n^2)... ouch

1) You're absolute right; there were two typos in the code and they have now been fixed

  1. The second version of the code should now be less than O(n^2).