Re: [Haskell-cafe] Re: Difference lists and ShowS

On Thu, 3 Jan 2008, Achim Schneider wrote:

Henning Thielemann 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?