[Haskell-cafe] Re: Difference lists and ShowS
lemming at henning-thielemann.de
Thu Jan 3 09:55:40 EST 2008
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
> 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?
More information about the Haskell-Cafe