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

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 $(i,j)$ is emitted in round $i+j$: its row enters in round $i$ 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.

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.