[Haskell-cafe] Re: Difference lists and ShowS (Was: The
barsoap at web.de
Thu Jan 3 09:41:15 EST 2008
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
> 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.
I figure it's (constant vs. linear) vs. (linear vs. quadratic), for
more involved examples.
(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
More information about the Haskell-Cafe