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
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
