On Thu, May 29, 2008 at 11:48 PM, Tillmann Rendel <rendel@daimi.au.dk> wrote:

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

In other words, if you look at the prototype of ++ given in the prelude, it generates a new list with first (length longList) elements same as those of longList, followed by the second list. So when you are accessing elements of (longList ++ s), you are actually accessing the elements of this newly generated list, which are generated as and when you access them, so that by the time you reach the first element of s, you have generated (length longList) elements of the result of ++.

_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe