3 ms·
Iteration Inside and Out
- btilly 14y agoIf 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 14y agoor, 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()
- btilly 14y agoVery nice. That would solve the basic inefficiency.
- munificent 14y agoExactly 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.
- btilly 14y agoOf 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.