[Haskell-cafe] appending an element to a list

[Tillmann Rendel]

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.

   Tillmann