Hi, 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 ++ [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’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 [5]. But (longList ++ [5]) 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 constructed. 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: {-# RULES "++" [~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? Greetings, Joachim -- Joachim "nomeata" Breitner mail: mail@joachim-breitner.de | ICQ# 74513189 | GPG-Key: 4743206C JID: nomeata@joachim-breitner.de | http://www.joachim-breitner.de/ Debian Developer: nomeata@debian.org