[Python-Dev] itertools.walk()

Bob Ippolito bob at redivi.com
Wed Mar 16 13:22:51 CET 2005


On Mar 16, 2005, at 6:19, Raymond Hettinger wrote:

> Some folks on comp.lang.python have been pushing for itertools to
> include a flatten() operation.  Unless you guys have some thoughts on
> the subject, I'm inclined to accept the request.
>
> Rather than calling it flatten(), it would be called "walk" and provide
> a generalized capability to descend through nested iterables (similar 
> to
> what os.walk does for directories).  The one wrinkle is having a
> stoplist argument to specify types that should be considered atomic
> eventhough they might be iterable (strings for example).

You could alternatively give them a way to supply their own "iter" 
function, like the code I demonstrate below:

from itertools import chain

def nostring_iter(obj):
     if isinstance(obj, basestring):
         raise TypeError
     return iter(obj)

def uniqueiter_factory(iterfunc=nostring_iter):
     def uniqueiter(obj, uniques={}):
         iterable = iterfunc(obj)
         if id(obj) in uniques:
             raise TypeError
         uniques[id(obj)] = obj
         return iterable
     return uniqueiter

# maybe there should be a bfswalk too?
def walk(iterable, iterfunc=nostring_iter):
     iterables = iter((iterable,))
     while True:
         for obj in iterables:
             try:
                 iterable = iterfunc(obj)
             except TypeError:
                 yield obj
             else:
                 iterables = chain(iterable, iterables)
                 break
         else:
             break

 >>> data = [('foo', 'bar'), 'baz', 5]
 >>> list(walk(data))
['foo', 'bar', 'baz', 5]
 >>> list(walk(data, uniqueiter_factory(iter)))
['f', 'o', 'o', 'b', 'a', 'r', 'b', 'a', 'z', 5]
 >>> data.append(data)
 >>> list(walk(data, uniqueiter_factory()))
['foo', 'bar', 'baz', 5, [('foo', 'bar'), 'baz', 5, [...]]]

-bob



More information about the Python-Dev mailing list