Solution

ID: 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/g/solution

For a finite outer list of proper lazy lists, use the fair binary product from part f:
cp :: [[a]] -> [[a]]
cp []       = [[]]
cp (xs:xss) = fairPair (:) xs (cp xss)
The empty family has one selection, the empty selection. For a nonempty finite family, each selection consists uniquely of one first-factor occurrence followed by a selection from the remaining factors. Induction on the number of factors, together with the fairness of fairPair, proves that every such selection is produced and no invalid selection is introduced. Infinite factors are allowed: in particular, the three-factor example is enumerated fairly. If any factor is empty, the finite-family computation returns the empty product.
The printed hypothesis also permits an infinite outer proper lazy list. No function can satisfy the full enumeration requirement for all such inputs. Take repeat [0,1]. Its mathematical Cartesian product contains every infinite binary sequence and is uncountable. If a result list enumerated these sequences as , the binary sequence with would differ from the -th listed sequence at position , contradicting completeness. This is an uncountability obstruction to enumerating infinite Cartesian products. The finite-outer qualification is a necessary repair to the specification, not a restriction imposed for convenience by the code.

New to topics? Read the docs here!