List Flatten

[Peter Otten]

bearophile wrote:

> def listflatten(l):
> """Flattens a list, examples:
> listflatten("a") => "a"
> listflatten([]) => []
> listflatten([[1,[2,[],"a"]]) => [1,2,"a"]
> """
> if type(l) != list:
> return l
> else:
> result = []
> stack = []
> stack.append((l,0))
> while len(stack) != 0:
> sequence, j = stack.pop(-1)
> while j < len(sequence):
> if type(sequence[j]) != list:
> k, j, lens = j, j+1, len(sequence)
> while j < len(sequence) and \
> (type(sequence[j]) != list):
> j += 1
> result.extend(sequence[k:j])
> else:
> stack.append((sequence, j+1))
> sequence, j = sequence[j], 0
> return result
 
I see my newsreader has a different notion about what flatten is meant to
be :-)

Have you considered generators?

def flatten(items):
    if not isinstance(items, list):
        yield items
    stack = [iter(items)]
    while stack:
        for item in stack[-1]:
            if isinstance(item, list):
                stack.append(iter(item))
                break
            yield item
        else:
            stack.pop()

assert list(flatten([[[[]]], 0, 1, [[[2,[3, [4]]]], [],[5, 6], 7, [8, 9]],
10])) == range(11)

I have not timed it, I just prefer the generator for its clarity (provided
it is correct, I haven't tested it either). This is achieved mostly by
hiding the indices together with the underlying list in iterator objects.
Generators may also save you a lot of memory for very large data structures
as you can iterate over a flat _view_ of your nested lists without ever
having to _create_ the large flat list.

Peter