A Problem with Python's 'yield'

[Eric Kidd <address@hidden>]

I'm going to pick on Python here, but only because the example code will
be short and sweet. :-) I believe several other implementations of
generators have the same problem.

Python's generator system, used naively, turns an O(N) tree traversal
into an O(N log N) tree traversal:

  class Tree:
      def __init__(self, value, left=None, right=None):
          self.value = value
          self.left = left
          self.right = right

      def in_order(self):
          if self.left is not None:
              for v in self.left.in_order():
                  yield v
          yield self.value
          if self.right is not None:
              for v in self.right.in_order():
                  yield v

  t=Tree(2, Tree(1), Tree(3))
  for v in yield_bug.t.in_order():
      print v

This prints:
  1
  2
  3
  
Unfortunately, this snippet calls 'yield' 5 times, because the leaf
values must be yielded twice on their way back up the tree.

We can shorten the code--and make it run in O(N) time--by adding a new
keyword to replace the "for v in ...: yield v" pattern:

  def in_order(self):
      if self.left is not None:
          yield_all self.left.in_order():
      yield self.value
      if self.right is not None:
          yield_all self.right.in_order():

Interestingly enough, this allows you define notions such as
"tail-recursive generation", and apply the usual bag of
recursion-optimization techniques.

Cheers,
Eric