[Haskell-cafe] appending an element to a list

[Joachim Breitner]

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 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
Type: application/pgp-signature
Size: 189 bytes
Desc: Dies ist ein digital signierter Nachrichtenteil
Url : http://www.haskell.org/pipermail/haskell-cafe/attachments/20080529/8bda745e/attachment.bin