On Thu, 3 Jan 2008, Achim Schneider wrote: > Henning Thielemann <[EMAIL PROTECTED]> wrote: > > > Sometimes I believed that I understand this reason, but then again I > > do not understand. I see that left-associative (++) like in > > ((a0 ++ a1) ++ a2) ++ a3 > > would cause quadratic time. But (++) is right-associative and > > 'concat' is 'foldr'. They should not scan the leading lists more than > > once. Also > > http://en.wikipedia.org/wiki/Difference_list > > doesn't answer this question. Where exactly is the problem? > > > > | The shows functions return a function that prepends the output String > | to an existing String. This allows constant-time concatenation of > | results using function composition.
How is "constant-time concatenation" meant? If I process all list elements, it will need linear time. If I do not touch any element, I will need no time due to lazy evaluation. As far as I know, lazy evaluation is implemented by returning a union of a routine generating the actual value and the value, if it was already computed. Thus, calling (++) returns a function internally. > I figure it's (constant vs. linear) vs. (linear vs. quadratic), for > more involved examples. I can't see it. If I consider (x++y) but I do not evaluate any element of (x++y) or only the first element, then this will need constant time. If I evaluate the first n elements I need n computation time units. How is (.) on difference lists faster than (++) here? _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
