Diagonal merging of lazy lists 2026-10-24
View more
For an outer proper lazy list of inner proper lazy lists, introduce row in round 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 , within-row index , is emitted in round . 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.
Read the full article
Past exam of the year 1 of the computer science course of the University of Oxford / 2005 / Functional programming, data structures and algorithms, procedural programming, and digital hardware / 3 / e / Solution 2026-10-31
View more
For two proper lazy lists, twiddle alternates heads, swapping which list is served after each output. Thus both input positions have finite waiting time. A tempting extension is remalldups . foldr twiddle [], but arbitrary empty rows make that insufficient: for [ [1,2] ] ++ repeat [], it emits 1 and then demands the combination of infinitely many empty rows before it can return to 2.
Use diagonal merging of lazy lists to avoid that obstruction. Maintain a finite active collection, add at most one new row per round, and take one head from every nonempty active row. The supplied twiddle combines those singleton contributions into a finite batch:
union' = remalldups . rounds []

rounds [] [] = []
rounds active [] = emit active []
rounds active (row:rows) = emit (active ++ [row]) rows

emit active rows = batch ++ rounds tails rows
  where (batch, tails) = sweep active

sweep [] = ([], [])
sweep ([]:rows) = sweep rows
sweep ((x:xs):rows) = (twiddle [x] heads, xs:tails)
  where (heads, tails) = sweep rows
Here rounds takes the finite active collection first and the not-yet-introduced outer list second. Because heads is a finite list, twiddle [x] heads emits x followed by those heads; the finite batch is then completely consumed before the next round. Empty exhausted rows are removed by sweep. No step tries to combine infinitely many not-yet-introduced rows.
Index rows and positions from zero. Row is introduced in round and contributes its element in round , if that element exists. Every earlier round inspects only finitely many rows. Therefore every occurrence has a finite emission time, proving fair enumeration. Applying first-occurrence duplicate removal gives
(1)
All outer and inner spines must be proper lazy lists and equality tests must terminate. Infinitely many empty rows after the final contribution still prevent certifying a terminating empty tail, just as part (c) predicts. Undefined input spines have the separate partial-list interleaving obstruction; the construction makes no promise to bypass them.
Read the full article
Past exam of the year 1 of the computer science course of the University of Oxford / 2019 / Functional programming, design and analysis of algorithms / 4 / d / Solution 2026-10-25
View more
Use diagonal merging of lazy lists: introduce one new row each round, and advance every active row once. Each round contains finitely many active rows, even when the outer list is infinite.
fairConcat :: [[a]] -> [a]
fairConcat = concat . levels []
  where
    levels [] [] = []
    levels active pending =
      let (new,rest) = case pending of
            []     -> ([],[])
            r:rs   -> ([r],rs)
          live = [r | r@(_:_) <- active ++ new]
      in map head live : levels (map tail live) rest
Number rows and positions within each row from zero. An occurrence at is emitted in round : its row enters in round and advances once per subsequent round. All earlier rounds and each round's output are finite, so every required occurrence appears after finite work. live discards only empty rows, and head emits only existing entries; no new value is invented.
Figure 1.
Diagonal merging of lazy lists visits every finite row-position pair after finitely many rounds
. Details.
Simply nesting interleave is unsafe here: foldr interleave [] ([1,2] : repeat []) emits 1 and then demands an undefined merge of the infinitely many empty rows before it can emit 2. The finite-round construction avoids that starvation. There is still an unavoidable termination qualification: after the last actual output, infinitely many empty pending rows cannot be certified empty in finite work. The result can then have an undefined tail instead of a terminating []. Every required occurrence has nevertheless appeared; no generic algorithm can promise a proper completed output in that exceptional situation, by the absence-detection obstruction for infinite lists.
Read the full article