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 / f / Solution

Merge the rows with fairConcat, retaining explicit empty-input cases:

fairPair :: (a -> b -> c) -> [a] -> [b] -> [c]
fairPair _ [] _  = []
fairPair _ _  [] = []
fairPair f xs ys = fairConcat [[f x y | y <- ys] | x <- xs]

For nonempty proper lazy lists, the occurrence f (xs!!i) (ys!!j) belongs to row $i$, position $j$, so the proof in part d puts it in round $i+j$. This supplies every pair after finite work, even when both input lists are infinite. The guards also return [] for either empty factor without traversing infinitely many empty rows.