[Haskell-cafe] appending an element to a list

Tillmann Rendel rendel at daimi.au.dk
Thu May 29 14:18:19 EDT 2008

Adrian Neumann wrote:
> Hello,
> I was wondering how expensive appending something to a list really is. 
> Say I write
> I'd say "longList ++ [5]" 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 [5]. Summed together, that 
makes O(n) actual calls of ++ for one written by the programmer.


More information about the Haskell-Cafe mailing list