Past exam of the year 1 of the computer science course of the University of Oxford / 2021 / Functional programming, design and analysis of algorithms (resit) / 1 / a / Solution

The empty-list case uses $f(a)=b$. At a cons, assuming the equality for the tail, the calculation isThe middle equality is the supplied compatibility condition, instantiated with the folded tail; the last expression is the right fold on the whole list. Structural induction therefore proves fusion for finite total spines.

The strictness condition accounts for a bottom-valued input spine: the inner list fold returns bottom, and $f(\perp )=\perp$ makes the two sides agree. The same induction covers finite partial lists. For pure definable continuous functions, an infinite list is the limit of its finite partial approximations, so equality extends to it. These are the three distinct obligations in the right-fold fusion law; strictness is not needed if the domain is restricted to finite terminating spines.