# 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
2. The second version of the code should now be less than O(n^2).

Having the benefit of time, I'm not terribly fond of any of my prior solutions, these days I'd probably start with a deque and eat things off the left side. A bit like:

```import collections

def flatten_to_list(something):
retlist = []
queue = collections.deque([something])
while queue:
item = queue.popleft()
while hasattr(item, '__iter__'):
item, *rest = item
queue.extendleft(reversed(rest))
retlist.append(item)
return retlist
```

Even so, the part that I'm most unhappy about is that this doesn't play well with strings but that's mostly because strings support __iter__ and always behave funny in this kind of situation.

There are probably better approaches and one could always consider a generator but so it goes.