[Haskell-beginners] Why ShowS?

[Christopher Howard]

On 08/09/2011 09:10 PM, Brandon Allbery wrote:
> On Wed, Aug 10, 2011 at 00:41, yi huang <yi.codeplayer at gmail.com
> <mailto: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 <mailto:allbery.b at gmail.com>
> wandering unix systems administrator (available)     (412) 475-9364 vm/sms
>

One of the reasons I asked: I was wondering if Haskell already had a 
library that would take an Int/Integer and convert it to the string 
representations of other bases; or if this was a chore that still needed 
to be taken care of by someone. I found the Numeric module, but then see 
that all relevant functions return this weird "ShowS" instead of a 
String. So... is that how everyone likes it? Or is there another module 
people use for base conversion...?

-- 
frigidcode.com
theologia.indicium.us