One mostly-readable (and presumably performant, though I haven't tested it) way to iteratively flatten a list:
from collections import deque
def iterative_flatten(li):
nested = deque(li)
res = []
dq = deque()
while nested or dq:
x = dq.pop() if dq else nested.popleft()
dq.extend(reversed(x)) if isinstance(x, list) else res.append(x)
return res
Uses deques to avoid nasty O(n**2) behavior from list.pop(0)
. You can get equivalent results by making a reversed copy and popping from the end, but I find the code a little easier to follow if you just use deques and popleft
. On a similar note, it's a line or two less code if you want to mutate the list in-place but way slower (for the same reason; pop
ping from the head of the list is O(n) since every element in the underlying array has to be shifted).
nested = [1,[[2,3],[[4,5],[6]]],[[[[7]]]]]
iterative_flatten(nested)
Out[116]: [1, 2, 3, 4, 5, 6, 7]
sum(iterative_flatten(nested))
Out[117]: 28
After it's flat, summing is (hopefully) trivial :-)