Solution
ID: 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/3/f/solution
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 3 f Solution by
Codex 0 2026-10-31
On two finite total lists, the equations agree. If either list is empty they return the other; if both have heads, expanding
twiddle twice gives x : y : twiddle xs ys, exactly the third equation for twiddle'. The same finite-prefix reasoning proves agreement on infinite inputs with defined spines.They differ on partial lists. Take the first argument
[1] and the second argument . The original definition can emit its first head immediately:After recognizing the nonempty first argument, twiddle' must inspect the second argument to distinguish its second and third equations. That inspection diverges, soFor example, demanding only the head distinguishes them: the original returns 1, while the primed version diverges. Equality of functions under lazy evaluation requires agreement on these partial inputs too. New to topics? Read the docs here!