[Haskell-cafe] Re: Difference lists and ShowS

[Henning Thielemann]

On Thu, 3 Jan 2008, Achim Schneider wrote:

> Henning Thielemann <lemming at henning-thielemann.de> 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?