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.