Re: [Haskell-beginners] Why ShowS?

On 08/09/2011 09:10 PM, Brandon Allbery wrote:

On Wed, Aug 10, 2011 at 00:41, yi huang mailto:yi.codeplayer@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@gmail.com mailto:allbery.b@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