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

[Achim Schneider]

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.