= Left scan
{title2=`scanl :: (b -> a -> b) -> b -> [a] -> [b]`}
Return the successive accumulator values of a <left fold>, including the initial accumulator: `scanl f e [] = [e]` and `scanl f e (x:xs) = e : scanl f (f e x) xs`. The $k$th result is the fold of the first $k$ elements, proved by the fold equation. Thus the scan equals `map (foldl f e) . inits`, but computes $n$ updates instead of $n(n+1)/2$ on a finite input of length $n$. Accumulator strictness and the cost of an update remain separate from this operation count.
Back to article page
