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

[Yves Parès]

Okay, thanks.

I got to wonder that because I was implementing a Show instance (for a game
grid, like an Othello), and string manipulation usually comes with a heavy
usage of (++).
I'm just using a strict left-fold on the game grid (e.g. Vector (Maybe
Pawn)) with a combination of show (converting the pawns to Strings) and
(++).
Is there a more efficient way to do so? (for instance using Text and
converting it back to String?)

> 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.
Okay, so the major problem comes from memory management.

> The expensive part happens when you
> (...(xs 0 ++ xs 1) ++ xs 2) ...) ++ xs (n-1)
Okay, because it constantly recreate new cons cells.

2011/10/13 Albert Y. C. Lai <trebla at vex.net>

> 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.
>
>
> ______________________________**_________________
> Haskell-Cafe mailing list
> Haskell-Cafe at haskell.org
> http://www.haskell.org/**mailman/listinfo/haskell-cafe<http://www.haskell.org/mailman/listinfo/haskell-cafe>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.haskell.org/pipermail/haskell-cafe/attachments/20111013/bee5971b/attachment.htm>