= Solution
Use `map k (u:us) = k u : map k us`, list-map fusion, and the <left fold> equation
``
foldl f e (x:ys) = foldl f (f e x) ys
``
For the empty list, the prefix definition immediately gives `scanl f e [] = [e]`. For a nonempty list, calculate:
``
scanl f e (x:xs)
= map (foldl f e) ([] : map (x:) (inits xs))
= e : map ((foldl f e) . (x:)) (inits xs)
= e : map (foldl f (f e x)) (inits xs)
= e : scanl f (f e x) xs
``
The second-to-third line uses the displayed fold equation as an equality of functions of `ys`. Hence the efficient <left scan> is:
``
scanl :: (b -> a -> b) -> b -> [a] -> [b]
scanl f e [] = [e]
scanl f e (x:xs) = e : scanl f (f e x) xs
``
On a finite input of length $n$, fully demanding the original prefix-fold results performs $0+1+\cdots+n=n(n+1)/2$ accumulator updates. The recurrence performs $n$. Thus the update count improves from \b[$\Theta(n^2)$ to $\Theta(n)$], assuming constant-cost updates. Both return $n+1$ results. This does not assert constant space for arbitrary accumulators or imply that lazy accumulators are evaluated strictly.
Back to article page
