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

Albert Y. C. Lai trebla at vex.net
Thu Oct 13 20:53:16 CEST 2011

On 11-10-12 06:50 PM, Yves Parès wrote:
> []     ++ 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.

So let us need the whole list. Let us print length(xs++ys) and count costs.

The amount of time is Θ(length xs + length ys). You then say, that's the 
same cost as printing length xs and printing length ys. I agree.

The number of new cons cells created in due course is Θ(length xs). 
These cons cells would not have been created if we printed length xs and 
printed length ys separately.

(Sure, those new cons cells may be deallocated promptly. Or may be not.)

The cost of (++) is pretty affordable when all you do is xs++ys. The 
expensive part happens when you
(...(xs 0 ++ xs 1) ++ xs 2) ...) ++ xs (n-1)
printing the length of that takes quadratic time to the printed answer.

More information about the Haskell-Cafe mailing list