= Solution
All three denote \b[`iterate :: (a -> a) -> a -> [a]`], producing $x,g(x),g^2(x),\ldots$. With <lazy evaluation>, demanding and fully evaluating the first $n$ elements costs \b[$\Theta(n)$ for `f1` and `f2`, and $\Theta(n^2)$ worst-case for `f3`], under the unit-cost application assumption.
In `f1` the next state is obtained with one new application of `g`. In `f2`, the shared binding `xs` points back to the already generated <list>; each new element maps `g` over a shared predecessor once. In `f3`, the recursive `f3 g x` is a fresh computation. Producing output position $j$ passes through $j$ separately constructed map layers, so a strict `g` causes $0+1+\cdots+(n-1)$ applications. A non-strict function such as `const 0` can avoid work, so the quadratic statement is a worst-case evaluation bound, not a lower bound for every possible `g`. Merely demanding the outer list spine without its elements is a different cost question.
Back to article page
