[Haskell-cafe] Re: Difference lists and ShowS

[Achim Schneider]

Henning Thielemann <lemming at henning-thielemann.de> wrote:

> > 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?
>
It's in multiple calls to length if you do ((x++y)++z), the first run
over x can be avoided. It basically gets rewritten to (x++y++z) by
another level of abstraction.


-- 
(c) this sig last receiving data processing entity. Inspect headers for
past copyright information. All rights reserved. Unauthorised copying,
hiring, renting, public performance and/or broadcasting of this
signature prohibited.