Re: [Haskell-cafe] appending an element to a list

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