= Diagonal merging of lazy lists
{title2=$\text{round}(i,j)=i+j$}
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.
Back to article page
