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

No universally correct sequential Haskell implementation has that guarantee for partial lists. Compare undefined paired with [v], and [v] paired with undefined, where the element type is arbitrary. A generic program cannot fabricate v; it must eventually inspect an input spine to obtain it. Whichever input it first demands can be chosen to be the undefined one, blocking access to the available element in the other input.

In particular, the implementation in part b can emit a defined prefix and then block when alternation reaches an undefined tail. Lazy evaluation postpones demands; it cannot recognize that a demanded computation will never finish. The result is the partial-list interleaving obstruction, not an objection to fairness under the proper-input hypothesis. Additional concurrent primitives would change the computational model.^[ref]