[Haskell-cafe] Re: Difference lists and ShowS

Achim Schneider barsoap at web.de
Thu Jan 3 10:13:17 EST 2008

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. 

More information about the Haskell-Cafe mailing list