= Solution
Repeated root removal gives the conventional <list>:
``
toList :: List a -> [a]
toList rs
| null rs = []
| otherwise = head rs : toList (tail rs)
``
The representation interpretation satisfies `toList (cons x rs) = x : toList rs`; alternatively, <structural induction> on the number of stored elements proves that each step emits exactly the next <preorder traversal> value. The output has $n$ cons cells, and each step takes <constant time>, so fully consuming it costs \b[$\Theta(n)$ time]. No repeated <list concatenation> is needed.
Back to article page
