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

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: [EMAIL PROTECTED] | ICQ# 74513189 | GPG-Key: 4743206C
  JID: [EMAIL PROTECTED] | http://www.joachim-breitner.de/
  Debian Developer: [EMAIL PROTECTED]

Attachment: signature.asc
Description: Dies ist ein digital signierter Nachrichtenteil

Haskell-Cafe mailing list

Reply via email to