[Haskell-cafe] Lists concatenation being O(n)

[Yves Parès]

Hello,

I re-read recently a bit of RealWorldHaskell, and I saw something that
puzzles me now that I have a better understanding of the language.
It concerns the list concatenation being costful, and the need to use
another type like DList.

[]     ++ ys = ys
(x:xs) ++ ys = x : (xs ++ ys)

To me, we have here something that would be costful in a strict language,
but that here, thanks to guarded recursion ((:) being non-strict), doesn't
evaluate the first list until it is needed.

How comes RHW says "We can see that the cost of creating a new list depends
on the length of the initial list", since nothing will be done unless we ask
for our list to be evaluated, which is somewhat something we will end up
asking.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.haskell.org/pipermail/haskell-cafe/attachments/20111013/8b808243/attachment.htm>