[Haskell-cafe] appending an element to a list
rendel at daimi.au.dk
Thu May 29 14:18:19 EDT 2008
Adrian Neumann wrote:
> I was wondering how expensive appending something to a list really is.
> Say I write
> I'd say "longList ++ " stays unevaluated until I consumed the whole
> list and then appending should go in O(1). Similarly when concatenating
> two lists.
> Is that true, or am I missing something?
I think that is true and you are missing something: You have to push the
call to ++ through the whole longList while consuming it wholy one
element at a time! So when longList has n elements, you have (n+1) calls
of ++, each returning after O(1) steps. The first n calls return a list
with the ++ pushed down, and the last returns . Summed together, that
makes O(n) actual calls of ++ for one written by the programmer.
More information about the Haskell-Cafe