On Wed, Aug 10, 2011 at 12:03 PM, Brandon Allbery wrote:

On Tue, Aug 9, 2011 at 23:34, Christopher Howard < christopher.howard@frigidcode.com> wrote:

...

What is meant here by "constant-time concatenation of results using function composition"? Perhaps someone could provide an example?

In effect, ShowS concatenates chunks instead of strings; you could think of it as building a list of strings, except that even then concatenation means going to the end of the list to append the new item, whereas the right-biased precedence of function composition means that it's already holding a pointer to the end of the "list" (instead of the beginning, as with normal lists).

So, concatenating

...

"the quick brown fox jumps over the lazy dog" and "now is the time for all good endofunctors to come to the aid of their category"

your choices are:

(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?

In all three cases, you have essentially the same time complexity in outputting the result.

-- brandon s allbery allbery.b@gmail.com wandering unix systems administrator (available) (412) 475-9364 vm/sms

_______________________________________________ Beginners mailing list Beginners@haskell.org http://www.haskell.org/mailman/listinfo/beginners

-- http://www.yi-programmer.com/blog/

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

Brandon Allbery wrote:

Now, as to how useful it is... you'll note there isn't actually a lot of code out there that uses ShowS

I use it sometimes. ShowS was the first and simplest, "pretty-printer" library. A pretty-printer library is an alternative to big ugly monolithic expressions for creating output. Because it is based on function composition, ShowS makes it easier to write in a nice combinator style. All of the early pretty-printer libraries used function composition in this way. It appears early library writers assumed that because of its advantages, and also because of certain limitations of early compilers, everyone would always use ShowS instead of directly constructing Strings. So they used ShowS for the types of showHex and showOct. In reality ShowS never caught on, but it's not worth the trouble to change those original types now.

 The simplistic show/read system uses it, but most other parsers and string generators use other mechanisms instead: Monad, Applicative, occasionally Arrow.

Recently the trend is to use "builders" based on Monoid for fast rendering libraries. That style has some of the advantages of ShowS, plus, unlike ShowS, it works equally well with ByteString and Text. While not the fastest or most featureful, ShowS still has the advantages of being really simple to use, available directly from the Prelude without any external library (and thus a standard style, even though it isn't as popular as it could be), and it generally has a pleasing simplifying effect on the surrounding code. It also works absolutely seamlessly with showHex and showOct :). Any big expression of type String that starts with "concat" followed by a long list of String expressions is a good candidate for using ShowS instead. Here is a simple example of how to use ShowS: showPerson :: String -> Int -> Int -> String showPerson name age shoeSize = concat [ "Name: ", name, ", Age: ", show age, ", Shoe size: ", show shoeSize] ... putStrLn $ showPerson name age shoe becomes, in the ShowS style: showsPerson :: String -> Int -> Int -> ShowS showsPerson name age shoeSize = ("Name: " ++) . (name ++) . (", Age: " ++) . shows age . (", Shoe size: " ++) . shows shoeSize ... putStrLn $ showsPerson name age shoe "" Regards, Yitz

I wrote:

...

Here is a simple example of how to use ShowS...

Christian Maeder wrote:

I think, this examples shows, why ShowS is rarely used!

I understand your feelings. The sections of ++ do look awkward on the surface, though in practice it's not really much of an issue.

It would even be longer if you used "showString" instead of these (ugly) sections with ++ (instead of using ++ directly).

Yes. That's why I used the sections in my examples, instead of the Prelude function "showString". Most other function-composition-style pretty-printing libraries using something shorter than "showString", like "text", to replace the ++ sections. Then it comes out the same length. You could use something even shorter. But saving a few keystrokes is not the point. The point is writing the expression as a compositional pipeline, which is conceptually nice, and more or less the same complexity in syntax.

I don't think, there's a performance issue, either. (++ is right-associative).

I think you're right. That was more of an issue for early compilers.

Creating a (better formatted) list of strings and then using "concat", "unwords", "unlines" or "intercalate ", " is quite a good choice.

Indeed, it's fine, and it's the most popular. Once you realize the beauty and power of the compositional combinator approach in general, though, using that approach also for rendering becomes an attractive alternative. Especially in situations where you might want to insert other combinators into the pipeline. Anyway, I think that's a more complete answer to Christopher's original question about ShowS. Thanks, Yitz