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@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@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe