Past exam of the year 1 of the computer science course of the University of Oxford / 2018 / Functional programming, design and analysis of algorithms / 3 / g

Reverse the children and recursively reverse each child:

rev :: CatList a -> CatList a
rev Nil       = Nil
rev (One x)   = One x
rev (Cat l r) = Cat (rev r) (rev l)

The proof uses $\mathrm{reverse}(xs++ys)=\mathrm{reverse}(ys)++\mathrm{reverse}(xs)$ and structural induction. The complete representation is processed and reconstructed in $\Theta (m)$ time. This is worst-case optimal for fully processing arbitrary explicit input representations with $m$ constructors; the datatype allows output information to be hidden at any leaf. Lazy evaluation can expose only an initial part of a result sooner, and this statement does not assert that every partial observation costs $m$.