Iterator design: flatten, peek, interleave

A flatten nested list iterator hands out the items of a list whose elements are items or further lists, one item per call, in reading order, without building a flat copy first. Two methods make up the class: next() returns the next item and has_next() says whether one remains. Two related designs come with it. Peek shows the next item without taking it, and interleave takes items from several iterators in turn. All three keep a little state between calls instead of doing the work up front.

The problem: a menu of nested sections

The menu [[101, [102]], [], [[[]]], 103, [[104, 105]]] gives 101, 102, 103, 104 and 105, after which has_next() returns False. The empty sections hold nothing, but the iterator still has to step through them. The menu [[], [[]]] gives no item at all: its first has_next() already returns False.

The brute force: copy every item first

The obvious design copies every item into a flat list in the constructor, recursing into each section, and then hands the items out with an index. Its answers are right, and it fails the limits in two ways:

"""The first design that comes to mind: copy every item into a flat list in the constructor, then hand them out with
an index. The answers are right; this program shows the two ways it fails at the stated sizes.
"""


class CopyFirstIterator:
    def __init__(self, menu):
        self.items = []
        self.visited = 0  # elements the constructor looked at before next() could answer anything
        self._copy(menu)
        self.i = 0

    def _copy(self, section):
        for x in section:
            self.visited += 1
            if isinstance(x, list):
                self._copy(x)  # one Python frame per level of nesting
            else:
                self.items.append(x)

    def has_next(self):
        return self.i < len(self.items)

    def next(self):
        self.i += 1
        return self.items[self.i - 1]


def nested(depth, item):
    """[[[...[item]...]]], `depth` lists deep."""
    menu = [item]
    for _ in range(depth - 1):
        menu = [menu]
    return menu


it = CopyFirstIterator([[101, [102]], [], [[[]]], 103, [[104, 105]]])
out = []
while it.has_next():
    out.append(it.next())
print("example:", out)

# 1. Nesting: the copy recurses once per level, and CPython stops at its recursion limit of 1,000 frames.
for depth in (500, 990, 1_000, 5_000):
    try:
        it = CopyFirstIterator(nested(depth, 7))
        print(f"depth {depth:,}: first item {it.next()}")
    except RecursionError as e:
        print(f"depth {depth:,}: RecursionError: {e}")

# 2. Work before the first answer: 100,000 items, each after an empty section, and a caller who reads 3 items.
menu = []
for k in range(100_000):
    menu += [[], 1000 + k]
it = CopyFirstIterator(menu)
first = [it.next() for _ in range(3)]
print(f"200,000 elements, 3 items read {first}: the copy looked at {it.visited:,} elements "
      f"and stored {len(it.items):,} items first")

example: [101, 102, 103, 104, 105]
depth 500: first item 7
depth 990: first item 7
depth 1,000: RecursionError: maximum recursion depth exceeded
depth 5,000: RecursionError: maximum recursion depth exceeded
200,000 elements, 3 items read [1000, 1001, 1002]: the copy looked at 200,000 elements and stored 100,000 items first

The copy recurses once per level, and CPython stops it at depth 1,000, its default recursion limit, far short of 5,000. Even without recursion, it looks at all 200,000 elements and stores 100,000 items before it can answer the first next(), for a caller who wanted three.

What to notice

An iterator only needs to remember where it is: in each open section, the position of the next element. That is a stack with one entry per level, so memory grows with the depth, not with the menu. Four designs follow:

• A stack of positions keeps one entry per open section and settles the next item only when asked.
• A recursive generator with yield from is short and lazy, but it nests one call per level.
• A peeking wrapper caches one item, so that peek() can show it without taking it.
• Round-robin interleaving keeps a queue of iterators and takes one item from the front iterator per call.

A stack of positions, step by step Pro: opens with a Pro, Premium or Ultimate pass