[Haskell-cafe] appending an element to a list
mail at joachim-breitner.de
Thu May 29 13:40:37 EDT 2008
Am Donnerstag, den 29.05.2008, 19:04 +0200 schrieb Adrian Neumann:
> I was wondering how expensive appending something to a list really is.
> Say I write
> I'd say "longList ++ " 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’m no expert, but I give it shot:
The problem is that longList might be referenced somewhere else as well,
so it has to be kept around, ending in , not in . But (longList ++
) also might be referenced somewhere, so you also need to keep that
list. Thus you have to copy the whole list structure for the appending
(not the values, though).
For comparision, with (5:longList), the new list can use the old list
unmodified, so nothing has to be copied.
You can also observe this in the code for (++):
(++) :: [a] -> [a] -> [a]
(++)  ys = ys
(++) (x:xs) ys = x : xs ++ ys
where you can see that on the right hand side, a totally new list is
In some cases, e.g. when the longList is only referenced there and
nowhere else, one might hope that the compiler can optimize this problem
away. There is some hope, as I see this in the code:
"++" [~1] forall xs ys. xs ++ ys = augment (\c n -> foldr c n xs) ys
Maybe some core-literate people can give more information on this?
Joachim "nomeata" Breitner
mail: mail at joachim-breitner.de | ICQ# 74513189 | GPG-Key: 4743206C
JID: nomeata at joachim-breitner.de | http://www.joachim-breitner.de/
Debian Developer: nomeata at debian.org
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Size: 189 bytes
Desc: Dies ist ein digital signierter Nachrichtenteil
Url : http://www.haskell.org/pipermail/haskell-cafe/attachments/20080529/8bda745e/attachment.bin
More information about the Haskell-Cafe