Okay, thanks.<br><br>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 (++).<br>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 (++).<br>
Is there a more efficient way to do so? (for instance using Text and converting it back to String?)<br><br>>
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.<br>Okay, so the major problem comes from memory management.<br><br>> The expensive part happens when you<br>> (...(xs 0 ++ xs 1) ++ xs 2) ...) ++ xs (n-1)<br>Okay, because it constantly recreate new cons cells.<br>
<br><div class="gmail_quote">2011/10/13 Albert Y. C. Lai <span dir="ltr"><<a href="mailto:trebla@vex.net">trebla@vex.net</a>></span><br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex;">
On 11-10-12 06:50 PM, Yves Parès wrote:<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
[] ++ ys = ys<div class="im"><br>
(x:xs) ++ ys = x : (xs ++ ys)<br>
<br>
To me, we have here something that would be costful in a strict<br>
language, but that here, thanks to guarded recursion ((:) being<br>
non-strict), doesn't evaluate the first list until it is needed.<br>
</div></blockquote>
<br>
So let us need the whole list. Let us print length(xs++ys) and count costs.<br>
<br>
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.<br>
<br>
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.<br>
<br>
(Sure, those new cons cells may be deallocated promptly. Or may be not.)<br>
<br>
The cost of (++) is pretty affordable when all you do is xs++ys. The expensive part happens when you<br>
(...(xs 0 ++ xs 1) ++ xs 2) ...) ++ xs (n-1)<br>
printing the length of that takes quadratic time to the printed answer.<br>
<br>
<br>
______________________________<u></u>_________________<br>
Haskell-Cafe mailing list<br>
<a href="mailto:Haskell-Cafe@haskell.org" target="_blank">Haskell-Cafe@haskell.org</a><br>
<a href="http://www.haskell.org/mailman/listinfo/haskell-cafe" target="_blank">http://www.haskell.org/<u></u>mailman/listinfo/haskell-cafe</a><br>
</blockquote></div><br>