[Haskell-beginners] Why ShowS?

[Brandon Allbery]

On Wed, Aug 10, 2011 at 00:41, yi huang <yi.codeplayer at gmail.com> wrote:

> (1) string concatenation:  step through the list of Char to reach the end,
>> then append the second string; this is linear in the length of "the quick
>> brown fox...".
>>
>> (2) list concatenation:  start with [], append "the quick brown fox...",
>> append "now is the time...".  Each concatenation is linear in the number of
>> strings already concatenated, so becomes expensive as more stings are
>> appended.
>>
>> (3) function composition:  (in effect) start with (const ""), compose it
>> with (++ "the quick brown fox...:), compose it with (++ "now is the
>> time...").  Each concatenation is constant time, since it's simply applying
>> (.) to what it has.
>>
>
> I don't understand, since (++) is lazy, the operation itself is very cheap,
> only traversing the concatenated list need O(n) time complexity, isn't that
> right?
>

Yes, but that's precisely what's being avoided.  The assumption for ShowS is
that you'll have to traverse it anyway to output it; ShowS avoids doing so
multiple times.

Now, as to how useful it is... you'll note there isn't actually a lot of
code out there that uses ShowS (or functional concatenation in general).
 The simplistic show/read system uses it, but most other parsers and string
generators use other mechanisms instead:  Monad, Applicative, occasionally
Arrow.  (ShowS/ReadS predates all three, I believe.  There may have also
been additional advantages with pre-monadic/Gofer-style I/O.)

There are also questions of stack/heap complexity; while it may save some
time to build up a large output string this way, it also builds up quite a
few thunks, whereas (especially with fusion) a more direct concatenation
system may have linear heap complexity and constant stack complexity.

(Also, coming at it from a systems perspective, I can't help but think that
I/O time dominates concatenation time in the vast majority of cases.)

-- 
brandon s allbery                                      allbery.b at gmail.com
wandering unix systems administrator (available)     (412) 475-9364 vm/sms
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.haskell.org/pipermail/beginners/attachments/20110810/096a3524/attachment.htm>