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

Use structural induction on the finite list xs, strengthening the induction hypothesis to hold for every accumulator value $y$. For the empty list, the defining equation of the left fold givesFor the inductive step, suppose the identity holds for the tail zs and every accumulator. Expand the first left fold, apply the induction hypothesis at accumulator $y\otimes z$, and then use the supplied compatibility law:HenceOnly equation (1) is needed for this part; the seed condition in equation (2) enters the next proof. Quantifying over the accumulator is essential because the recursive call changes it.

Again use structural induction on the finite list. At [], both the right fold and the left fold return the seed $a$. If they agree on zs, thenThe third line uses part (a); the fourth uses equation (2). Thus the left-right fold equivalence isThis is a statement about values on finite, total inputs. It does not assert equal evaluation costs or equal behaviour on infinite lists.

Use list concatenation as the combining operation and the empty list as the seed:

concat :: [[a]] -> [a]
concat = foldr (++) []

For three inner lists, this constructs xs ++ (ys ++ (zs ++ [])), preserving the elements' original order. The concise answer is $\boxed{\mathrm{concat}=\mathrm{foldr}(++)[]}$.

Set both $\oplus$ and $\otimes$ equal to list concatenation, with $a=[]$. Associativity gives xs ++ (ys ++ zs) = (xs ++ ys) ++ zs, which is equation (1). The two identity laws give xs ++ [] = [] ++ xs, which is equation (2). Part (b) therefore yields

concat :: [[a]] -> [a]
concat = foldl (++) []

Thus $\boxed{\mathrm{concat}=\mathrm{foldl}(++)[]}$ on finite lists. The argument order is unchanged: the accumulator is the already concatenated prefix, and the next inner list is appended to its right. This preserves the order but repeatedly copies that prefix.

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.