Fair enumeration

A fair enumeration emits every required occurrence after finitely many computation steps. The inputs can be infinite; completeness does not mean waiting until they have all been exhausted. If two proper lazy lists alternate their next available entries, every occurrence reaches the output after finitely many swaps. In contrast, a nested list comprehension can remain forever in its first infinite inner list. Fairness concerns input occurrences, even when different occurrences happen to have equal values.

For an outer proper lazy list of inner proper lazy lists, introduce row $i$ in round $i$ and advance each active row once per round. Discard an active row when its terminating constructor is observed. Each round inspects finitely many rows, and the entry at row index $i$, within-row index $j$, is emitted in round $i+j$. Every earlier round has finite work, proving fair enumeration of all occurrences.

An implementation can keep a finite list of row remainders, append at most one newly introduced row, collect one head from every nonempty remainder, and retain their tails for the next round. It must not first combine all not-yet-introduced rows. In fact, foldr interleave [] ([1,2] : repeat []) can emit 1 and then block before 2; diagonal merging of lazy lists emits both. If infinitely many empty rows remain after the final output, detecting termination is impossible in general: the absence-detection obstruction for infinite lists prevents a universal promise of a terminating empty tail, while every required occurrence can still be emitted.