[Python-Dev] Re: Graph exploration with generators

David Abrahams dave at boost-consulting.com
Thu Aug 21 19:35:21 EDT 2003

```"Shane Holloway (IEEE)" <shane.holloway at ieee.org> writes:

> Well, I've been holding this generators idea for after the Python 2.3
> release since it would be a Python 2. or later feature.  That and I
> didn't want to delay the release by even a the time to read an email.
> ;)
>
> Over the last few months, I've been using generators more and more to
> do lazy graph exploration.  As a concrete example, take the following
> binary tree type structure:
>
>      class Tree(object):
>          def __init__(self, left=(), right=()):
>              self.left = left
>              self.right = right
>
>          def __iter__(self):
>              for each in self.left:
>                  yield each
>              yield self
>              for each in self.right:
>                  yield each
>
> This works great for iterating over ad-hoc graphs, and since "left"
> and "right" simply have to be iterable, you can chain trees to graphs,
> lists, or anything iterable.  However, for each "chained" generator
> quite a bit of speed is lost.  I assume this loss is due to restoring
> each context in the chain.  (I would need help verifying this
> assumption.)
> What I would like to propose is a "yield *" type statement, where
> "yield *collection" would have the equivalent functionality of "for
> item in collection: yield item".  The above example would then appear
> as follows:

I wonder if this is improves the speed and is expressive enough:

class YieldSeq(object):
__slots__ = [ 'outer', 'inner' ]

def __init__(self, *seq):
self.outer = iter(seq)

def __iter__(self):
return self

def next(self):
while 1:
try:
return self.inner.next()
except StopIteration:
self.inner = iter(self.outer.next())

class Tree(object):
def __init__(self, name, left=(), right=()):
self.name = name
self.left = left
self.right = right

def __iter__(self):
return YieldSeq(self.left, (self,), self.right)

def __repr__(self):
return self.name

t = Tree('a',
Tree('b',
Tree('c'),
Tree('d')),
Tree('e',
Tree('f'),
Tree('g')
)
)

print [ c for c in t ]

Of course I realize it's not as beautiful as using generators...

--
Dave Abrahams
Boost Consulting
www.boost-consulting.com

```