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

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$.

Write $S_j={\ell }_1+\cdots +{\ell }_j$, with $S_0=0$. At the $j$th step of the left fold, the left operand of list concatenation is the accumulated prefix of length $S_{j-1}$. Fully forcing these concatenations repeatedly copies earlier elements. Including the traversal of the outer list and the whole output spine givesFor singleton inner lists, this becomes $\Theta (1+2+\cdots +(k-1))=\Theta (k^2)$, whereas the right fold takes $\Theta (k)$. More generally, for equal positive length $r$, the left fold takes $\Theta (r{k}^2+k)$.

An $O(kN+k)$ bound is tight in the worst case over length distributions, but is not a tight formula for every distribution: if all $N$ elements occur only in the final inner list, all earlier accumulators are empty and the cost is $\Theta (k+N)$. Lazy evaluation changes when the work happens; it does not remove repeated prefix traversal when the whole result is demanded.