[Haskell-beginners] Why ShowS?

[Brandon Allbery]

On Tue, Aug 9, 2011 at 23:34, Christopher Howard <
christopher.howard at 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.

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

-- 
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/6904f527/attachment-0001.htm>