Iteration Inside and Out

http://journal.stuffwithstuff.com/2013/01/13/iteration-inside-and-out/

by munificent • 14 years ago

7 5 14 years ago

journal.stuffwithstuff.com

btilly3• 14 years ago

If you've got iterators and a yield statement, like Python does, you can make the tree example look much nicer:

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

Unfortunately this is horribly inefficient if the tree has deep nodes because each iterator call recursively calls each level of the tree, only do just pass values back. If there was something like tail call optimization for iterators in Python, then this could actually be efficient. But there is not.

However it does show that, at least in principle, the external form of iteration can make the tree problem look pretty.

(Purists can claim with justice that that I'm cheating. The yield primitive allows co-routines to be constructed, which allows you to effectively flip internal and external. That is why it was one of the solutions to allow internal iterators to solve the interleaving problem.)

mwhite• 14 years ago

or, in Python 3.3:

    def in_order(self):
        if self.left is not None:
            yield from self.left.in_order()
        yield self.node
        if self.right is not None:
            yield from self.right.in_order()

btilly3• 14 years ago

Very nice. That would solve the basic inefficiency.

munificent• 14 years ago

Exactly right. Part two will be about generators like this, as well as coroutines and fibers. Simple generators don't really let you flip internal and external iteration, they just give you a nice way to reify a single stack frame. Coroutines and fibers are even more awesome because they let you reify an entire callstack.

btilly3• 14 years ago

Of course the downside of that kind of power is that it makes it very hard to reason about what code will do sometimes. As I once heard about continuations, it is a like a goroutine, only worse.

Iteration Inside and Out

Related Stories