[Haskell-cafe] Lists concatenation being O(n)
apfelmus at quantentunnel.de
Fri Oct 14 15:17:17 CEST 2011
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
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)
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
More information about the Haskell-Cafe