[Haskell-cafe] Re: Difference lists and ShowS (Was: The Worker/Wrapper Transformation)

Achim Schneider 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
>   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. 

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
signature prohibited. 

More information about the Haskell-Cafe mailing list