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

Let there be $k$ inner lists, of lengths ${\ell }_1,\dots ,{\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$: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$.