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

[Heinrich Apfelmus]

Yves Parès wrote:
> 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.

Well, the run-time needed to evaluate an expression depends on how much 
of the expression you evaluate. If you don't evaluate anything, then you 
don't need any time.

The cost of list concatenation refers to the following fact:

"Assuming that  xs  and  ys  have been evaluated to normal form already, 
then the cost of evaluating  xs ++ ys  to normal form is Θ(length xs) 
reduction steps."

For difference lists, the latter cost is only Θ(1).


The best way to reason about other "demand patterns" than normal form is 
Okasaki's method of attributing a debt to each constructor. See also

   http://apfelmus.nfshost.com/articles/debit-method.html


Best regards,
Heinrich Apfelmus

--
http://apfelmus.nfshost.com