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 / ii

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.