[Python-Dev] itertools.walk()

[Nick Coghlan]

Bob Ippolito wrote:
> I'm not sure why it's useful to explode the stack with all that 
> recursion?  Mine didn't do that.  The control flow is nearly identical, 
> but it looks more fragile (and you would get some really evil stack 
> trace if iter_factory(foo) happened to raise something other than 
> TypeError).

It was a holdover from my first version which *was* recursive. When I switched 
to using your chaining style, I didn't think to get rid of the now unneeded 
recursion.

So just drop the recursive calls to 'walk', and it should be back to your structure.

For the 'infinite recursion on basestring' example, PJE at one point suggested a 
"if item is iterable" guard that immediately yielded the item. Allowing breadth 
first operation requires something a little different, though:

from itertools import chain

def walk(iterable, depth_first=True, atomic_types=(basestring,), iter_factory=iter):
   itr = iter(iterable)
   while True:
     for item in itr:
       if isinstance(item, atomic_types):
         yield item
         continue
       try:
         subitr = iter_factory(item)
       except TypeError:
         yield item
         continue
       # Block simple cycles (like characters)
       try:
         subitem = subitr.next()
       except StopIteration:
         continue
       if subitem is item:
         yield subitem
         continue
       if depth_first:
         itr = chain([subitem], subitr, itr)
       else:
         itr = chain(itr, [subitem], subitr)
       break
     else:
       break

Py> seq
[['123', '456'], 'abc', 'abc', 'abc', 'abc', ['xyz']]
Py> list(walk(seq))
['123', '456', 'abc', 'abc', 'abc', 'abc', 'xyz']
Py> list(walk(seq, depth_first=False))
['abc', 'abc', 'abc', 'abc', '123', '456', 'xyz']
Py> list(walk(seq, atomic_types=()))
['1', '2', '3', '4', '5', '6', 'a', 'b', 'c', 'a', 'b', 'c', 'a', 'b', 'c', 'a',
  'b', 'c', 'x', 'y', 'z']
Py> list(walk(seq, depth_first=False, atomic_types=()))
['a', 'b', 'c', 'a', 'b', 'c', 'a', 'b', 'c', 'a', 'b', 'c', '1', '2', '3', '4',
  '5', '6', 'x', 'y', 'z']

Raymond may simply decide to keep things simple instead, of course.

Cheers,
Nick.

-- 
Nick Coghlan   |   ncoghlan at email.com   |   Brisbane, Australia
---------------------------------------------------------------
             http://boredomandlaziness.skystorm.net