On Wed, Aug 10, 2011 at 12:03 PM, Brandon Allbery
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