Past exam of the year 1 of the computer science course of the University of Oxford / 2019 / Functional programming, design and analysis of algorithms / 1 / e / Solution

Let $F=\mathrm{foldl}(\ominus )0$, using the specified operation $u\ominus v=v-u$. Direct evaluation gives $F([])=0$, $F([0])=0$, $F([1])=1$, and $F([1,0])=-1$.

Suppose $F=\mathrm{foldr}cb$ with the same integer result type. The empty list forces $b=0$. The two singleton calculations force $c00=0$ and $c10=1$. But thencontrary to $F([1,0])=-1$. No such c,b exist. This is the information restriction in the fold factorisation criterion: equal folded tails must remain indistinguishable after the same head is attached. A larger, function-valued result type can retain the missing information, as the continuation representation of a left fold does below.