Walking deeply nested lists

[Carl Banks]

On Aug 27, 8:21 pm, donn <donn.in... at gmail.com> wrote:

> Each Tag has a flatwalk() method. The return from that is a list which
> can be deeply nested. As an example, something like this:
> L=[1, [2, 3, [4, [5, 6], 7], 8], [9, 10] ]
>
> (The numbers in the example would actually be Tag Instances.)
>
> Aim 1
> ---
> I'm trying to write a generator around such lists so that I can 'walk' them:
>
> for parent, child in mystery_generator(L):
>   print level, item
>
> Right now, I am running a 'flatten' function on the entire list (which I
> don't savvy, I found it online) and then I iterate over that flattened
> list. This doesn't feel right to me. (Code at end.)


Hmm.

In the past I've argued that iterative techniques are superior to
recursive approaches in terms of readability, understandability, and
conciseness, and thus Python made the right decision to stress
iteration over the Lisp/functional preference for recursion.

I did consider recursion to be superior to operate on branched
structures like trees.  However, lately I've started thinking it's
better to use iterative techniques even for situations like that.  I
say that as someone with no problem getting my head around recursion.

Even if you disagree, I think there's value in learning iterative
approaches to nested problems, in the same way that there's value to
learning recursive approaches to linear problems.  So here it is:


def flatten_iter(s):
    stack = list()
    stack.extend(reversed(s))
    while stack:
        item = stack.pop()
        if isinstance(item,list):
            stack.extend(reversed(item))
        else:
            yield item


It's simple. Copy the object to flatten onto your stack. Pop one item
off the stack. If the item you popped is a list, push each item of
that list onto the stack. Otherwise yield the value. Loop until stack
is empty.

There's many advantages to iterative approaches:
1. Less function call overhead (in time and space, I'd think)
2. Opportunity to optimize by scanning through the stack, something
you can't do *at all* with recursion
3. Might be able to avoid things like passing around a namespace
4. Iteration is more readable, understandable, and concise in
general (though I'd expect recursion is more refactorable than
iteration so as the system grows the refactorability of recursion will
start to outweigh other factors)

The main advantage of recursion is if you have baggage associated with
processing a node which does needed to be passed around.  In the
iterative approach that state has to be stored on the stack.  So in
those cases recursion is better.

So I'm not suggesting that recursion be avoided (I've probably written
a dozen recursive functions in the last week), I'm just saying
sometimes it makes sense to use iteration even for problems recursion
is tailor-made for.


Carl Banks