[Python-Dev] Re: Graph exploration with generators

[David Abrahams]

"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)
           self.inner = iter(()) # start with something empty

       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