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

Use function extensionality: show $f(x)=g(x)$ for every value $x$ of the argument type. In lazy evaluation semantics, “every value” includes the bottom value and partial values. For list arguments, structural induction on lazy lists supplies the empty, bottom and cons cases, with continuity justifying passage to infinite lists.

The original printed equation has the same right fold on both sides, including the same operator and seed; this is visible in the scan.^[ref] Thus its literal answer isFor every input $xs$, both sides denote the very same expression foldr (oplus) e xs; equality follows by reflexivity. This remains true if its value is $\perp$. Neither termination nor associativity nor an identity law is required. The scan does not establish a different intended equation, so no replacement by a left fold is assumed.