[Haskell-beginners] Why ShowS?

[yi huang]

On Wed, Aug 10, 2011 at 12:03 PM, Brandon Allbery <allbery.b at gmail.com>wrote:

> 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.
>

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 at gmail.com
> wandering unix systems administrator (available)     (412) 475-9364 vm/sms
>
>
> _______________________________________________
> Beginners mailing list
> Beginners at haskell.org
> http://www.haskell.org/mailman/listinfo/beginners
>
>


-- 
http://www.yi-programmer.com/blog/
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.haskell.org/pipermail/beginners/attachments/20110810/ae7cf5d5/attachment.htm>