= Solution
Let there be $k$ inner <lists>, of lengths $\ell_1,\ldots,\ell_k$, and let $N=\sum_j\ell_j$. Evaluate the whole output <list> spine, taking each input element as an already available value. The defining equation `(x:xs) ++ ys = x : (xs ++ ys)` shows that <list concatenation> traverses its left operand, sharing its right operand.
The <right fold> puts each original inner <list> on the left of exactly one concatenation. Thus its total element traversal is proportional to $N$, and visiting the outer <list> costs $k$:
$$
\boxed{T_{\mathrm{right}}=\Theta(k+N).}
$$
The $k$ term matters when many inner <lists> are empty. With $k$ rows each of length $r$, the bound is $\Theta(k+kr)$. In particular, with uniformly bounded positive row length it is linear in $k$.
Back to article page
