= Solution
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 $\operatorname{reverse}(xs\mathbin{++}ys)=\operatorname{reverse}(ys)\mathbin{++}\operatorname{reverse}(xs)$ and <structural induction>. The complete representation is processed and reconstructed in \b[$\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$.
Back to article page
